Package org.goplanit.graph.directed.acyclic

Class ACyclicSubGraphImpl

  • All Implemented Interfaces:
    Cloneable, Comparable<IdAble>, Iterable<DirectedVertex>, ACyclicSubGraph, DirectedSubGraph, IdAble
    public class ACyclicSubGraphImpl
extends Object
implements ACyclicSubGraph
    An acyclic sub graph contains a subset of the full graph without cycles. The active subset of the graph is tracked by explicitly registering edge segments. Edge segments are by definition directed. Whenever edge segments are added it is verified that no cycles are created. Also each edge segment that is added must connect to the existing subgraph's contents
    Author:
    markr

    • Constructor Detail

      • ACyclicSubGraphImpl

        public ACyclicSubGraphImpl​(IdGroupingToken groupId,
                           int numberOfParentEdgeSegments,
                           DirectedVertex root)
        Constructor
        Parameters:
        groupId - generate id based on the group it resides in
        numberOfParentEdgeSegments - number of directed edge segments of the parent this subgraph is a subset from
        root - (initial) root of the subgraph

      • ACyclicSubGraphImpl

        public ACyclicSubGraphImpl​(ACyclicSubGraphImpl aCyclicSubGraphImpl)
        Copy constructor
        Parameters:
        aCyclicSubGraphImpl - to copy

    • Method Detail

      • postVisit

        protected void postVisit​(org.goplanit.graph.directed.acyclic.AcyclicVertexData vertexData,
                         LongAdder counter)
        While traversing the graph recursively, postVisit is invoked AFTER exploring a vertex (successfully). In this implementation, the preVisit simply increments the counter and updates the postVisit variable on the vertex data. See also Gupta et al. 2008
        Parameters:
        vertexData - data of the vertex
        counter - track the progress of traversing the graph, increment by one

      • preVisit

        protected void preVisit​(org.goplanit.graph.directed.acyclic.AcyclicVertexData vertexData,
                        LongAdder counter)
        While traversing the graph recursively, preVisit is invoked BEFORE exploring a vertex further. In this implementation, the preVisit simply increments the counter and updates the preVisit variable on the vertex data. See also Gupta et al. 2008
        Parameters:
        vertexData - data of the vertex
        counter - track the progress of traversing the graph, increment by one

      • getVertexData

        protected org.goplanit.graph.directed.acyclic.AcyclicVertexData getVertexData​(DirectedVertex vertex)
        Collect vertex data for given vertex
        Parameters:
        vertex - to collect for
        Returns:
        vertex data

      • topologicalSort

        public Collection<DirectedVertex> topologicalSort​(boolean update)
        Perform topological sorting from root, based on Gupta et al. 2008.
        Specified by:
        topologicalSort in interface ACyclicSubGraph
        Parameters:
        update - when true we force an update, when false we return the most recent result without performing an update (if any exist)
        Returns:
        Topologically sorted list of vertices, null when graph is not acyclic, or disconnected

      • getId

        public long getId()
        Collect id of the entity
        Specified by:
        getId in interface IdAble
        Returns:
        id found

      • addEdgeSegment

        public void addEdgeSegment​(EdgeSegment edgeSegment)
        Register an edge segment on the subgraph
        Specified by:
        addEdgeSegment in interface DirectedSubGraph
        Parameters:
        edgeSegment - to add

      • containsEdgeSegment

        public boolean containsEdgeSegment​(EdgeSegment edgeSegment)
        Verify if given edge segment is registered on this subgraph
        Specified by:
        containsEdgeSegment in interface DirectedSubGraph
        Parameters:
        edgeSegment - to verify
        Returns:
        true when registered, false otherwise

      • getNumberOfVertices

        public long getNumberOfVertices()
        Based on the registered edge segments, the number of vertices is automatically determined. This method provides the number of vertices corresponding to these registered edge segments
        Specified by:
        getNumberOfVertices in interface DirectedSubGraph
        Returns:
        number of vertices