Digraph.cc File Reference

directed graph base classes More...

#include <utility/graph/Digraph.hh>
#include <utility/graph/unordered_object_pool.hpp>
#include <utility/assert.hh>
#include <iostream>
#include <ObjexxFCL/FArray2D.hh>
#include <boost/pool/object_pool.hpp>

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
void	utility::graph::visit (Digraph const &g, platform::Size node_index, utility::vector1< platform::Size > &visited_status, std::list< platform::Size > &toposort_order, bool &is_DAG)
platform::Size	utility::graph::find_unmarked_node (utility::vector1< platform::Size > &visited_status, platform::Size last_descend_from)
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...

Variables
platform::Size const	utility::graph::NOT_VISITED = 0
platform::Size const	utility::graph::TEMPORARY_VISITED = 1
platform::Size const	utility::graph::VISITED = 2

Detailed Description

directed graph base classes

Author

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