/**
     * 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);
        }
    }