132 lines
2.6 KiB
Java
132 lines
2.6 KiB
Java
|
|
//gioel
|
|
|
|
package graph;
|
|
|
|
|
|
import arraylist.ArrayIndexList;
|
|
import arraylist.IndexList;
|
|
import position.NodePositionList;
|
|
import position.PositionList;
|
|
|
|
import exceptions.InvalidKeyException;
|
|
|
|
public abstract class BFS<V, E, I, R> {
|
|
protected Graph<V, E> graph;
|
|
protected Vertex<V> start;
|
|
protected I info;
|
|
protected R visitResult;
|
|
protected static Object STATUS = new Object();
|
|
protected static Object VISITED = new Object();
|
|
protected static Object UNVISITED = new Object();
|
|
|
|
protected IndexList<PositionList<Vertex<V>>> layers;
|
|
|
|
public R execute(Graph<V, E> g, Vertex<V> s, I in) throws InvalidKeyException{
|
|
graph = g;
|
|
layers = new ArrayIndexList<PositionList<Vertex<V>>>(
|
|
graph.numVertices());
|
|
start = s;
|
|
info = in;
|
|
for (Vertex<V> v : graph.vertices())
|
|
unVisit(v);
|
|
for (Edge<E> e : graph.edges())
|
|
unVisit(e);
|
|
|
|
setup();
|
|
return finalResult(bfsTraversal(start));
|
|
}
|
|
|
|
protected void setup() {
|
|
}
|
|
|
|
protected R bfsTraversal(Vertex<V> v) throws InvalidKeyException{
|
|
initResult();
|
|
if (!isDone())
|
|
startVisit(v);
|
|
|
|
if (!isDone()) {
|
|
visit(v);
|
|
|
|
layers.add(0, new NodePositionList<Vertex<V>>());
|
|
layers.get(0).addLast(v);
|
|
}
|
|
|
|
int i = 0;
|
|
while (!layers.get(i).isEmpty()) {
|
|
layers.add(i + 1, new NodePositionList<Vertex<V>>());
|
|
|
|
for (Vertex<V> vertexInLayer : layers.get(i)) {
|
|
for (Edge<E> e : graph.incidentEdges(vertexInLayer)) {
|
|
if (!isVisited(e)) {
|
|
visit(e);
|
|
Vertex<V> w = graph.opposite(vertexInLayer, e);
|
|
if (!isVisited(w)) {
|
|
traverseDiscovery(e, vertexInLayer);
|
|
|
|
if (isDone())
|
|
break;
|
|
|
|
visit(w);
|
|
layers.get(i + 1).addLast(w);
|
|
|
|
if (isDone())
|
|
break;
|
|
} else {
|
|
traverseCross(e, v);
|
|
if (isDone())
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (!isDone())
|
|
finishVisit(vertexInLayer);
|
|
}
|
|
|
|
i++;
|
|
}
|
|
|
|
return result();
|
|
}
|
|
|
|
protected void initResult() {
|
|
}
|
|
|
|
protected void startVisit(Vertex<V> v) {
|
|
}
|
|
|
|
protected void traverseCross(Edge<E> e, Vertex<V> v) {
|
|
}
|
|
|
|
protected void traverseDiscovery(Edge<E> e, Vertex<V> v) {
|
|
}
|
|
|
|
protected void finishVisit(Vertex<V> v) {
|
|
}
|
|
|
|
protected boolean isDone() {
|
|
return false;
|
|
}
|
|
|
|
protected R result() {
|
|
return null;
|
|
}
|
|
|
|
protected R finalResult(R r) {
|
|
return null;
|
|
}
|
|
|
|
protected void visit(DecorablePosition<?> p) throws InvalidKeyException{
|
|
p.put(STATUS, VISITED);
|
|
}
|
|
|
|
protected void unVisit(DecorablePosition<?> p) throws InvalidKeyException {
|
|
p.put(STATUS, UNVISITED);
|
|
}
|
|
|
|
protected boolean isVisited(DecorablePosition<?> p) throws InvalidKeyException {
|
|
return p.get(STATUS) == VISITED;
|
|
}
|
|
}
|