Analyze dependencies between reaction runtime instances. More...

Inherits org.lflang.graph.PrecedenceGraph< T extends Object >.

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.
int	getBreadth (ReactorInstance enclave)
	Return the max breadth of the reaction dependency 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.
Integer[]	getNumReactionsPerLevel (ReactorInstance enclave)
	Get an array of non-negative integers representing the number of reactions per each level, where levels are indices of the array.
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.
record	MriPortPair (MixedRadixInt index, PortInstance port)
	A port and an index of a reaction relative to the port.
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.
	ReactionInstanceGraph (ReactorInstance main)
	Create a new graph by traversing the maps in the named instances embedded in the hierarchy of the program.
void	rebuildAndAssignDeadlines ()
	Rebuild the graph and propagate and assign deadlines to all reactions.
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.

Public Attributes
final ReactorInstance	main
	The main reactor instance that this graph is associated with.

Protected Member Functions
void	addDownstreamReactions (PortInstance port, ReactionInstance reaction)
	Add to the graph edges between the given reaction and all the reactions that depend on the specified port.
void	addNodesAndEdges (ReactorInstance reactor)
	Build the graph by adding nodes and edges based on the given reactor instance.

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

Analyze dependencies between reaction runtime instances.

For each ReactionInstance, there may be more than one runtime instance because the ReactionInstance may be nested within one or more banks. In the worst case, of these runtime instances may have distinct dependencies, and hence distinct levels in the graph. Moreover, some of these instances may be involved in cycles while others are not.

Upon construction of this class, the runtime instances are created if necessary, stored in each ReactionInstance, and assigned levels (maximum number of upstream reaction instances), deadlines, and single dominating reactions.

After creation, the resulting graph will be empty unless there are causality cycles, in which case, the resulting graph is a graph of runtime reaction instances that form cycles.

Author: Marten Lohstroh; Edward A. Lee

Constructor & Destructor Documentation

◆ ReactionInstanceGraph()

org.lflang.generator.ReactionInstanceGraph.ReactionInstanceGraph ( ReactorInstance main )

Create a new graph by traversing the maps in the named instances embedded in the hierarchy of the program.

Member Function Documentation

◆ addDownstreamReactions()

void org.lflang.generator.ReactionInstanceGraph.addDownstreamReactions	(	PortInstance	port,
		ReactionInstance	reaction )

protected

Add to the graph edges between the given reaction and all the reactions that depend on the specified port.

Parameters

port	The port that the given reaction has as an effect.
reaction	The reaction to relate downstream reactions to.

◆ 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 >.

◆ addNodesAndEdges()

void org.lflang.generator.ReactionInstanceGraph.addNodesAndEdges ( ReactorInstance reactor )

protected

Build the graph by adding nodes and edges based on the given reactor instance.

Parameters

reactor The reactor on the basis of which to add nodes and edges.

◆ 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 ( )

inherited

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 >.

◆ getBreadth()

int org.lflang.generator.ReactionInstanceGraph.getBreadth ( ReactorInstance enclave )

Return the max breadth of the reaction dependency graph.

Parameters

enclave The enclave to get the breadth for.

Returns: The max breadth of the reaction dependency graph.

◆ getCycles()

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

inherited

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.

◆ getNumReactionsPerLevel()

Integer[] org.lflang.generator.ReactionInstanceGraph.getNumReactionsPerLevel ( ReactorInstance enclave )

Get an array of non-negative integers representing the number of reactions per each level, where levels are indices of the array.

Parameters

enclave The enclave to get the number of reactions for.

Returns: An array of non-negative integers representing the number of reactions per each level, where levels are indices of the array, or an empty array if the enclave has no reactions.

◆ 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 ( )

inherited

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

inherited

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.

◆ MriPortPair()

record org.lflang.generator.ReactionInstanceGraph.MriPortPair	(	MixedRadixInt	index,
		PortInstance	port )

A port and an index of a reaction relative to the port.

◆ 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 ( )

inherited

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

inherited

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.

◆ rebuildAndAssignDeadlines()

void org.lflang.generator.ReactionInstanceGraph.rebuildAndAssignDeadlines ( )

Rebuild the graph and propagate and assign deadlines to all reactions.

◆ 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 )

inherited

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

◆ toDOT()

String org.lflang.generator.ReactionInstanceGraph.toDOT ( )

Return the DOT (GraphViz) representation of the graph.

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

◆ 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<>()

protectedinherited

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

◆ main

final ReactorInstance org.lflang.generator.ReactionInstanceGraph.main

The main reactor instance that this graph is associated with.

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

/Users/runner/work/lingua-franca/lingua-franca/core/src/main/java/org/lflang/generator/ReactionInstanceGraph.java

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ReactionInstanceGraph()

Member Function Documentation

◆ addDownstreamReactions()

◆ addEdge()

◆ addEdges()

◆ addNode()

◆ addNodesAndEdges()

◆ clear()

◆ copy()

◆ detectCycles()

◆ edgeCount()

◆ getBreadth()

◆ getCycles()

◆ getDownstreamAdjacentNodes()

◆ getNumReactionsPerLevel()

◆ getUpstreamAdjacentNodes()

◆ graphChanged()

◆ hasCycles()

◆ hasNode()

◆ leafNodes()

◆ merge()

◆ MriPortPair()

◆ nodeCount()

◆ nodes()

◆ nodesInReverseTopologicalOrder()

◆ nodesInTopologicalOrder()

◆ rebuildAndAssignDeadlines()

◆ removeEdge()

◆ removeNode()

◆ rootNodes()

◆ strongConnect()

◆ toDOT()

◆ toString()

Member Data Documentation

◆ cycles

◆ main