/** * Not discovered node */ private static final int FRESH = 0; /** * Open node */ private static final int OPEN = 1; /** * Closed node */ private static final int CLOSED = 2; /** * Recursive form of depth-first search * * @param graph */ public static void depthFirstSearch(GraphIface graph) { //node states int[] state = new int[graph.getVertexCount()]; for (int i = 0; i < state.length; i++) { state[i] = FRESH; } //perform depth first search of all connected components for (int i = 0; i < graph.getVertexCount(); i++) { if (state[i] == FRESH) { doDFS(graph, i, state); } } } /** * Perform depth-first search * * @param graph graph * @param vertexNr node identifier * @param state array of node states */ private static void doDFS(GraphIface graph, int vertexNr, int[] state) { state[vertexNr] = OPEN; List<GraphNodeIface> succ = graph.getNode(vertexNr).getSuccessors(); for (GraphNodeIface n : succ) { if (state[n.getId()] == FRESH) { doDFS(graph, n.getId(), state); } } state[vertexNr] = CLOSED; } /** * Defines basic interface for a generic graph * * @author Pavel Micka */ public interface GraphIface<ENTITY> { /** * Add an edge to a graph * * @param from source node * @param to target node */ public void addEdge(int from, int to); /** * Get number of edges in the graph * * @return number of edges in the graph */ public int getEdgeCount(); /** * Return vertex (node) with the given identifier * * @param id * @return */ public GraphNodeIface getNode(int id); /** * Return total number of nodes (vertices) * * @return total number of nodes (vertices) */ public int getVertexCount(); /** * Remove the edge * * @param from source node * @param to target node */ public void removeEdge(int from, int to); /** * Defines basic interface for a node of a graph * * @param <ENTITY> */ public interface GraphNodeIfac<ENTITY> { /** * @return the id */ public int getId(); /** * @return the successors */ public List<GraphNodeIface> getSuccessors(); /** * @return the value */ public ENTITY getValue(); /** * @param value the value to set */ public void setValue(ENTITY value); } }