graph.h File Reference

A Template Class for Graphs. More...

#include <algorithm>
#include <functional>
#include <iosfwd>
#include <list>
#include <map>
#include <queue>
#include <sstream>
#include <stack>
#include <vector>
#include "invariant.h"

Include dependency graph for graph.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	empty_edget
class	graph_nodet< E >
	This class represents a node in a directed graph. More...
class	visited_nodet< E >
	A node type with an extra bit. More...
class	grapht< N >
	A generic directed graph with a parametric node type. More...
class	grapht< N >::tarjant

Functions
template<class E >
void	intersection (const typename graph_nodet< E >::edgest &a, const typename graph_nodet< E >::edgest &b, typename graph_nodet< E >::edgest &dest)
	Compute intersection of two edge sets, in linear time. More...
template<class Container , typename nodet = typename Container::value_type>
void	get_reachable (Container &set, const std::function< void(const typename Container::value_type &, const std::function< void(const typename Container::value_type &)> &)> &for_each_successor)
	Add to set, nodes that are reachable from set. More...
template<typename node_index_type >
void	output_dot_generic (std::ostream &out, const std::function< void(std::function< void(const node_index_type &)>)> &for_each_node, const std::function< void(const node_index_type &, std::function< void(const node_index_type &)>)> &for_each_succ, const std::function< std::string(const node_index_type &)> node_to_string, const std::function< std::string(const node_index_type &)> node_to_pretty)

Detailed Description

A Template Class for Graphs.

Definition in file graph.h.

Function Documentation

get_reachable()

template<class Container , typename nodet = typename Container::value_type>

void get_reachable	(	Container &	set,
		const std::function< void(const typename Container::value_type &, const std::function< void(const typename Container::value_type &)> &)> &	for_each_successor
	)

Add to set, nodes that are reachable from set.

This implements a depth first search using a stack: at each step we pop a node, and push on the stack all its successors that have not yet been visited.

Parameters

set	set of source nodes, must be a container with an insert(const value_type&) method.
for_each_successor	function which given a node n and a function f, applies f on all successors of n.

Definition at line 573 of file graph.h.

intersection()

template<class E >

void intersection	(	const typename graph_nodet< E >::edgest &	a,
		const typename graph_nodet< E >::edgest &	b,
		typename graph_nodet< E >::edgest &	dest
	)

Compute intersection of two edge sets, in linear time.

Definition at line 115 of file graph.h.

output_dot_generic()

template<typename node_index_type >

void output_dot_generic	(	std::ostream &	out,
		const std::function< void(std::function< void(const node_index_type &)>)> &	for_each_node,
		const std::function< void(const node_index_type &, std::function< void(const node_index_type &)>)> &	for_each_succ,
		const std::function< std::string(const node_index_type &)>	node_to_string,
		const std::function< std::string(const node_index_type &)>	node_to_pretty
	)

Definition at line 923 of file graph.h.