Class Graph<T>

  • Type Parameters:
    T -

    public class Graph<T>
    extends java.lang.Object
    A directed graph data structure.
    Version:
    $Revision$
    • Field Detail

      • VISIT_COLOR_WHITE

        public static final int VISIT_COLOR_WHITE
        Color used to mark unvisited nodes
        See Also:
        Constant Field Values
      • VISIT_COLOR_GREY

        public static final int VISIT_COLOR_GREY
        Color used to mark nodes as they are first visited in DFS order
        See Also:
        Constant Field Values
      • VISIT_COLOR_BLACK

        public static final int VISIT_COLOR_BLACK
        Color used to mark nodes after descendants are completely visited
        See Also:
        Constant Field Values
      • verticies

        private java.util.Map<java.lang.String,​Vertex<T>> verticies
        Map of graph verticies
      • edges

        private java.util.List<Edge<T>> edges
        Vector of edges in the graph
      • rootVertex

        private Vertex<T> rootVertex
        The vertex identified as the root of the graph
    • Constructor Detail

      • Graph

        public Graph()
        Construct a new graph without any vertices or edges
    • Method Detail

      • isEmpty

        public boolean isEmpty()
        Are there any verticies in the graph
        Returns:
        true if there are no verticies in the graph
      • addVertex

        public boolean addVertex​(Vertex<T> v)
        Add a vertex to the graph
        Parameters:
        v - the Vertex to add
        Returns:
        true if the vertex was added, false if it was already in the graph.
      • size

        public int size()
        Get the vertex count.
        Returns:
        the number of verticies in the graph.
      • getRootVertex

        public Vertex<T> getRootVertex()
        Get the root vertex
        Returns:
        the root vertex if one is set, null if no vertex has been set as the root.
      • setRootVertex

        public void setRootVertex​(Vertex<T> root)
        Set a root vertex. If root does no exist in the graph it is added.
        Parameters:
        root - - the vertex to set as the root and optionally add if it does not exist in the graph.
      • getVertex

        public Vertex<T> getVertex​(int n)
        Get the given Vertex.
        Parameters:
        n - the index [0, size()-1] of the Vertex to access
        Returns:
        the nth Vertex
      • getVerticies

        public java.util.List<Vertex<T>> getVerticies()
        Get the graph verticies
        Returns:
        the graph verticies
      • addEdge

        public boolean addEdge​(Vertex<T> from,
                               Vertex<T> to,
                               int cost)
                        throws java.lang.IllegalArgumentException
        Insert a directed, weighted Edge into the graph.
        Parameters:
        from - - the Edge starting vertex
        to - - the Edge ending vertex
        cost - - the Edge weight/cost
        Returns:
        true if the Edge was added, false if from already has this Edge
        Throws:
        java.lang.IllegalArgumentException - if from/to are not verticies in the graph
      • insertBiEdge

        public boolean insertBiEdge​(Vertex<T> from,
                                    Vertex<T> to,
                                    int cost)
                             throws java.lang.IllegalArgumentException
        Insert a bidirectional Edge in the graph
        Parameters:
        from - - the Edge starting vertex
        to - - the Edge ending vertex
        cost - - the Edge weight/cost
        Returns:
        true if edges between both nodes were added, false otherwise
        Throws:
        java.lang.IllegalArgumentException - if from/to are not verticies in the graph
      • getEdges

        public java.util.List<Edge<T>> getEdges()
        Get the graph edges
        Returns:
        the graph edges
      • removeVertex

        public boolean removeVertex​(Vertex<T> v)
        Remove a vertex from the graph
        Parameters:
        v - the Vertex to remove
        Returns:
        true if the Vertex was removed
      • removeEdge

        public boolean removeEdge​(Vertex<T> from,
                                  Vertex<T> to)
        Remove an Edge from the graph
        Parameters:
        from - - the Edge starting vertex
        to - - the Edge ending vertex
        Returns:
        true if the Edge exists, false otherwise
      • clearMark

        public void clearMark()
        Clear the mark state of all verticies in the graph by calling clearMark() on all verticies.
        See Also:
        Vertex.clearMark()
      • clearEdges

        public void clearEdges()
        Clear the mark state of all edges in the graph by calling clearMark() on all edges.
      • depthFirstSearch

        public void depthFirstSearch​(Vertex<T> v,
                                     Visitor<T> visitor)
        Perform a depth first serach using recursion.
        Parameters:
        v - - the Vertex to start the search from
        visitor - - the vistor to inform prior to
        See Also:
        Visitor.visit(Graph, Vertex)
      • depthFirstSearch

        public <E extends java.lang.Exception> void depthFirstSearch​(Vertex<T> v,
                                                                     VisitorEX<T,​E> visitor)
                                                              throws E extends java.lang.Exception
        Perform a depth first serach using recursion. The search may be cut short if the visitor throws an exception.
        Type Parameters:
        E - exception type
        Parameters:
        v - - the Vertex to start the search from
        visitor - - the vistor to inform prior to
        Throws:
        E - if visitor.visit throws an exception
        E extends java.lang.Exception
        See Also:
        Visitor.visit(Graph, Vertex)
      • breadthFirstSearch

        public void breadthFirstSearch​(Vertex<T> v,
                                       Visitor<T> visitor)
        Perform a breadth first search of this graph, starting at v.
        Parameters:
        v - - the search starting point
        visitor - - the vistor whose vist method is called prior to visting a vertex.
      • breadthFirstSearch

        public <E extends java.lang.Exception> void breadthFirstSearch​(Vertex<T> v,
                                                                       VisitorEX<T,​E> visitor)
                                                                throws E extends java.lang.Exception
        Perform a breadth first search of this graph, starting at v. The vist may be cut short if visitor throws an exception during a vist callback.
        Type Parameters:
        E - exception type
        Parameters:
        v - - the search starting point
        visitor - - the vistor whose vist method is called prior to visting a vertex.
        Throws:
        E - if vistor.visit throws an exception
        E extends java.lang.Exception
      • dfsSpanningTree

        public void dfsSpanningTree​(Vertex<T> v,
                                    DFSVisitor<T> visitor)
        Find the spanning tree using a DFS starting from v.
        Parameters:
        v - - the vertex to start the search from
        visitor - - visitor invoked after each vertex is visited and an edge is added to the tree.
      • findVertexByName

        public Vertex<T> findVertexByName​(java.lang.String name)
        Search the verticies for one with name.
        Parameters:
        name - - the vertex name
        Returns:
        the first vertex with a matching name, null if no matches are found
      • findVertexByData

        public Vertex<T> findVertexByData​(T data,
                                          java.util.Comparator<T> compare)
        Search the verticies for one with data.
        Parameters:
        data - - the vertex data to match
        compare - - the comparator to perform the match
        Returns:
        the first vertex with a matching data, null if no matches are found
      • findCycles

        public Edge<T>[] findCycles()
        Search the graph for cycles. In order to detect cycles, we use a modified depth first search called a colored DFS. All nodes are initially marked white. When a node is encountered, it is marked grey, and when its descendants are completely visited, it is marked black. If a grey node is ever encountered, then there is a cycle.
        Returns:
        the edges that form cycles in the graph. The array will be empty if there are no cycles.
      • visit

        private void visit​(Vertex<T> v,
                           java.util.ArrayList<Edge<T>> cycleEdges)
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object