A graph that models the dependencies between a set of objects of type VertexT. More...

#include <DependencyGraph.hpp>

Classes
class	const_iterator
	The DependencyGraph const iterator. More...

class	iterator
	The DependencyGraph non-const iterator. More...

Public Member Functions
void	addDependency (const VertexT &dependency, bool throwIfExists=true)
	Add a dependency. More...

void	addRelationship (const VertexT &independent, const VertexT &dependent)
	Add a dependency relationship between two existing dependencies. More...

void	addRelationship (const VertexT &independent, const VertexT &dependent, const EdgeT &edgeData)
	Add a dependency relationship between two existing dependencies, with edge data. More...

iterator	begin ()
	Get an iterator positioned at the beginning of the dependency graph. More...

const_iterator	begin () const
	Get a const iterator positioned at the beginning of the dependency graph. More...

std::vector< VertexT >	dependencyOrder () const
	Calculate the dependency order of the dependencies. More...

std::vector< VertexT >	directDependenciesOf (const VertexT &dependency) const
	What are the direct dependencies of the specified dependency. More...

iterator	end ()
	Get an iterator positioned at the end of the dependency graph. More...

const_iterator	end () const
	Get a const iterator positioned at the end of the dependency graph. More...

bool	hasCycles () const
	Does the dependency graph have any cycles? More...

bool	hasCycles (std::vector< std::pair< VertexT, VertexT >> &cycleEdges) const
	Does the dependency graph have any cycles? More...

bool	hasDependency (const VertexT &dependency) const
	Does the graph have the specified dependency? More...

void	logGraph (LoggingLevel level, const char *title)
	Log the dependency tree to the "balau.container" logger if the logger is enabled for the supplied logging level. More...

const VertexT *	lookupDependency (const VertexT &key) const
	Lookups up the dependency that matches the supplied candidate object. More...

std::vector< std::vector< VertexT > >	parallelDependencyOrder () const
	Calculate the parallel dependency order of the dependencies. More...

void	removeDependency (const VertexT &dependency, bool throwIfNotExists=true)
	Remove a dependency. More...

void	removeRelationship (const VertexT &independent, const VertexT &dependent)
	Remove a dependency relationship between two existing dependencies. More...

Detailed Description

template<typename VertexT = boost::no_property, typename EdgeT = boost::no_property, typename GraphT = boost::no_property>
class Balau::Container::DependencyGraph< VertexT, EdgeT, GraphT >

A graph that models the dependencies between a set of objects of type VertexT.

The dependency graph provides information on:

the direct dependencies of nodes;
the dependency order of the set of nodes;
the parallel dependency order of the set of nodes;
whether the dependency tree has any cycles.

The type VertexT is usually defined to be an arbitrary type, but it may also be a Boost property list if vertex property lists are required.

In addition to vertex objects, edge data may also be attached to the edges of the graph if required. In order to do this, the additional optional type EdgeT should be defined.

Finally, a single graph data object may also be attached to the graph if required. This allows a bundle of data to be closely associated with the graph, without requiring the developer to define a custom class containing the bundle and the graph itself. In order attach a single object to the graph, the additional optional type GraphT should be defined.

This class was initially conceived to support the injector, but may be used for any set of dependencies by creating the appropriate object type VertexT.

As two copies of the objects of type VertexT are maintained in the dependency graph class, the type VertexT should be a compact representation of the concept being modelled. If this is not possible, a compact proxy object should be used and a single copy of the real objects should be maintained in an external structure instead.

It is best to avoid calling DependencyGraph::removeDependency on larger dependency graphs, as the method is O(n) due to the need to rebuild the reverse lookup map on each call.

This data structure is not thread safe.

The DependencyGraph class uses the Boost Graph Library and is inspired from the Boost Graph library dependency example (Copyright 1997, 1998, 1999, 2000 University of Notre Dame; authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek).

Member Function Documentation

◆ addDependency()

void addDependency	(	const VertexT &	dependency,
		bool	throwIfExists = `true`
	)

inline

Add a dependency.

If the dependency already exists and throwIfExists is set to false, the result will be a NOP.

Parameters

