Elaboration of DirectedGraph that is capable of identifying strongly connected components and topologically sorting its nodes. More...

Inherits org.lflang.graph.DirectedGraph< T >.

Inherited by org.lflang.generator.ReactionInstanceGraph.

Public Member Functions
void	addEdge (T sink, T source)
	Add a new directed edge to the graph.
void	addEdges (T sink, List< T > sources)
	Add new directed edges to the graph.
void	addNode (T node)
	Add the given node to the graph.
void	clear ()
DirectedGraph< T >	copy ()
	Obtain a copy of this graph by creating an new instance and copying the adjacency maps.
void	detectCycles ()
	Run Tarjan's algorithm for finding strongly connected components.
int	edgeCount ()
	Return the number of directed edges in this graph.
List< Set< T > >	getCycles ()
	Return a list of strongly connected components that exist in this graph.
Set< T >	getDownstreamAdjacentNodes (T node)
	Return all immediate downstream neighbors of a given node.
Set< T >	getUpstreamAdjacentNodes (T node)
	Return all immediate upstream neighbors of a given node.
void	graphChanged ()
	Invalidate cached analysis due to changes in the graph structure.
boolean	hasCycles ()
	Report whether this graph has any cycles in it.
boolean	hasNode (T node)
	Return true if this graph has the given node in it.
Set< T >	leafNodes ()
	Return the leaf nodes of this graph.
void	merge (DirectedGraph< T > another)
	Merge another directed graph into this one.
int	nodeCount ()
	Return the number of nodes in this graph.
Set< T >	nodes ()
	Return an unmodifiable set of nodes in this graph.
List< T >	nodesInReverseTopologicalOrder ()
	Return the nodes of this graph in reverse topological order.
List< T >	nodesInTopologicalOrder ()
	Return the nodes of this graph in reverse topological order.
	PrecedenceGraph ()
	Construct a new dependency graph.
void	removeEdge (T sink, T source)
	Remove a directed edge from the graph.
void	removeNode (T node)
	Remove the given node from the graph.
Set< T >	rootNodes ()
	Return the root nodes of this graph.
void	strongConnect (T node)
	Traverse the graph to visit unvisited dependencies and determine whether they are part of a cycle.
String	toDOT ()
	Return the DOT (GraphViz) representation of the graph.
String	toString ()
	Return a textual list of the nodes.

Protected Attributes
List< Set< T > >	cycles = new ArrayList<>()
	After analysis has completed, this list contains all all sets of nodes that are part of the same strongly connected component.

Detailed Description

Elaboration of DirectedGraph that is capable of identifying strongly connected components and topologically sorting its nodes.

Author: Marten Lohstroh

Constructor & Destructor Documentation

◆ PrecedenceGraph()

org.lflang.graph.PrecedenceGraph< T extends Object >.PrecedenceGraph ( )

Construct a new dependency graph.

Member Function Documentation

◆ addEdge()

void org.lflang.graph.DirectedGraph< T >.addEdge	(	T	sink,
		T	source )

inherited

Add a new directed edge to the graph.

The first argument is the downstream node, the second argument the upstream node. If either argument is null, do nothing.

Parameters

sink	The downstream immediate neighbor.
source	The upstream immediate neighbor.

Implements org.lflang.graph.Graph< T >.

◆ addEdges()

void org.lflang.graph.DirectedGraph< T >.addEdges	(	T	sink,
		List< T >	sources )

inherited

Add new directed edges to the graph.

The first argument is the downstream node, the second argument a set of upstream nodes.

Parameters

sink	The downstream immediate neighbor.
sources	The upstream immediate neighbors.

Implements org.lflang.graph.Graph< T >.

◆ addNode()

void org.lflang.graph.DirectedGraph< T >.addNode ( T node )

inherited

Add the given node to the graph.

Implements org.lflang.graph.Graph< T >.

◆ clear()

void org.lflang.graph.DirectedGraph< T >.clear ( )

inherited

◆ copy()

DirectedGraph< T > org.lflang.graph.DirectedGraph< T >.copy ( )

inherited

Obtain a copy of this graph by creating an new instance and copying the adjacency maps.

◆ detectCycles()

void org.lflang.graph.PrecedenceGraph< T extends Object >.detectCycles ( )

Run Tarjan's algorithm for finding strongly connected components.

After invoking this method, the detected cycles with be listed in the class variable cycles.

◆ edgeCount()

int org.lflang.graph.DirectedGraph< T >.edgeCount ( )

inherited

Return the number of directed edges in this graph.

Implements org.lflang.graph.Graph< T >.

◆ getCycles()

List< Set< T > > org.lflang.graph.PrecedenceGraph< T extends Object >.getCycles ( )

Return a list of strongly connected components that exist in this graph.

◆ getDownstreamAdjacentNodes()

Set< T > org.lflang.graph.DirectedGraph< T >.getDownstreamAdjacentNodes ( T node )

inherited

Return all immediate downstream neighbors of a given node.

