Overview

A mutable graph structure that models dependency relationships in a dependency graph.

DependencyGraph uses the Boost graph library, and is inspired by the Boost graph library dependency example.

Quick start

#include <Balau/Container/DependencyGraph.hpp>

Construction

The construction of a dependency graph is made by the default constructor.

			// Create a dependency graph (T is the value type stored in each graph node).
			DependencyGraph<T> graph;
		

Population

Population of the graph is performed with two main actions:

• adding dependency instances;
• creating dependency relationships.

These two actions correspond to the addition of graph nodes and graph edges.

To add a node, call the addDependency method.

			// Add a dependency instance to the graph.

			// The instance (normally sourced elsewhere).
			T value;

			graph.addDependency(value);
		

To add a dependency relationship, call the addRelationship method.

			// Add a relationship between two dependencies.

			// The instances (normally sourced elsewhere).
			T independent;
			T dependent;

			graph.addRelationship(independent, dependent);
		

The dependency graph is designed to use small values that are used as keys. The types used in the dependency graph must therefore have a valid equals method for use in a map based structure. If a large amount of data needs to be stored in each value, one suitable approach would be to add a std::shared_ptr field to the value and exclude it from the comparison method logic.

Querying

In addition to standard iterators, the dependency graph has a set of query methods.

Function name	Description
hasDependency	Does the graph have the specified dependency?
directDependenciesOf	What are the direct dependencies of the specified dependency.
dependencyOrder	Calculate the dependency order of the dependencies.
parallelDependencyOrder	Calculate the parallel dependency order of the dependencies.
hasCycles	Does the dependency graph have any cycles?

In addition to the query methods, the logGraph method logs the contents of the dependency graph to the logging system.

See the DependencyGraph API documentation for information on the API for these methods.

Concurrency

The dependency graph is not thread safe.