dependency	the dependency to add
throwIfExists	set to true to throw if the dependency already exists

Exceptions

ItemExistsException if throwIfExists is set to true and the item already exists

◆ addRelationship() [1/2]

void addRelationship	(	const VertexT &	independent,
		const VertexT &	dependent
	)

inline

Add a dependency relationship between two existing dependencies.

◆ addRelationship() [2/2]

void addRelationship	(	const VertexT &	independent,
		const VertexT &	dependent,
		const EdgeT &	edgeData
	)

inline

Add a dependency relationship between two existing dependencies, with edge data.

◆ begin() [1/2]

iterator begin ( )

inline

Get an iterator positioned at the beginning of the dependency graph.

◆ begin() [2/2]

const_iterator begin ( ) const

inline

Get a const iterator positioned at the beginning of the dependency graph.

◆ dependencyOrder()

std::vector<VertexT> dependencyOrder ( ) const

inline

Calculate the dependency order of the dependencies.

◆ directDependenciesOf()

std::vector<VertexT> directDependenciesOf ( const VertexT & dependency ) const

inline

What are the direct dependencies of the specified dependency.

◆ end() [1/2]

iterator end ( )

inline

Get an iterator positioned at the end of the dependency graph.

◆ end() [2/2]

const_iterator end ( ) const

inline

Get a const iterator positioned at the end of the dependency graph.

◆ hasCycles() [1/2]

bool hasCycles ( ) const

inline

Does the dependency graph have any cycles?

◆ hasCycles() [2/2]

bool hasCycles ( std::vector< std::pair< VertexT, VertexT >> & cycleEdges ) const

inline

Does the dependency graph have any cycles?

Parameters

cycleEdges any edges that are found to have cycles are added to this vector

◆ hasDependency()

bool hasDependency ( const VertexT & dependency ) const

inline

Does the graph have the specified dependency?

◆ logGraph()

void logGraph	(	LoggingLevel	level,
		const char *	title
	)

inline

Log the dependency tree to the "balau.container" logger if the logger is enabled for the supplied logging level.

◆ lookupDependency()

const VertexT* lookupDependency ( const VertexT & key ) const

inline

Lookups up the dependency that matches the supplied candidate object.

Returns: a const pointer to the dependency object, or nullptr if the key is not in the graph

◆ parallelDependencyOrder()

std::vector<std::vector<VertexT> > parallelDependencyOrder ( ) const

inline

Calculate the parallel dependency order of the dependencies.

This method separates dependencies into steps, where each step contains a set of independent dependencies.

◆ removeDependency()

void removeDependency	(	const VertexT &	dependency,
		bool	throwIfNotExists = `true`
	)

inline

Remove a dependency.

If the dependency does not exist and throwIfNotExists is set to false, the result will be a NOP.

This method is O(n) due to the need to rebuild the reverse lookup map on each call.

Parameters

dependency	the dependency to remove
throwIfNotExists	set to true to throw if the dependency does not exist

Exceptions

ItemDoesNotExistException if throwIfNotExists is set to true and the item does not exist

◆ removeRelationship()

void removeRelationship	(	const VertexT &	independent,
		const VertexT &	dependent
	)

inline

Remove a dependency relationship between two existing dependencies.

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

DependencyGraph.hpp (12)

Classes

Public Member Functions

Detailed Description

template<typename VertexT = boost::no_property, typename EdgeT = boost::no_property, typename GraphT = boost::no_property> class Balau::Container::DependencyGraph< VertexT, EdgeT, GraphT >

Member Function Documentation

◆ addDependency()

◆ addRelationship() [1/2]

◆ addRelationship() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ dependencyOrder()

◆ directDependenciesOf()

◆ end() [1/2]

◆ end() [2/2]

◆ hasCycles() [1/2]

◆ hasCycles() [2/2]

◆ hasDependency()

◆ logGraph()

◆ lookupDependency()

◆ parallelDependencyOrder()

◆ removeDependency()

◆ removeRelationship()

template<typename VertexT = boost::no_property, typename EdgeT = boost::no_property, typename GraphT = boost::no_property>
class Balau::Container::DependencyGraph< VertexT, EdgeT, GraphT >