1 | /* | |
2 | * Copyright 2006 - 2013 | |
3 | * Stefan Balev <stefan.balev@graphstream-project.org> | |
4 | * Julien Baudry <julien.baudry@graphstream-project.org> | |
5 | * Antoine Dutot <antoine.dutot@graphstream-project.org> | |
6 | * Yoann Pign������ <yoann.pigne@graphstream-project.org> | |
7 | * Guilhelm Savin <guilhelm.savin@graphstream-project.org> | |
8 | * | |
9 | * This file is part of GraphStream <http://graphstream-project.org>. | |
10 | * | |
11 | * GraphStream is a library whose purpose is to handle static or dynamic | |
12 | * graph, create them from scratch, file or any source and display them. | |
13 | * | |
14 | * This program is free software distributed under the terms of two licenses, the | |
15 | * CeCILL-C license that fits European law, and the GNU Lesser General Public | |
16 | * License. You can use, modify and/ or redistribute the software under the terms | |
17 | * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following | |
18 | * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by | |
19 | * the Free Software Foundation, either version 3 of the License, or (at your | |
20 | * option) any later version. | |
21 | * | |
22 | * This program is distributed in the hope that it will be useful, but WITHOUT ANY | |
23 | * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A | |
24 | * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. | |
25 | * | |
26 | * You should have received a copy of the GNU Lesser General Public License | |
27 | * along with this program. If not, see <http://www.gnu.org/licenses/>. | |
28 | * | |
29 | * The fact that you are presently reading this means that you have had | |
30 | * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. | |
31 | */ | |
32 | package org.graphstream.graph.implementations; | |
33 | ||
34 | import java.util.Arrays; | |
35 | import java.util.HashMap; | |
36 | import java.util.Iterator; | |
37 | import java.util.NoSuchElementException; | |
38 | ||
39 | import org.graphstream.graph.Edge; | |
40 | import org.graphstream.graph.EdgeFactory; | |
41 | import org.graphstream.graph.Graph; | |
42 | import org.graphstream.graph.Node; | |
43 | import org.graphstream.graph.NodeFactory; | |
44 | ||
45 | /** | |
46 | * <p> | |
47 | * A lightweight graph class intended to allow the construction of big graphs | |
48 | * (millions of elements). | |
49 | * </p> | |
50 | * | |
51 | * <p> | |
52 | * The main purpose here is to minimize memory consumption even if the | |
53 | * management of such a graph implies more CPU consuming. See the | |
54 | * <code>complexity</code> tags on each method so as to figure out the impact on | |
55 | * the CPU. | |
56 | * </p> | |
57 | */ | |
58 | public class AdjacencyListGraph extends AbstractGraph { | |
59 | ||
60 | public static final double GROW_FACTOR = 1.1; | |
61 | public static final int DEFAULT_NODE_CAPACITY = 128; | |
62 | public static final int DEFAULT_EDGE_CAPACITY = 1024; | |
63 | ||
64 | protected HashMap<String, AbstractNode> nodeMap; | |
65 | protected HashMap<String, AbstractEdge> edgeMap; | |
66 | ||
67 | protected AbstractNode[] nodeArray; | |
68 | protected AbstractEdge[] edgeArray; | |
69 | ||
70 | protected int nodeCount; | |
71 | protected int edgeCount; | |
72 | ||
73 | // *** Constructors *** | |
74 | ||
75 | /** | |
76 | * Creates an empty graph. | |
77 | * | |
78 | * @param id | |
79 | * Unique identifier of the graph. | |
80 | * @param strictChecking | |
81 | * If true any non-fatal error throws an exception. | |
82 | * @param autoCreate | |
83 | * If true (and strict checking is false), nodes are | |
84 | * automatically created when referenced when creating a edge, | |
85 | * even if not yet inserted in the graph. | |
86 | * @param initialNodeCapacity | |
87 | * Initial capacity of the node storage data structures. Use this | |
88 | * if you know the approximate maximum number of nodes of the | |
89 | * graph. The graph can grow beyond this limit, but storage | |
90 | * reallocation is expensive operation. | |
91 | * @param initialEdgeCapacity | |
92 | * Initial capacity of the edge storage data structures. Use this | |
93 | * if you know the approximate maximum number of edges of the | |
94 | * graph. The graph can grow beyond this limit, but storage | |
95 | * reallocation is expensive operation. | |
96 | */ | |
97 | public AdjacencyListGraph(String id, boolean strictChecking, boolean autoCreate, | |
98 | int initialNodeCapacity, int initialEdgeCapacity) { | |
99 | super(id, strictChecking, autoCreate); | |
100 | ||
101 |
1
1. |
setNodeFactory(new NodeFactory<AdjacencyListNode>() { |
102 | public AdjacencyListNode newInstance(String id, Graph graph) { | |
103 |
1
1. newInstance : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListGraph$1::newInstance to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return new AdjacencyListNode((AbstractGraph) graph, id); |
104 | } | |
105 | }); | |
106 | ||
107 |
1
1. |
setEdgeFactory(new EdgeFactory<AbstractEdge>() { |
108 | public AbstractEdge newInstance(String id, Node src, Node dst, | |
109 | boolean directed) { | |
110 |
1
1. newInstance : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListGraph$2::newInstance to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return new AbstractEdge(id, (AbstractNode) src, |
111 | (AbstractNode) dst, directed); | |
112 | } | |
113 | }); | |
114 | ||
115 | nodeMap = new HashMap<String, AbstractNode>( | |
116 |
3
1. 2. 3. |
4 * initialNodeCapacity / 3 + 1); |
117 | edgeMap = new HashMap<String, AbstractEdge>( | |
118 |
3
1. 2. 3. |
4 * initialEdgeCapacity / 3 + 1); |
119 | nodeArray = new AbstractNode[initialNodeCapacity]; | |
120 | edgeArray = new AbstractEdge[initialEdgeCapacity]; | |
121 | nodeCount = edgeCount = 0; | |
122 | } | |
123 | ||
124 | /** | |
125 | * Creates an empty graph with default edge and node capacity. | |
126 | * | |
127 | * @param id | |
128 | * Unique identifier of the graph. | |
129 | * @param strictChecking | |
130 | * If true any non-fatal error throws an exception. | |
131 | * @param autoCreate | |
132 | * If true (and strict checking is false), nodes are | |
133 | * automatically created when referenced when creating a edge, | |
134 | * even if not yet inserted in the graph. | |
135 | */ | |
136 | public AdjacencyListGraph(String id, boolean strictChecking, boolean autoCreate) { | |
137 | this(id, strictChecking, autoCreate, DEFAULT_NODE_CAPACITY, | |
138 | DEFAULT_EDGE_CAPACITY); | |
139 | } | |
140 | ||
141 | /** | |
142 | * Creates an empty graph with strict checking and without auto-creation. | |
143 | * | |
144 | * @param id | |
145 | * Unique identifier of the graph. | |
146 | */ | |
147 | public AdjacencyListGraph(String id) { | |
148 | this(id, true, false); | |
149 | } | |
150 | ||
151 | // *** Callbacks *** | |
152 | ||
153 | @Override | |
154 | protected void addEdgeCallback(AbstractEdge edge) { | |
155 | edgeMap.put(edge.getId(), edge); | |
156 |
1
1. addEdgeCallback : negated conditional → SURVIVED |
if (edgeCount == edgeArray.length) { |
157 |
2
1. addEdgeCallback : Replaced double multiplication with division → NO_COVERAGE 2. addEdgeCallback : Replaced integer addition with subtraction → NO_COVERAGE |
AbstractEdge[] tmp = new AbstractEdge[(int) (edgeArray.length * GROW_FACTOR) + 1]; |
158 |
1
1. addEdgeCallback : removed call to java/lang/System::arraycopy → NO_COVERAGE |
System.arraycopy(edgeArray, 0, tmp, 0, edgeArray.length); |
159 |
1
1. addEdgeCallback : removed call to java/util/Arrays::fill → NO_COVERAGE |
Arrays.fill(edgeArray, null); |
160 | edgeArray = tmp; | |
161 | } | |
162 | edgeArray[edgeCount] = edge; | |
163 |
2
1. addEdgeCallback : removed call to org/graphstream/graph/implementations/AbstractEdge::setIndex → SURVIVED 2. addEdgeCallback : Replaced integer addition with subtraction → KILLED |
edge.setIndex(edgeCount++); |
164 | } | |
165 | ||
166 | @Override | |
167 | protected void addNodeCallback(AbstractNode node) { | |
168 | nodeMap.put(node.getId(), node); | |
169 |
1
1. addNodeCallback : negated conditional → SURVIVED |
if (nodeCount == nodeArray.length) { |
170 |
2
1. addNodeCallback : Replaced double multiplication with division → NO_COVERAGE 2. addNodeCallback : Replaced integer addition with subtraction → NO_COVERAGE |
AbstractNode[] tmp = new AbstractNode[(int) (nodeArray.length * GROW_FACTOR) + 1]; |
171 |
1
1. addNodeCallback : removed call to java/lang/System::arraycopy → NO_COVERAGE |
System.arraycopy(nodeArray, 0, tmp, 0, nodeArray.length); |
172 |
1
1. addNodeCallback : removed call to java/util/Arrays::fill → NO_COVERAGE |
Arrays.fill(nodeArray, null); |
173 | nodeArray = tmp; | |
174 | } | |
175 | nodeArray[nodeCount] = node; | |
176 |
2
1. addNodeCallback : removed call to org/graphstream/graph/implementations/AbstractNode::setIndex → SURVIVED 2. addNodeCallback : Replaced integer addition with subtraction → KILLED |
node.setIndex(nodeCount++); |
177 | } | |
178 | ||
179 | @Override | |
180 | protected void removeEdgeCallback(AbstractEdge edge) { | |
181 | edgeMap.remove(edge.getId()); | |
182 | int i = edge.getIndex(); | |
183 |
1
1. removeEdgeCallback : Replaced integer subtraction with addition → KILLED |
edgeArray[i] = edgeArray[--edgeCount]; |
184 |
1
1. removeEdgeCallback : removed call to org/graphstream/graph/implementations/AbstractEdge::setIndex → SURVIVED |
edgeArray[i].setIndex(i); |
185 | edgeArray[edgeCount] = null; | |
186 | } | |
187 | ||
188 | @Override | |
189 | protected void removeNodeCallback(AbstractNode node) { | |
190 | nodeMap.remove(node.getId()); | |
191 | int i = node.getIndex(); | |
192 |
1
1. removeNodeCallback : Replaced integer subtraction with addition → KILLED |
nodeArray[i] = nodeArray[--nodeCount]; |
193 |
1
1. removeNodeCallback : removed call to org/graphstream/graph/implementations/AbstractNode::setIndex → SURVIVED |
nodeArray[i].setIndex(i); |
194 | nodeArray[nodeCount] = null; | |
195 | } | |
196 | ||
197 | @Override | |
198 | protected void clearCallback() { | |
199 |
1
1. clearCallback : removed call to java/util/HashMap::clear → SURVIVED |
nodeMap.clear(); |
200 |
1
1. clearCallback : removed call to java/util/HashMap::clear → SURVIVED |
edgeMap.clear(); |
201 |
1
1. clearCallback : removed call to java/util/Arrays::fill → SURVIVED |
Arrays.fill(nodeArray, 0, nodeCount, null); |
202 |
1
1. clearCallback : removed call to java/util/Arrays::fill → SURVIVED |
Arrays.fill(edgeArray, 0, edgeCount, null); |
203 | nodeCount = edgeCount = 0; | |
204 | } | |
205 | ||
206 | @SuppressWarnings("unchecked") | |
207 | @Override | |
208 | public <T extends Edge> T getEdge(String id) { | |
209 |
1
1. getEdge : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListGraph::getEdge to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return (T) edgeMap.get(id); |
210 | } | |
211 | ||
212 | @SuppressWarnings("unchecked") | |
213 | @Override | |
214 | public <T extends Edge> T getEdge(int index) { | |
215 |
4
1. getEdge : changed conditional boundary → SURVIVED 2. getEdge : changed conditional boundary → KILLED 3. getEdge : negated conditional → KILLED 4. getEdge : negated conditional → KILLED |
if (index < 0 || index >= edgeCount) |
216 | throw new IndexOutOfBoundsException("Edge " + index | |
217 | + " does not exist"); | |
218 |
1
1. getEdge : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListGraph::getEdge to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return (T) edgeArray[index]; |
219 | } | |
220 | ||
221 | @Override | |
222 | public int getEdgeCount() { | |
223 |
1
1. getEdgeCount : replaced return of integer sized value with (x == 0 ? 1 : 0) → KILLED |
return edgeCount; |
224 | } | |
225 | ||
226 | @SuppressWarnings("unchecked") | |
227 | @Override | |
228 | public <T extends Node> T getNode(String id) { | |
229 |
1
1. getNode : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListGraph::getNode to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return (T) nodeMap.get(id); |
230 | } | |
231 | ||
232 | @SuppressWarnings("unchecked") | |
233 | @Override | |
234 | public <T extends Node> T getNode(int index) { | |
235 |
4
1. getNode : changed conditional boundary → KILLED 2. getNode : changed conditional boundary → KILLED 3. getNode : negated conditional → KILLED 4. getNode : negated conditional → KILLED |
if (index < 0 || index > nodeCount) |
236 | throw new IndexOutOfBoundsException("Node " + index | |
237 | + " does not exist"); | |
238 |
1
1. getNode : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListGraph::getNode to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return (T) nodeArray[index]; |
239 | } | |
240 | ||
241 | @Override | |
242 | public int getNodeCount() { | |
243 |
1
1. getNodeCount : replaced return of integer sized value with (x == 0 ? 1 : 0) → KILLED |
return nodeCount; |
244 | } | |
245 | ||
246 | // *** Iterators *** | |
247 | ||
248 | protected class EdgeIterator<T extends Edge> implements Iterator<T> { | |
249 | int iNext = 0; | |
250 | int iPrev = -1; | |
251 | ||
252 | public boolean hasNext() { | |
253 |
4
1. hasNext : changed conditional boundary → KILLED 2. hasNext : negated conditional → KILLED 3. hasNext : replaced return of integer sized value with (x == 0 ? 1 : 0) → KILLED 4. hasNext : replaced return of integer sized value with (x == 0 ? 1 : 0) → KILLED |
return iNext < edgeCount; |
254 | } | |
255 | ||
256 | @SuppressWarnings("unchecked") | |
257 | public T next() { | |
258 |
2
1. next : changed conditional boundary → SURVIVED 2. next : negated conditional → KILLED |
if (iNext >= edgeCount) |
259 | throw new NoSuchElementException(); | |
260 |
1
1. next : Replaced integer addition with subtraction → KILLED |
iPrev = iNext++; |
261 |
1
1. next : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListGraph$EdgeIterator::next to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return (T) edgeArray[iPrev]; |
262 | } | |
263 | ||
264 | public void remove() { | |
265 |
1
1. remove : negated conditional → NO_COVERAGE |
if (iPrev == -1) |
266 | throw new IllegalStateException(); | |
267 |
1
1. remove : removed call to org/graphstream/graph/implementations/AdjacencyListGraph::removeEdge → NO_COVERAGE |
removeEdge(edgeArray[iPrev], true, true, true); |
268 | iNext = iPrev; | |
269 | iPrev = -1; | |
270 | } | |
271 | } | |
272 | ||
273 | protected class NodeIterator<T extends Node> implements Iterator<T> { | |
274 | int iNext = 0; | |
275 | int iPrev = -1; | |
276 | ||
277 | public boolean hasNext() { | |
278 |
4
1. hasNext : changed conditional boundary → KILLED 2. hasNext : negated conditional → KILLED 3. hasNext : replaced return of integer sized value with (x == 0 ? 1 : 0) → KILLED 4. hasNext : replaced return of integer sized value with (x == 0 ? 1 : 0) → KILLED |
return iNext < nodeCount; |
279 | } | |
280 | ||
281 | @SuppressWarnings("unchecked") | |
282 | public T next() { | |
283 |
2
1. next : changed conditional boundary → SURVIVED 2. next : negated conditional → KILLED |
if (iNext >= nodeCount) |
284 | throw new NoSuchElementException(); | |
285 |
1
1. next : Replaced integer addition with subtraction → KILLED |
iPrev = iNext++; |
286 |
1
1. next : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListGraph$NodeIterator::next to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return (T) nodeArray[iPrev]; |
287 | } | |
288 | ||
289 | public void remove() { | |
290 |
1
1. remove : negated conditional → NO_COVERAGE |
if (iPrev == -1) |
291 | throw new IllegalStateException(); | |
292 |
1
1. remove : removed call to org/graphstream/graph/implementations/AdjacencyListGraph::removeNode → NO_COVERAGE |
removeNode(nodeArray[iPrev], true); |
293 | iNext = iPrev; | |
294 | iPrev = -1; | |
295 | } | |
296 | } | |
297 | ||
298 | @Override | |
299 | public <T extends Edge> Iterator<T> getEdgeIterator() { | |
300 |
1
1. getEdgeIterator : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListGraph::getEdgeIterator to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return new EdgeIterator<T>(); |
301 | } | |
302 | ||
303 | @Override | |
304 | public <T extends Node> Iterator<T> getNodeIterator() { | |
305 |
1
1. getNodeIterator : mutated return of Object value for org/graphstream/graph/implementations/AdjacencyListGraph::getNodeIterator to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return new NodeIterator<T>(); |
306 | } | |
307 | ||
308 | /* | |
309 | * For performance tuning | |
310 | * | |
311 | * @return the number of allocated but unused array elements public int | |
312 | * getUnusedArrayElements() { int count = 0; count += edgeArray.length - | |
313 | * edgeCount; count += nodeArray.length - nodeCount; for (ALNode n : | |
314 | * this.<ALNode> getEachNode()) count += n.edges.length - n.degree; return | |
315 | * count; } | |
316 | */ | |
317 | } | |
Mutations | ||
101 |
1.1 |
|
103 |
1.1 |
|
107 |
1.1 |
|
110 |
1.1 |
|
116 |
1.1 2.2 3.3 |
|
118 |
1.1 2.2 3.3 |
|
156 |
1.1 |
|
157 |
1.1 2.2 |
|
158 |
1.1 |
|
159 |
1.1 |
|
163 |
1.1 2.2 |
|
169 |
1.1 |
|
170 |
1.1 2.2 |
|
171 |
1.1 |
|
172 |
1.1 |
|
176 |
1.1 2.2 |
|
183 |
1.1 |
|
184 |
1.1 |
|
192 |
1.1 |
|
193 |
1.1 |
|
199 |
1.1 |
|
200 |
1.1 |
|
201 |
1.1 |
|
202 |
1.1 |
|
209 |
1.1 |
|
215 |
1.1 2.2 3.3 4.4 |
|
218 |
1.1 |
|
223 |
1.1 |
|
229 |
1.1 |
|
235 |
1.1 2.2 3.3 4.4 |
|
238 |
1.1 |
|
243 |
1.1 |
|
253 |
1.1 2.2 3.3 4.4 |
|
258 |
1.1 2.2 |
|
260 |
1.1 |
|
261 |
1.1 |
|
265 |
1.1 |
|
267 |
1.1 |
|
278 |
1.1 2.2 3.3 4.4 |
|
283 |
1.1 2.2 |
|
285 |
1.1 |
|
286 |
1.1 |
|
290 |
1.1 |
|
292 |
1.1 |
|
300 |
1.1 |
|
305 |
1.1 |