Package dev.nm.graph

Class GraphUtils


  • public final class GraphUtils
    extends Object
    These are the utility functions to manipulate Graph.
    • Method Detail

      • containsVertex

        public static <V> boolean containsVertex​(Graph<V,​?> g,
                                                 V v)
        Returns true if this graph's vertex collection contains v
        Type Parameters:
        V - vertex type
        Parameters:
        g - a graph
        v - the vertex whose presence is being queried
        Returns:
        true if this graph contains the vertex
      • containsEdge

        public static <V> boolean containsEdge​(Graph<V,​?> g,
                                               HyperEdge<V> e)
        Returns true if this graph's edge collection contains e
        Type Parameters:
        V - vertex type
        Parameters:
        g - a graph
        e - the edge whose presence is being queried
        Returns:
        true if this graph contains the edge
      • numberOfEdges

        public static <V> int numberOfEdges​(Graph<V,​?> g)
        Gets the number of edges in this graph.
        Type Parameters:
        V - vertex type
        Parameters:
        g - a graph
        Returns:
        the number of edges in this graph
      • numberOfVertices

        public static <V> int numberOfVertices​(Graph<V,​?> g)
        Gets the number of vertices in this graph.
        Type Parameters:
        V - vertex type
        Parameters:
        g - a graph
        Returns:
        the number of vertices in this graph
      • getNeighbors

        public static <V> Set<V> getNeighbors​(Graph<V,​?> g,
                                              V v)
        Gets the set of vertices which are connected to v via any edges in this graph.
        Type Parameters:
        V - vertex type
        Parameters:
        g - a graph
        v - a vertex
        Returns:
        the neighbors of the vertex
      • getEdges

        public static <V> Set<HyperEdge<V>> getEdges​(Graph<V,​?> g,
                                                     V v1,
                                                     V v2)
        Gets the set of edges that connect the two vertices. Direction is not taken into account.
        Type Parameters:
        V - vertex type
        Parameters:
        g - a graph
        v1 - a vertex
        v2 - a vertex (could be the same as v1)
        Returns:
        the set of edges that connect v1 and v2
      • removeIsolatedVertices

        public static <V,​E extends HyperEdge<V>> Graph<V,​E> removeIsolatedVertices​(Graph<V,​E> g)
        Removes those nodes that have no edges from a graph.
        Type Parameters:
        V - vertex type
        E - edge type
        Parameters:
        g - a graph
        Returns:
        a purged graph
      • addEdges

        public static <V,​E extends HyperEdge<V>> void addEdges​(Graph<V,​E> g,
                                                                     E... edges)
        Add a set of edges to a graph.
        Type Parameters:
        V - vertex type
        E - edge type
        Parameters:
        g - a graph
        edges - edges
      • addVertices

        public static <V> void addVertices​(Graph<V,​?> G,
                                           V... V)
        Add a set of vertices to a graph.
        Type Parameters:
        V - vertex type
        Parameters:
        G - a graph
        V - vertices
      • equals

        public static <V> boolean equals​(Graph<V,​?> g1,
                                         Graph<V,​?> g2)
        Check if two graphs are equal in terms of node values and edges.
        Type Parameters:
        V - vertex type
        Parameters:
        g1 - a graph
        g2 - a graph
        Returns:
        true if the two graphs are equal
      • isAcyclic

        public static <V> boolean isAcyclic​(UnDiGraph<V,​UndirectedEdge<V>> g)
        Check if an undirected graph is acyclic.
        Type Parameters:
        V - vertex type
        Parameters:
        g - an undirected graph
        Returns:
        true if the undirected graph is acyclic
      • isConnected

        public static <V> boolean isConnected​(UnDiGraph<V,​? extends UndirectedEdge<V>> g)
        Check whether an undirected graph is connected.
        Type Parameters:
        V - vertex type
        Parameters:
        g - a graph
        Returns:
        true if an undirected graph is connected
        See Also:
        "http://www.brpreiss.com/books/opus4/html/page561.html"
      • di2UnDiGraph

        public static <V> UnDiGraph<V,​UndirectedEdge<V>> di2UnDiGraph​(DiGraph<V,​? extends Arc<V>> diG)
        Converts a directed graph into an undirected graph by removing the direction of all arcs.
        Type Parameters:
        V - vertex type
        Parameters:
        diG - a directed graph
        Returns:
        an undirected graph
      • getDisjointGraphs

        public static <V,​E extends UndirectedEdge<V>,​G extends UnDiGraph<V,​E>> List<G> getDisjointGraphs​(UnDiGraph<V,​E> g,
                                                                                                                           GraphUtils.GraphFactory<G> gCtor)
        Separate an undirected graph into disjointed connected graphs.
        Type Parameters:
        V - vertex type
        E - edge type
        G - graph type
        Parameters:
        g - an undirected graph
        gCtor - a factory to construct instances of the graph type
        Returns:
        a collection of disjointed connected graphs
      • getParents

        public static <V> Set<V> getParents​(DiGraph<V,​? extends Arc<V>> g,
                                            V v)
        Get the set of vertices that have an outgoing arc pointing to a vertex.
        Type Parameters:
        V - vertex type
        Parameters:
        g - a directed graph
        v - a vertex
        Returns:
        the set of parents/predecessors vertices
      • numberOfParents

        public static <V> int numberOfParents​(DiGraph<V,​? extends Arc<V>> g,
                                              V v)
        Gets the number of parents.
        Type Parameters:
        V - vertex type
        Parameters:
        g - a graph
        v - a vertex
        Returns:
        the number of parents
      • getChildren

        public static <V> Set<V> getChildren​(DiGraph<V,​? extends Arc<V>> g,
                                             V v)
        Get the set of vertices that have an incoming arc coming from a vertex.
        Type Parameters:
        V - vertex type
        Parameters:
        g - a graph
        v - a vertex
        Returns:
        the set of children/successor vertices
      • numberOfChildren

        public static <V> int numberOfChildren​(DiGraph<V,​? extends Arc<V>> g,
                                               V v)
        Gets the number of children.
        Type Parameters:
        V - vertex type
        Parameters:
        g - a graph
        v - a vertex
        Returns:
        the number of children
      • isStronglyConnected

        public static <V> boolean isStronglyConnected​(DiGraph<V,​? extends Arc<V>> g)
        Check whether a directed graph is strongly connected.
        Type Parameters:
        V - vertex type
        Parameters:
        g - a directed graph
        Returns:
        true if a directed graph is strongly connected
        See Also:
        "http://www.brpreiss.com/books/opus4/html/page562.html"
      • unDi2DAGraph

        public static <V,​N,​E extends Arc<N>> DAGraph<N,​E> unDi2DAGraph​(UnDiGraph<V,​? extends UndirectedEdge<V>> g,
                                                                                         V root,
                                                                                         GraphUtils.EdgeFactory<V,​N,​E,​UndirectedEdge<V>> edgeFactory)
        Converts an undirected graph into a directed acyclic graph, arcs are created from the edges by parent-child relations as determined by breadth-first-search. Cyclic, same-depth edges are removed from the graph.
        Type Parameters:
        V - vertex type in the original undirected graph
        N - node type in the new directed acyclic graph
        E - edge type in the new directed acyclic graph
        Parameters:
        g - an (connected) undirected graph
        root - a designated root
        edgeFactory - the method to create an edge in the new directed acyclic graph
        Returns:
        a directed acyclic graph
      • unDi2DAGraph

        public static <V> DAGraph<V,​Arc<V>> unDi2DAGraph​(UnDiGraph<V,​? extends UndirectedEdge<V>> g,
                                                               V root)
        Converts an undirected graph into a directed acyclic graph, arcs are created from the edges by parent-child relations as determined by breadth-first-search. Cyclic, same-depth edges are removed from the graph.
        Type Parameters:
        V - vertex type
        Parameters:
        g - an undirected graph
        root - a designated root
        Returns:
        a directed acyclic graph