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 DepthFirstIterator<T extends Node> implements Iterator<T> { | |
38 | boolean directed; | |
39 | Graph graph; | |
40 | ||
41 | Node[] parent; | |
42 | Iterator<Edge>[] iterator; | |
43 | int depth[]; | |
44 | Node next; | |
45 | int maxDepth; | |
46 | ||
47 | @SuppressWarnings("unchecked") | |
48 | public DepthFirstIterator(Node startNode, boolean directed) { | |
49 | this.directed = directed; | |
50 | graph = startNode.getGraph(); | |
51 | int n = graph.getNodeCount(); | |
52 | parent = new Node[n]; | |
53 | iterator = new Iterator[n]; | |
54 | depth = new int[n]; | |
55 | ||
56 | int s = startNode.getIndex(); | |
57 |
3
1. 2. 3. |
for (int i = 0; i < n; i++) |
58 |
1
1. |
depth[i] = i == s ? 0 : -1; |
59 | next = startNode; | |
60 | } | |
61 | ||
62 | protected void gotoNext() { | |
63 |
1
1. gotoNext : negated conditional → NO_COVERAGE |
while (next != null) { |
64 | int i = next.getIndex(); | |
65 |
1
1. gotoNext : negated conditional → NO_COVERAGE |
while (iterator[i].hasNext()) { |
66 | Node neighbor = iterator[i].next().getOpposite(next); | |
67 | int j = neighbor.getIndex(); | |
68 |
1
1. gotoNext : negated conditional → NO_COVERAGE |
if (iterator[j] == null) { |
69 | parent[j] = next; | |
70 |
1
1. gotoNext : negated conditional → NO_COVERAGE |
iterator[j] = directed ? neighbor.getLeavingEdgeIterator() |
71 | : neighbor.getEnteringEdgeIterator(); | |
72 |
1
1. gotoNext : Replaced integer addition with subtraction → NO_COVERAGE |
depth[j] = depth[i] + 1; |
73 |
2
1. gotoNext : changed conditional boundary → NO_COVERAGE 2. gotoNext : negated conditional → NO_COVERAGE |
if (depth[j] > maxDepth) |
74 | maxDepth = depth[j]; | |
75 | next = neighbor; | |
76 | return; | |
77 | } | |
78 | } | |
79 | next = parent[i]; | |
80 | } | |
81 | } | |
82 | ||
83 | public DepthFirstIterator(Node startNode) { | |
84 | this(startNode, true); | |
85 | } | |
86 | ||
87 | public boolean hasNext() { | |
88 |
3
1. hasNext : negated conditional → NO_COVERAGE 2. hasNext : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE 3. hasNext : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return next != null; |
89 | } | |
90 | ||
91 | @SuppressWarnings("unchecked") | |
92 | public T next() { | |
93 |
1
1. next : negated conditional → NO_COVERAGE |
if (next == null) |
94 | throw new NoSuchElementException(); | |
95 |
1
1. next : negated conditional → NO_COVERAGE |
iterator[next.getIndex()] = directed ? next.getLeavingEdgeIterator() |
96 | : next.getEnteringEdgeIterator(); | |
97 | Node previous = next; | |
98 |
1
1. next : removed call to org/graphstream/graph/DepthFirstIterator::gotoNext → NO_COVERAGE |
gotoNext(); |
99 |
1
1. next : mutated return of Object value for org/graphstream/graph/DepthFirstIterator::next to ( if (x != null) null else throw new RuntimeException ) → NO_COVERAGE |
return (T) previous; |
100 | } | |
101 | ||
102 | public void remove() { | |
103 | throw new UnsupportedOperationException( | |
104 | "This iterator does not support remove"); | |
105 | } | |
106 | ||
107 | public int getDepthOf(Node node) { | |
108 |
1
1. getDepthOf : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return depth[node.getIndex()]; |
109 | } | |
110 | ||
111 | public int getDepthMax() { | |
112 |
1
1. getDepthMax : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return maxDepth; |
113 | } | |
114 | ||
115 | public boolean tabu(Node node) { | |
116 |
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; |
117 | } | |
118 | ||
119 | public boolean isDirected() { | |
120 |
1
1. isDirected : replaced return of integer sized value with (x == 0 ? 1 : 0) → NO_COVERAGE |
return directed; |
121 | } | |
122 | } | |
Mutations | ||
57 |
1.1 2.2 3.3 |
|
58 |
1.1 |
|
63 |
1.1 |
|
65 |
1.1 |
|
68 |
1.1 |
|
70 |
1.1 |
|
72 |
1.1 |
|
73 |
1.1 2.2 |
|
88 |
1.1 2.2 3.3 |
|
93 |
1.1 |
|
95 |
1.1 |
|
98 |
1.1 |
|
99 |
1.1 |
|
108 |
1.1 |
|
112 |
1.1 |
|
116 |
1.1 2.2 3.3 |
|
120 |
1.1 |