Digraph.hh File Reference

generic directed graph class header More...

#include <utility/graph/Digraph.fwd.hh>
#include <utility/graph/unordered_object_pool.fwd.hpp>
#include <platform/types.hh>
#include <utility/vector1.hh>
#include <utility/VirtualBase.hh>
#include <iosfwd>
#include <list>

Classes
class	utility::graph::DirectedEdgeListElement
	An extensible directed graph class. More...
class	utility::graph::DirectedEdgeListIterator
	Custom DirectedEdge list (non-const) iterator class, which can return non-const DirectedEdge pointers. This iterator cannot be used to change the structure of its list without access to that list directly. Customized since STL's const-iterator cannot be prevented from giving non-const access to its data. The former workaround to this problem was to define two sets of edge lists on each vertex: a list< DirectedEdge * > and a list< DirectedEdge const * >. More...
class	utility::graph::DirectedEdgeListConstIterator
	Custom DirectedEdge list const iterator class, which returns only const DirectedEdge pointers. This iterator cannot be used to change the structure of its list without access to that list directly. Customized since STL's const-iterator cannot be prevented from giving non-const access to its data. More...
class	utility::graph::DirectedEdgeList
	Custom edge list class. Returns const-iterators which only return DirectedEdge const *'s and non-const-iterators which can return either const or non-const DirectedEdge*'s. Manages its own memory using an unordered-object-pool for fast insertion and deletion of DirectedEdgeListElements. Implemented as a doubly linked list, though there's no practical way to start at the end of a list and work backward since decrementing the end iterator is not a valid operation. More...
class	utility::graph::DirectedNode
class	utility::graph::DirectedEdge
class	utility::graph::Digraph
	A Digraph with constant time edge insertion and deletion. Extensible. More...

Namespaces
	utility
	unresizable vector whose size is known at compile time, which may be allocated on the stack, and which indexes from 0.
	utility::graph

Functions
std::pair< std::list< platform::Size >, bool >	utility::graph::topological_sort (Digraph const &g)
	Construct a topological sort for the input directed graph, if it is a DAG, and return whether or not the input graph is actually a DAG. More...
bool	utility::graph::digraph_is_a_DAG (Digraph const &g)
	Return whether or not the input directed graph is a DAG – this invokes the topological_sort function and simply returns the second element in the pair that it returns. More...

Detailed Description

generic directed graph class header

Author

Andrew Leaver-Fay (aleav.nosp@m.erfa.nosp@m.y@gma.nosp@m.il.c.nosp@m.om)