Dependency graph. Collects nodes and builds a searchable directed graph. More...

#include <Dep.h>

Classes
class	Iter_
	Depth-first pre-order iterator over vertices. More...

class	NodeIter_
	Depth-first pre-order iterator over nodes. Iterates over nodes that constitute each vertex in a vertex range. More...

class	Vertex
	A vertex is initially associated with one key and acts like a multi-map, storing all nodes and graph links of DepNodes matching that key. More...

Public Types
typedef stdutil::unordered_set< DepNode *, Alloc >	NodeList

typedef stdutil::unordered_set< const DepNode *, Alloc >	NodeListConst

typedef stdutil::unordered_set< Key, Alloc >	KeyList

typedef Iter_< Vertex >	Iter

typedef Iter_< const Vertex >	ConstIter

typedef NodeIter_< Vertex >	NodeIter

typedef NodeIter_< const Vertex >	NodeConstIter

Public Member Functions
bool	add (DepNode &node)
	Add a node to the graph. More...

bool	remove (DepNode &node)
	Remove a node from the graph. More...

void	clear ()
	Clear graph of all nodes. More...

Range_< ConstIter, ConstIter >	range (optional< const Key & > start=optnull, DepType type=DepType::out) const
	Get a depth-first pre-order range starting from a vertex. If start vertex is null then range is over all vertices, starting from all roots. More...

Range_< Iter, Iter >	range (optional< const Key & > start=optnull, DepType type=DepType::out)

Range_< NodeConstIter, NodeConstIter >	rangeNode (optional< const Key & > start=optnull, DepType type=DepType::out) const
	Get a depth-first pre-order range over nodes starting from a vertex. If start vertex is null then range is over all nodes in graph. More...

Range_< NodeIter, NodeIter >	rangeNode (optional< const Key & > start=optnull, DepType type=DepType::out)

bool	depends (const Key &vertex, const Key &dependency, DepType type=DepType::out) const
	Check if vertex depends on another vertex. More...

bool	depends (const Key &vertex, const DepNode &dependency, DepType type=DepType::out) const
	Check if vertex depends on node. More...

const Vertex *	vertex (const Key &key) const
	Get a vertex which contains a list of cyclical (strongly connected) dependency nodes. More...

Vertex *	vertex (const Key &key)

void	condense ()
	Condense directed graph into directed acyclic graph. Useful for finding dependency cycles and optimizing searches. More...

Detailed Description

template<class DepNode_>
class honey::DepGraph< DepNode_ >

Dependency graph. Collects nodes and builds a searchable directed graph.

Nodes can be added and removed from the graph freely, even after calls to condense(). Do not change a node's dependency list while it is still in the graph, the node must be removed first and re-added after.

Member Typedef Documentation

template<class DepNode_>

typedef Iter_<const Vertex> honey::DepGraph< DepNode_ >::ConstIter

template<class DepNode_>

typedef Iter_<Vertex> honey::DepGraph< DepNode_ >::Iter

template<class DepNode_>

typedef stdutil::unordered_set<Key, Alloc> honey::DepGraph< DepNode_ >::KeyList

template<class DepNode_>

typedef NodeIter_<const Vertex> honey::DepGraph< DepNode_ >::NodeConstIter

template<class DepNode_>

typedef NodeIter_<Vertex> honey::DepGraph< DepNode_ >::NodeIter

template<class DepNode_>

typedef stdutil::unordered_set<DepNode*, Alloc> honey::DepGraph< DepNode_ >::NodeList

template<class DepNode_>

typedef stdutil::unordered_set<const DepNode*, Alloc> honey::DepGraph< DepNode_ >::NodeListConst

Member Function Documentation

template<class DepNode_>

bool honey::DepGraph< DepNode_ >::add ( DepNode & node )

inline

Add a node to the graph.

template<class DepNode_>

void honey::DepGraph< DepNode_ >::clear ( )

inline

Clear graph of all nodes.

template<class DepNode_>

void honey::DepGraph< DepNode_ >::condense ( )

inline

Condense directed graph into directed acyclic graph. Useful for finding dependency cycles and optimizing searches.

The condensation is done by finding all strongly connected subgraphs and merging each subgraph into one vertex. All nodes can still be added/removed normally after condensation, and condensation can be done repeatedly. If a node is removed after condensation and it belongs to a merged vertex, then the vertex will be decomposed back into its constituent nodes.

template<class DepNode_>

bool honey::DepGraph< DepNode_ >::depends	(	const Key &	vertex,
		const Key &	dependency,
		DepType	type = `DepType::out`
	)		const

inline

Check if vertex depends on another vertex.

template<class DepNode_>

bool honey::DepGraph< DepNode_ >::depends	(	const Key &	vertex,
		const DepNode &	dependency,
		DepType	type = `DepType::out`
	)		const

inline

Check if vertex depends on node.

template<class DepNode_>

Range_<ConstIter, ConstIter> honey::DepGraph< DepNode_ >::range	(	optional< const Key & >	start = `optnull`,
		DepType	type = `DepType::out`
	)		const

inline

Get a depth-first pre-order range starting from a vertex. If start vertex is null then range is over all vertices, starting from all roots.

template<class DepNode_>

Range_<Iter, Iter> honey::DepGraph< DepNode_ >::range	(	optional< const Key & >	start = `optnull`,
		DepType	type = `DepType::out`
	)

inline

template<class DepNode_>

Range_<NodeConstIter, NodeConstIter> honey::DepGraph< DepNode_ >::rangeNode	(	optional< const Key & >	start = `optnull`,
		DepType	type = `DepType::out`
	)		const

inline

Get a depth-first pre-order range over nodes starting from a vertex. If start vertex is null then range is over all nodes in graph.

template<class DepNode_>

Range_<NodeIter, NodeIter> honey::DepGraph< DepNode_ >::rangeNode	(	optional< const Key & >	start = `optnull`,
		DepType	type = `DepType::out`
	)

inline

template<class DepNode_>

bool honey::DepGraph< DepNode_ >::remove ( DepNode & node )

inline

Remove a node from the graph.

template<class DepNode_>

const Vertex* honey::DepGraph< DepNode_ >::vertex ( const Key & key ) const

inline

Get a vertex which contains a list of cyclical (strongly connected) dependency nodes.

Call condense() prior to this to merge each group of cyclical nodes into a single vertex.

template<class DepNode_>

Vertex* honey::DepGraph< DepNode_ >::vertex ( const Key & key )

inline

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

src/common/Honey/Graph/Dep.h

Classes

Public Types

Public Member Functions

Detailed Description

template<class DepNode_> class honey::DepGraph< DepNode_ >

Member Typedef Documentation

Member Function Documentation

template<class DepNode_>
class honey::DepGraph< DepNode_ >