Parameters

node	The node to report the immediate downstream neighbors of.

◆ getUpstreamAdjacentNodes()

Set< T > org.lflang.graph.DirectedGraph< T >.getUpstreamAdjacentNodes ( T node )

inherited

Return all immediate upstream neighbors of a given node.

Parameters

node	The node to report the immediate upstream neighbors of.

◆ graphChanged()

void org.lflang.graph.PrecedenceGraph< T extends Object >.graphChanged ( )

Invalidate cached analysis due to changes in the graph structure.

Reimplemented from org.lflang.graph.DirectedGraph< T >.

◆ hasCycles()

boolean org.lflang.graph.PrecedenceGraph< T extends Object >.hasCycles ( )

Report whether this graph has any cycles in it.

◆ hasNode()

boolean org.lflang.graph.DirectedGraph< T >.hasNode ( T node )

inherited

Return true if this graph has the given node in it.

Parameters

node	The node to look for.

Implements org.lflang.graph.Graph< T >.

◆ leafNodes()

Set< T > org.lflang.graph.DirectedGraph< T >.leafNodes ( )

inherited

Return the leaf nodes of this graph.

Leaf nodes have no downstream neighbors.

◆ merge()

void org.lflang.graph.DirectedGraph< T >.merge ( DirectedGraph< T > another )

inherited

Merge another directed graph into this one.

Parameters

another The graph to merge into this one.

◆ nodeCount()

int org.lflang.graph.DirectedGraph< T >.nodeCount ( )

inherited

Return the number of nodes in this graph.

Implements org.lflang.graph.Graph< T >.

◆ nodes()

Set< T > org.lflang.graph.DirectedGraph< T >.nodes ( )

inherited

Return an unmodifiable set of nodes in this graph.

Implements org.lflang.graph.Graph< T >.

◆ nodesInReverseTopologicalOrder()

List< T > org.lflang.graph.PrecedenceGraph< T extends Object >.nodesInReverseTopologicalOrder ( )

Return the nodes of this graph in reverse topological order.

Each node in the returned list is succeeded by the nodes that it depends on.

◆ nodesInTopologicalOrder()

List< T > org.lflang.graph.PrecedenceGraph< T extends Object >.nodesInTopologicalOrder ( )

Return the nodes of this graph in reverse topological order.

Each node in the returned list is preceded by the nodes that it depends on.

◆ removeEdge()

void org.lflang.graph.DirectedGraph< T >.removeEdge	(	T	sink,
		T	source )

inherited

Remove a directed edge from the graph.

Parameters

sink	The downstream immediate neighbor.
source	The upstream immediate neighbor.

Implements org.lflang.graph.Graph< T >.

◆ removeNode()

void org.lflang.graph.DirectedGraph< T >.removeNode ( T node )

inherited

Remove the given node from the graph.

This also eliminates any edges from upstream and to downstream neighbors of this node.

Parameters

node	The node to remove.

Implements org.lflang.graph.Graph< T >.

◆ rootNodes()

Set< T > org.lflang.graph.DirectedGraph< T >.rootNodes ( )

inherited

Return the root nodes of this graph.

Root nodes have no upstream neighbors.

◆ strongConnect()

void org.lflang.graph.PrecedenceGraph< T extends Object >.strongConnect ( T node )

Traverse the graph to visit unvisited dependencies and determine whether they are part of a cycle.

◆ toDOT()

String org.lflang.graph.DirectedGraph< T >.toDOT ( )

inherited

Return the DOT (GraphViz) representation of the graph.

Implements org.lflang.graph.Graph< T >.

Reimplemented in org.lflang.generator.ReactionInstanceGraph.

◆ toString()

String org.lflang.graph.DirectedGraph< T >.toString ( )

inherited

Return a textual list of the nodes.

Member Data Documentation

◆ cycles

List<Set<T> > org.lflang.graph.PrecedenceGraph< T extends Object >.cycles = new ArrayList<>()

protected

After analysis has completed, this list contains all all sets of nodes that are part of the same strongly connected component.

The documentation for this class was generated from the following file:

/Users/runner/work/lingua-franca/lingua-franca/core/src/main/java/org/lflang/graph/PrecedenceGraph.java

Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ PrecedenceGraph()

Member Function Documentation

◆ addEdge()

◆ addEdges()

◆ addNode()

◆ clear()

◆ copy()

◆ detectCycles()

◆ edgeCount()

◆ getCycles()

◆ getDownstreamAdjacentNodes()

◆ getUpstreamAdjacentNodes()

◆ graphChanged()

◆ hasCycles()

◆ hasNode()

◆ leafNodes()

◆ merge()

◆ nodeCount()

◆ nodes()

◆ nodesInReverseTopologicalOrder()

◆ nodesInTopologicalOrder()

◆ removeEdge()

◆ removeNode()

◆ rootNodes()

◆ strongConnect()

◆ toDOT()

◆ toString()

Member Data Documentation

◆ cycles