Package org.jboss.util.graph

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