Class SparseDAGraph<V,​E extends Arc<V>>

  • Type Parameters:
    V - vertex type
    E - arc type
    All Implemented Interfaces:
    DAGraph<V,​E>, DiGraph<V,​E>, Graph<V,​E>

    public class SparseDAGraph<V,​E extends Arc<V>>
    extends SparseDiGraph<V,​E>
    implements DAGraph<V,​E>
    This class implements the sparse directed acyclic graph representation.
    • Constructor Detail

      • SparseDAGraph

        public SparseDAGraph​(boolean toCheckCyclicity)
        Construct an empty directed acyclic graph.
        Parameters:
        toCheckCyclicity - true if to check cyclicity each time an edge is added (slow performance)
      • SparseDAGraph

        public SparseDAGraph()
        Construct an empty directed acyclic graph.
      • SparseDAGraph

        public SparseDAGraph​(DAGraph<V,​E> g)
        (Copy) construct a directed acyclic graph from another directed acyclic graph.
        Parameters:
        g - a graph
    • Method Detail

      • addEdge

        public SparseDAGraph<V,​E> addEdge​(E e)
        Description copied from interface: Graph
        Adds an edge to this graph. Does nothing if e is already in the graph. If the edge contains new vertices, those will be added to the graph.
        Specified by:
        addEdge in interface Graph<V,​E extends Arc<V>>
        Overrides:
        addEdge in class SparseGraph<V,​E extends Arc<V>>
        Parameters:
        e - the edge to add
        Returns:
        this graph (for builder pattern)
      • topologicalOrder

        public int topologicalOrder​(V v)
        Description copied from interface: DAGraph
        Get the topological order of a vertex.
        Specified by:
        topologicalOrder in interface DAGraph<V,​E extends Arc<V>>
        Parameters:
        v - a vertex
        Returns:
        the topological order of a vertex
      • isAcyclic

        public boolean isAcyclic()
        Runs validity check to ensure that this DA graph is indeed acyclic.
        Returns:
        true if this graph is acyclic