Rosetta  2020.46
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Classes | Namespaces | Functions
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)