cprover
graph.h File Reference

A Template Class for Graphs. More...

#include <algorithm>
#include <cassert>
#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
setset of source nodes, must be a container with an insert(const value_type&) method.
for_each_successorfunction which given a node n and a function f, applies f on all successors of n.

Definition at line 570 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 116 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 920 of file graph.h.