Description

A directed acyclic graph (DAG) data structure with informative error reporting for cycles.

Definition at line 17 of file VuoDirectedAcyclicGraph.hh.

Classes
class	Vertex
	Abstract base class for the items contained in the DAG. More...

Public Member Functions
	VuoDirectedAcyclicGraph (void)
	Constructs an empty graph. More...

	~VuoDirectedAcyclicGraph (void)
	Destroys all vertex instances in the graph. More...

void	addVertex (Vertex *vertex)
	Adds a vertex to the graph. More...

void	removeVertex (Vertex *vertex)
	Removes a vertex and all of its incoming and outgoing edges from the graph. More...

Vertex *	findVertex (const string &key)
	Finds the vertex in the graph whose Vertex::key function returns key, or null if there is no such vertex. More...

void	addEdge (Vertex fromVertex, Vertex toVertex)
	Adds a directed edge to the graph. More...

vector< Vertex * >	getDownstreamVertices (Vertex *vertex)
	Returns all vertices that can be reached from vertex via a path of directed edges. More...

vector< Vertex * >	getUpstreamVertices (Vertex *vertex)
	Returns all vertices that can reach vertex via a path of directed edges. More...

set< Vertex * >	getCycleVertices (void)
	Returns any vertices that are part of a cycle (making this not actually a directed acyclic graph). More...

int	getLongestDownstreamPath (Vertex *vertex)
	Returns the number of vertices in the longest path downstream of vertex (not counting vertex itself). More...

string	toString (bool showVertexAddresses=false)
	For debugging. More...

Friends
class	VuoDirectedAcyclicNetwork

Constructor & Destructor Documentation

◆ VuoDirectedAcyclicGraph()

VuoDirectedAcyclicGraph::VuoDirectedAcyclicGraph ( void )

Constructs an empty graph.

Definition at line 20 of file VuoDirectedAcyclicGraph.cc.

◆ ~VuoDirectedAcyclicGraph()

VuoDirectedAcyclicGraph::~VuoDirectedAcyclicGraph ( void )

Destroys all vertex instances in the graph.

Definition at line 28 of file VuoDirectedAcyclicGraph.cc.

Member Function Documentation

◆ addEdge()

void VuoDirectedAcyclicGraph::addEdge	(	Vertex *	fromVertex,
		Vertex *	toVertex
	)

Adds a directed edge to the graph.

The addVertex function can be called first on each vertex but doesn't have to be. The graph takes ownership of the vertex objects and is responsible for destroying them.

If this function is called multiple times for the same edge endpoints, the edge is only added once.

Definition at line 100 of file VuoDirectedAcyclicGraph.cc.

◆ addVertex()

void VuoDirectedAcyclicGraph::addVertex ( Vertex * vertex )

Adds a vertex to the graph.

The graph takes ownership of the vertex object and is responsible for destroying it.

If this function is called multiple times for the same vertex object, the vertex is only added once.

Definition at line 39 of file VuoDirectedAcyclicGraph.cc.

◆ findVertex()

VuoDirectedAcyclicGraph::Vertex * VuoDirectedAcyclicGraph::findVertex ( const string & key )

Finds the vertex in the graph whose Vertex::key function returns key, or null if there is no such vertex.

Definition at line 83 of file VuoDirectedAcyclicGraph.cc.

◆ getCycleVertices()

set< VuoDirectedAcyclicGraph::Vertex * > VuoDirectedAcyclicGraph::getCycleVertices ( void )

Returns any vertices that are part of a cycle (making this not actually a directed acyclic graph).

Definition at line 181 of file VuoDirectedAcyclicGraph.cc.

◆ getDownstreamVertices()

vector< VuoDirectedAcyclicGraph::Vertex * > VuoDirectedAcyclicGraph::getDownstreamVertices ( Vertex * vertex )

Returns all vertices that can be reached from vertex via a path of directed edges.

The returned vertices are not in any particular order. In the future, this function may be modified to return them in topological order.

Definition at line 122 of file VuoDirectedAcyclicGraph.cc.

◆ getLongestDownstreamPath()

int VuoDirectedAcyclicGraph::getLongestDownstreamPath ( Vertex * vertex )

Returns the number of vertices in the longest path downstream of vertex (not counting vertex itself).

Definition at line 205 of file VuoDirectedAcyclicGraph.cc.

◆ getUpstreamVertices()

vector< VuoDirectedAcyclicGraph::Vertex * > VuoDirectedAcyclicGraph::getUpstreamVertices ( Vertex * vertex )

Returns all vertices that can reach vertex via a path of directed edges.

The returned vertices are not in any particular order. In the future, this function may be modified to return them in topological order.

Definition at line 152 of file VuoDirectedAcyclicGraph.cc.

◆ removeVertex()

void VuoDirectedAcyclicGraph::removeVertex ( Vertex * vertex )

Removes a vertex and all of its incoming and outgoing edges from the graph.

Definition at line 49 of file VuoDirectedAcyclicGraph.cc.

◆ toString()

string VuoDirectedAcyclicGraph::toString ( bool showVertexAddresses = false )

For debugging.

Definition at line 299 of file VuoDirectedAcyclicGraph.cc.

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

compiler/VuoDirectedAcyclicGraph.hh
compiler/VuoDirectedAcyclicGraph.cc