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; | |
33 | ||
34 | import java.util.Iterator; | |
35 | import java.util.NoSuchElementException; | |
36 | ||
37 | public class BreadthFirstIterator<T extends Node> implements Iterator<T> { | |
38 | protected boolean directed; | |
39 | protected Graph graph; | |
40 | protected Node[] queue; | |
41 | protected int[] depth; | |
42 | protected int qHead, qTail; | |
43 | ||
44 | public BreadthFirstIterator(Node startNode, boolean directed) { | |
45 | this.directed = directed; | |
46 | graph = startNode.getGraph(); | |
47 | int n = graph.getNodeCount(); | |
48 | queue = new Node[n]; | |
49 | depth = new int[n]; | |
50 | ||
51 | int s = startNode.getIndex(); | |
52 |
3
1. 2. 3. |
for (int i = 0; i < n; i++) |
53 |
1
1. |
depth[i] = i == s ? 0 : -1; |
54 | queue[0] = startNode; | |
55 | qHead = 0; | |
56 | qTail = 1; | |
57 | } | |
58 | ||
59 | public BreadthFirstIterator(Node startNode) { | |
60 | this(startNode, true); | |
61 | } | |
62 | ||
63 | public boolean hasNext() { | |
64 |
4
1. hasNext : changed conditional boundary → NO_COVERAGE 2. hasNext : negated conditional → NO_COVERAGE 3. hasNext : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE 4. hasNext : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return qHead < qTail; |
65 | } | |
66 | ||
67 | @SuppressWarnings("unchecked") | |
68 | public T next() { | |
69 |
2
1. next : changed conditional boundary → NO_COVERAGE 2. next : negated conditional → NO_COVERAGE |
if (qHead >= qTail) |
70 | throw new NoSuchElementException(); | |
71 |
1
1. next : Replaced integer addition with subtraction → NO_COVERAGE |
Node current = queue[qHead++]; |
72 |
1
1. next : Replaced integer addition with subtraction → NO_COVERAGE |
int level = depth[current.getIndex()] + 1; |
73 |
1
1. next : negated conditional → NO_COVERAGE |
Iterable<Edge> edges = directed ? current.getEachLeavingEdge() |
74 | : current.getEachEdge(); | |
75 |
1
1. next : negated conditional → NO_COVERAGE |
for (Edge e : edges) { |
76 | Node node = e.getOpposite(current); | |
77 | int j = node.getIndex(); | |
78 |
1
1. next : negated conditional → NO_COVERAGE |
if (depth[j] == -1) { |
79 |
1
1. next : Replaced integer addition with subtraction → NO_COVERAGE |
queue[qTail++] = node; |
80 | depth[j] = level; | |
81 | } | |
82 | } | |
83 |
1
1. next : mutated return of Object value for org/graphstream/graph/BreadthFirstIterator::next to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return (T)current; |
84 | } | |
85 | ||
86 | public void remove() { | |
87 | throw new UnsupportedOperationException( | |
88 | "This iterator does not support remove"); | |
89 | } | |
90 | ||
91 | public int getDepthOf(Node node) { | |
92 |
1
1. getDepthOf : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return depth[node.getIndex()]; |
93 | } | |
94 | ||
95 | public int getDepthMax() { | |
96 |
2
1. getDepthMax : Replaced integer subtraction with addition → NO_COVERAGE 2. getDepthMax : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return depth[queue[qTail - 1].getIndex()]; |
97 | } | |
98 | ||
99 | public boolean tabu(Node node) { | |
100 |
3
1. tabu : negated conditional → NO_COVERAGE 2. tabu : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE 3. tabu : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return depth[node.getIndex()] != -1; |
101 | } | |
102 | ||
103 | public boolean isDirected() { | |
104 |
1
1. isDirected : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return directed; |
105 | } | |
106 | } | |
Mutations | ||
52 |
1.1 2.2 3.3 |
|
53 |
1.1 |
|
64 |
1.1 2.2 3.3 4.4 |
|
69 |
1.1 2.2 |
|
71 |
1.1 |
|
72 |
1.1 |
|
73 |
1.1 |
|
75 |
1.1 |
|
78 |
1.1 |
|
79 |
1.1 |
|
83 |
1.1 |
|
92 |
1.1 |
|
96 |
1.1 2.2 |
|
100 |
1.1 2.2 3.3 |
|
104 |
1.1 |