1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
/*
* Copyright 2014-2015 Open Networking Laboratory
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.onlab.graph;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
/**
* DFS graph search algorithm implemented via iteration rather than recursion.
*/
public class DepthFirstSearch<V extends Vertex, E extends Edge<V>>
extends AbstractGraphPathSearch<V, E> {
/**
* Graph edge types as classified by the DFS algorithm.
*/
public static enum EdgeType {
TREE_EDGE, FORWARD_EDGE, BACK_EDGE, CROSS_EDGE
}
@Override
public SpanningTreeResult search(Graph<V, E> graph, V src, V dst,
EdgeWeight<V, E> weight, int maxPaths) {
checkArguments(graph, src, dst);
// Prepare the search result.
SpanningTreeResult result = new SpanningTreeResult(src, dst, maxPaths);
// The source vertex has cost 0, of course.
result.updateVertex(src, null, 0.0, true);
// Track finished vertexes and keep a stack of vertexes that have been
// started; start this stack with the source on it.
Set<V> finished = new HashSet<>();
Stack<V> stack = new Stack<>();
stack.push(src);
while (!stack.isEmpty()) {
V vertex = stack.peek();
if (vertex.equals(dst)) {
// If we have reached our destination, bail.
break;
}
double cost = result.cost(vertex);
boolean tangent = false;
// Visit all egress edges of the current vertex.
for (E edge : graph.getEdgesFrom(vertex)) {
// If we have seen the edge already, skip it.
if (result.isEdgeMarked(edge)) {
continue;
}
// Examine the destination of the current edge.
V nextVertex = edge.dst();
if (!result.hasCost(nextVertex)) {
// If this vertex have not finished this vertex yet,
// not started it, then start it as a tree-edge.
result.markEdge(edge, EdgeType.TREE_EDGE);
double newCost = cost + (weight == null ? 1.0 : weight.weight(edge));
result.updateVertex(nextVertex, edge, newCost, true);
stack.push(nextVertex);
tangent = true;
break;
} else if (!finished.contains(nextVertex)) {
// We started the vertex, but did not yet finish it, so
// it must be a back-edge.
result.markEdge(edge, EdgeType.BACK_EDGE);
} else {
// The target has been finished already, so what we have
// here is either a forward-edge or a cross-edge.
result.markEdge(edge, isForwardEdge(result, edge) ?
EdgeType.FORWARD_EDGE : EdgeType.CROSS_EDGE);
}
}
// If we have not been sent on a tangent search and reached the
// end of the current scan normally, mark the node as finished
// and pop it off the vertex stack.
if (!tangent) {
finished.add(vertex);
stack.pop();
}
}
// Finally, but the paths on the search result and return.
result.buildPaths();
return result;
}
/**
* Determines whether the specified edge is a forward edge using the
* accumulated set of parent edges for each vertex.
*
* @param result search result
* @param edge edge to be classified
* @return true if the edge is a forward edge
*/
protected boolean isForwardEdge(DefaultResult result, E edge) {
// Follow the parent edges until we hit the edge source vertex
V target = edge.src();
V vertex = edge.dst();
Set<E> parentEdges;
while ((parentEdges = result.parents.get(vertex)) != null) {
for (E parentEdge : parentEdges) {
vertex = parentEdge.src();
if (vertex.equals(target)) {
return true;
}
}
}
return false;
}
/**
* Graph search result which includes edge classification for building
* a spanning tree.
*/
public class SpanningTreeResult extends DefaultResult {
protected final Map<E, EdgeType> edges = new HashMap<>();
/**
* Creates a new spanning tree result.
*
* @param src search source
* @param dst optional search destination
* @param maxPaths limit on the number of paths
*/
public SpanningTreeResult(V src, V dst, int maxPaths) {
super(src, dst, maxPaths);
}
/**
* Returns the map of edge type.
*
* @return edge to edge type bindings
*/
public Map<E, EdgeType> edges() {
return edges;
}
/**
* Indicates whether or not the edge has been marked with type.
*
* @param edge edge to test
* @return true if the edge has been marked already
*/
boolean isEdgeMarked(E edge) {
return edges.containsKey(edge);
}
/**
* Marks the edge with the specified type.
*
* @param edge edge to mark
* @param type edge type
*/
void markEdge(E edge, EdgeType type) {
edges.put(edge, type);
}
}
}
|
