Package org.goplanit.graph.directed.acyclic

Class UntypedACyclicSubGraphImpl<V extends DirectedVertex,E extends EdgeSegment>

java.lang.Object

org.goplanit.graph.directed.acyclic.UntypedACyclicSubGraphImpl<V,E>

All Implemented Interfaces:

Comparable<IdAble>, Iterable<V>, UntypedACyclicSubGraph<V,E>, DirectedSubGraph<V,E>, IdAble

Direct Known Subclasses:

ACyclicSubGraphImpl, ConjugateACyclicSubGraphImpl

public class UntypedACyclicSubGraphImpl<V extends DirectedVertex,E extends EdgeSegment>
extends Object
implements UntypedACyclicSubGraph<V,E>

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 Summary

Constructors

Constructor	Description
UntypedACyclicSubGraphImpl(UntypedACyclicSubGraphImpl<V,E> other, boolean deepCopy)	Copy constructor
UntypedACyclicSubGraphImpl(IdGroupingToken groupId, Set<V> rootVertices, boolean invertedDirection, int numberOfParentEdgeSegments)	Constructor
UntypedACyclicSubGraphImpl(IdGroupingToken groupId, V rootVertex, boolean invertedDirection, int numberOfParentEdgeSegments)	Constructor

Method Summary

Modifier and Type	Method	Description
void	addEdgeSegment(E edgeSegment)	Register an edge segment on the subgraph
void	addRootVertex(V rootVertex)	Add a new root vertex
boolean	containsEdgeSegment(EdgeSegment edgeSegment)	Verify if given edge segment is registered on this subgraph
UntypedACyclicSubGraphImpl<V,E>	deepClone()	An id entity should always support a deep copy, i.e., all "owned" members will be deep copied when a clone of this instance is created via this call.
long	getId()	Collect id of the entity
long	getNumberOfVertices()	The number of registered vertices.
Set<V>	getRootVertices()	Root vertices of this acyclic graph.
protected org.goplanit.graph.directed.acyclic.AcyclicVertexData	getVertexData(DirectedVertex vertex)	Collect vertex data for given vertex
boolean	isDirectionInverted()	Indicates if the direction of the graph is inverted, i.e., when inverted the root vertex is the final vertex and all other vertices precede it, otherwise it is a starting point and all other vertices succeed it
Iterator<V>	iterator()
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).
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.
void	removeEdgeSegment(E edgeSegment)	Remove an edge segment on the subgraph
UntypedACyclicSubGraphImpl<V,E>	shallowClone()	Create a shallow copy of this entity
Deque<V>	topologicalSort(boolean update)	Perform topological sorting from root, based on Gupta et al.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.goplanit.utils.graph.directed.DirectedSubGraph

getNumberOfEdgeSegments, isEmpty

Methods inherited from interface org.goplanit.utils.id.IdAble

compareTo, idEquals, idHashCode

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface org.goplanit.utils.graph.directed.acyclic.UntypedACyclicSubGraph

getTopologicalIterator, getTopologicalIterator

Constructor Detail

UntypedACyclicSubGraphImpl

public UntypedACyclicSubGraphImpl(IdGroupingToken groupId,
                                  V rootVertex,
                                  boolean invertedDirection,
                                  int numberOfParentEdgeSegments)

Constructor

Parameters:

groupId - generate id based on the group it resides in

rootVertex - of the dag

invertedDirection - when true dag ends at root and all other vertices precede it, when false the root is the starting point and all other vertices succeed it

numberOfParentEdgeSegments - number of directed edge segments of the parent this subgraph is a subset from

UntypedACyclicSubGraphImpl

public UntypedACyclicSubGraphImpl(IdGroupingToken groupId,
                                  Set<V> rootVertices,
                                  boolean invertedDirection,
                                  int numberOfParentEdgeSegments)

Constructor

Parameters:

groupId - generate id based on the group it resides in

rootVertices - the root vertices of the conjugate dag which can be the end or starting point depending whether or not direction is inverted.

invertedDirection - when true dag ends at root and all other vertices precede it, when false the root is the starting point and all other vertices succeed it

numberOfParentEdgeSegments - number of directed edge segments of the parent this subgraph is a subset from

UntypedACyclicSubGraphImpl

public UntypedACyclicSubGraphImpl(UntypedACyclicSubGraphImpl<V,E> other,
                                  boolean deepCopy)

Copy constructor

Parameters:

other - to copy

deepCopy - when true, create a deep copy, shallow copy otherwise

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 Deque<V> topologicalSort(boolean update)

Perform topological sorting from root, based on Gupta et al. 2008.

Specified by:

topologicalSort in interface UntypedACyclicSubGraph<V extends DirectedVertex,E extends EdgeSegment>

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(E edgeSegment)

Register an edge segment on the subgraph

Specified by:

addEdgeSegment in interface DirectedSubGraph<V extends DirectedVertex,E extends EdgeSegment>

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<V extends DirectedVertex,E extends EdgeSegment>

Parameters:

edgeSegment - to verify

Returns:

true when registered, false otherwise

getNumberOfVertices

public long getNumberOfVertices()

The number of registered vertices. This method provides the number of vertices corresponding to these registered edge segments

Specified by:

getNumberOfVertices in interface DirectedSubGraph<V extends DirectedVertex,E extends EdgeSegment>

Returns:

number of vertices

iterator

public Iterator<V> iterator()

Specified by:

iterator in interface Iterable<V extends DirectedVertex>

removeEdgeSegment

public void removeEdgeSegment(E edgeSegment)

Remove an edge segment on the subgraph

Specified by:

removeEdgeSegment in interface DirectedSubGraph<V extends DirectedVertex,E extends EdgeSegment>

Parameters:

edgeSegment - to remove

shallowClone

public UntypedACyclicSubGraphImpl<V,E> shallowClone()

Create a shallow copy of this entity

Specified by:

shallowClone in interface DirectedSubGraph<V extends DirectedVertex,E extends EdgeSegment>

Specified by:

shallowClone in interface IdAble

Specified by:

shallowClone in interface UntypedACyclicSubGraph<V extends DirectedVertex,E extends EdgeSegment>

Returns:

shallow copy of entity

deepClone

public UntypedACyclicSubGraphImpl<V,E> deepClone()

An id entity should always support a deep copy, i.e., all "owned" members will be deep copied when a clone of this instance is created via this call. To be used with caution if not called by managed id container related code

Specified by:

deepClone in interface DirectedSubGraph<V extends DirectedVertex,E extends EdgeSegment>

Specified by:

deepClone in interface IdAble

Specified by:

deepClone in interface UntypedACyclicSubGraph<V extends DirectedVertex,E extends EdgeSegment>

Returns:

deep copy of entity

getRootVertices

public Set<V> getRootVertices()

Root vertices of this acyclic graph. Roots can either be a starting point or end point depending on the direction of the dag

Specified by:

getRootVertices in interface UntypedACyclicSubGraph<V extends DirectedVertex,E extends EdgeSegment>

Returns:

root vertices

isDirectionInverted

public boolean isDirectionInverted()

Indicates if the direction of the graph is inverted, i.e., when inverted the root vertex is the final vertex and all other vertices precede it, otherwise it is a starting point and all other vertices succeed it

Specified by:

isDirectionInverted in interface UntypedACyclicSubGraph<V extends DirectedVertex,E extends EdgeSegment>

Returns:

true when inverted, false otherwise

addRootVertex

public void addRootVertex(V rootVertex)

Add a new root vertex

Specified by:

addRootVertex in interface UntypedACyclicSubGraph<V extends DirectedVertex,E extends EdgeSegment>

Parameters:

rootVertex - to add