cprover
graph.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: A Template Class for Graphs
4 
5 Author: Daniel Kroening, kroening@kroening.com
6 
7 \*******************************************************************/
8 
11 
12 #ifndef CPROVER_UTIL_GRAPH_H
13 #define CPROVER_UTIL_GRAPH_H
14 
15 #include <algorithm>
16 #include <cassert>
17 #include <functional>
18 #include <iosfwd>
19 #include <list>
20 #include <map>
21 #include <queue>
22 #include <stack>
23 #include <vector>
24 
25 #include "invariant.h"
26 
28 {
29 };
30 
33 template<class E=empty_edget>
35 {
36 public:
37  typedef std::size_t node_indext;
38 
39  typedef E edget;
40  typedef std::map<node_indext, edget> edgest;
41 
43 
45  {
46  in.insert(std::pair<node_indext, edget>(n, edget()));
47  }
48 
50  {
51  out.insert(std::pair<node_indext, edget>(n, edget()));
52  }
53 
55  {
56  in.erase(n);
57  }
58 
60  {
61  out.erase(n);
62  }
63 };
64 
66 template<class E>
67 class visited_nodet:public graph_nodet<E>
68 {
69 public:
70  typedef typename graph_nodet<E>::edget edget;
71  typedef typename graph_nodet<E>::edgest edgest;
72 
73  bool visited;
74 
76  {
77  }
78 };
79 
81 template<class E>
83  const typename graph_nodet<E>::edgest &a,
84  const typename graph_nodet<E>::edgest &b,
85  typename graph_nodet<E>::edgest &dest)
86 {
88  it_a=a.begin(),
89  it_b=b.begin();
90 
91  while(it_a!=a.end() && it_b!=b.end())
92  {
93  if(*it_a==*it_b)
94  {
95  dest.insert(*it_a);
96  it_a++;
97  it_b++;
98  }
99  else if(*it_a<*it_b)
100  it_a++;
101  else // *it_a>*it_b
102  it_b++;
103  }
104 }
105 
132 template<class N=graph_nodet<empty_edget> >
133 class grapht
134 {
135 public:
136  typedef N nodet;
137  typedef typename nodet::edgest edgest;
138  typedef std::vector<nodet> nodest;
139  typedef typename nodet::edget edget;
140  typedef typename nodet::node_indext node_indext;
141 
142 protected:
144 
145 public:
147  {
148  node_indext no=nodes.size();
149  nodes.push_back(nodet());
150  return no;
151  }
152 
153  void swap(grapht &other)
154  {
155  nodes.swap(other.nodes);
156  }
157 
159  {
160  return nodes[i].out.find(j)!=nodes[i].out.end();
161  }
162 
163  const nodet &operator[](node_indext n) const
164  {
165  return nodes[n];
166  }
167 
169  {
170  return nodes[n];
171  }
172 
174  {
175  nodes.resize(s);
176  }
177 
178  std::size_t size() const
179  {
180  return nodes.size();
181  }
182 
183  bool empty() const
184  {
185  return nodes.empty();
186  }
187 
188  const edgest &in(node_indext n) const
189  {
190  return nodes[n].in;
191  }
192 
193  const edgest &out(node_indext n) const
194  {
195  return nodes[n].out;
196  }
197 
199  {
200  nodes[a].add_out(b);
201  nodes[b].add_in(a);
202  }
203 
205  {
206  nodes[a].erase_out(b);
207  nodes[b].erase_in(a);
208  }
209 
211  {
212  return nodes[a].out[b];
213  }
214 
219 
221  {
222  remove_in_edges(n);
223  remove_out_edges(n);
224  }
225 
226  void clear()
227  {
228  nodes.clear();
229  }
230 
231  typedef std::list<node_indext> patht;
232 
234  node_indext src,
235  node_indext dest,
236  patht &path) const
237  {
238  shortest_path(src, dest, path, false);
239  }
240 
242  node_indext node,
243  patht &path) const
244  {
245  shortest_path(node, node, path, true);
246  }
247 
248  void visit_reachable(node_indext src);
249 
250  std::vector<node_indext> get_reachable(node_indext src, bool forwards) const;
251 
252  std::vector<node_indext>
253  get_reachable(const std::vector<node_indext> &src, bool forwards) const;
254 
256  void disconnect_unreachable(const std::vector<node_indext> &src);
257 
258  std::vector<typename N::node_indext>
259  depth_limited_search(typename N::node_indext src, std::size_t limit) const;
260 
261  std::vector<typename N::node_indext> depth_limited_search(
262  std::vector<typename N::node_indext> &src,
263  std::size_t limit) const;
264 
265  void make_chordal();
266 
267  // return value: number of connected subgraphs
268  std::size_t connected_subgraphs(
269  std::vector<node_indext> &subgraph_nr);
270 
271  // return value: number of SCCs
272  std::size_t SCCs(std::vector<node_indext> &subgraph_nr) const;
273 
274  bool is_dag() const
275  {
276  return empty() || !topsort().empty();
277  }
278 
279  std::list<node_indext> topsort() const;
280 
281  std::vector<node_indext> get_successors(const node_indext &n) const;
282  void output_dot(std::ostream &out) const;
283  void for_each_successor(
284  const node_indext &n,
285  std::function<void(const node_indext &)> f) const;
286 
287 protected:
288  std::vector<typename N::node_indext> depth_limited_search(
289  std::vector<typename N::node_indext> &src,
290  std::size_t limit,
291  std::vector<bool> &visited) const;
292 
293  class tarjant
294  {
295  public:
296  std::vector<bool> visited;
297  std::vector<unsigned> depth;
298  std::vector<unsigned> lowlink;
299  std::vector<bool> in_scc;
300  std::stack<node_indext> scc_stack;
301  std::vector<node_indext> &subgraph_nr;
302 
303  std::size_t scc_count, max_dfs;
304 
305  tarjant(std::size_t n, std::vector<node_indext> &_subgraph_nr):
306  subgraph_nr(_subgraph_nr)
307  {
308  visited.resize(n, false);
309  depth.resize(n, 0);
310  lowlink.resize(n, 0);
311  in_scc.resize(n, false);
312  max_dfs=scc_count=0;
313  subgraph_nr.resize(n, 0);
314  }
315  };
316 
317  void tarjan(class tarjant &t, node_indext v) const;
318 
319  void shortest_path(
320  node_indext src,
321  node_indext dest,
322  patht &path,
323  bool non_trivial) const;
324 };
325 
326 template<class N>
328 {
329  assert(a<nodes.size());
330  assert(b<nodes.size());
331  nodet &na=nodes[a];
332  nodet &nb=nodes[b];
333  na.add_out(b);
334  nb.add_out(a);
335  na.add_in(b);
336  nb.add_in(a);
337 }
338 
339 template<class N>
341 {
342  nodet &na=nodes[a];
343  nodet &nb=nodes[b];
344  na.out.erase(b);
345  nb.out.erase(a);
346  na.in.erase(b);
347  nb.in.erase(a);
348 }
349 
350 template<class N>
352 {
353  nodet &node=nodes[n];
354 
355  // delete all incoming edges
356  for(typename edgest::const_iterator
357  it=node.in.begin();
358  it!=node.in.end();
359  it++)
360  nodes[it->first].erase_out(n);
361 
362  node.in.clear();
363 }
364 
365 template<class N>
367 {
368  nodet &node=nodes[n];
369 
370  // delete all outgoing edges
371  for(typename edgest::const_iterator
372  it=node.out.begin();
373  it!=node.out.end();
374  it++)
375  nodes[it->first].erase_in(n);
376 
377  node.out.clear();
378 }
379 
380 template<class N>
382  node_indext src,
383  node_indext dest,
384  patht &path,
385  bool non_trivial) const
386 {
387  std::vector<bool> visited;
388  std::vector<unsigned> distance;
389  std::vector<unsigned> previous;
390 
391  // initialization
392  visited.resize(nodes.size(), false);
393  distance.resize(nodes.size(), (unsigned)(-1));
394  previous.resize(nodes.size(), 0);
395 
396  if(!non_trivial)
397  {
398  distance[src]=0;
399  visited[src]=true;
400  }
401 
402  // does BFS, not Dijkstra
403  // we hope the graph is sparse
404  std::vector<node_indext> frontier_set, new_frontier_set;
405 
406  frontier_set.reserve(nodes.size());
407 
408  frontier_set.push_back(src);
409 
410  unsigned d=0;
411  bool found=false;
412 
413  while(!frontier_set.empty() && !found)
414  {
415  d++;
416 
417  new_frontier_set.clear();
418  new_frontier_set.reserve(nodes.size());
419 
420  for(typename std::vector<node_indext>::const_iterator
421  f_it=frontier_set.begin();
422  f_it!=frontier_set.end() && !found;
423  f_it++)
424  {
425  node_indext i=*f_it;
426  const nodet &n=nodes[i];
427 
428  // do all neighbors
429  for(typename edgest::const_iterator
430  o_it=n.out.begin();
431  o_it!=n.out.end() && !found;
432  o_it++)
433  {
434  node_indext o=o_it->first;
435 
436  if(!visited[o])
437  {
438  distance[o]=d;
439  previous[o]=i;
440  visited[o]=true;
441 
442  if(o==dest)
443  found=true;
444  else
445  new_frontier_set.push_back(o);
446  }
447  }
448  }
449 
450  frontier_set.swap(new_frontier_set);
451  }
452 
453  // compute path
454  // walk towards 0-distance node
455  path.clear();
456 
457  // reachable at all?
458  if(distance[dest]==(unsigned)(-1))
459  return; // nah
460 
461  while(true)
462  {
463  path.push_front(dest);
464  if(distance[dest]==0 ||
465  previous[dest]==src) break; // we are there
466  assert(dest!=previous[dest]);
467  dest=previous[dest];
468  }
469 }
470 
471 template<class N>
473 {
474  std::vector<node_indext> reachable = get_reachable(src, true);
475  for(const auto index : reachable)
476  nodes[index].visited = true;
477 }
478 
487 template <class N>
489 {
490  const std::vector<node_indext> source_nodes(1, src);
491  disconnect_unreachable(source_nodes);
492 }
493 
497 template <class N>
498 void grapht<N>::disconnect_unreachable(const std::vector<node_indext> &src)
499 {
500  std::vector<node_indext> reachable = get_reachable(src, true);
501  std::sort(reachable.begin(), reachable.end());
502  std::size_t reachable_idx = 0;
503  for(std::size_t i = 0; i < nodes.size(); i++)
504  {
505  if(reachable_idx >= reachable.size())
506  remove_edges(i);
507  else if(i == reachable[reachable_idx])
508  reachable_idx++;
509  else if(i > reachable[reachable_idx])
510  throw "error disconnecting unreachable nodes";
511  else
512  remove_edges(i);
513  }
514 }
515 
525 template <class Container, typename nodet = typename Container::value_type>
527  Container &set,
528  const std::function<void(
529  const typename Container::value_type &,
530  const std::function<void(const typename Container::value_type &)> &)>
531  &for_each_successor)
532 {
533  std::vector<nodet> stack;
534  for(const auto &elt : set)
535  stack.push_back(elt);
536 
537  while(!stack.empty())
538  {
539  auto n = stack.back();
540  stack.pop_back();
541  for_each_successor(n, [&](const nodet &node) {
542  if(set.insert(node).second)
543  stack.push_back(node);
544  });
545  }
546 }
547 
553 template<class N>
554 std::vector<typename N::node_indext>
555 grapht<N>::get_reachable(node_indext src, bool forwards) const
556 {
557  std::vector<node_indext> src_vector;
558  src_vector.push_back(src);
559 
560  return get_reachable(src_vector, forwards);
561 }
562 
568 template <class N>
569 std::vector<typename N::node_indext> grapht<N>::get_reachable(
570  const std::vector<node_indext> &src,
571  bool forwards) const
572 {
573  std::vector<node_indext> result;
574  std::vector<bool> visited(size(), false);
575 
576  std::stack<node_indext, std::vector<node_indext>> s(src);
577 
578  while(!s.empty())
579  {
580  node_indext n = s.top();
581  s.pop();
582 
583  if(visited[n])
584  continue;
585 
586  result.push_back(n);
587  visited[n] = true;
588 
589  const auto &node = nodes[n];
590  const auto &succs = forwards ? node.out : node.in;
591  for(const auto succ : succs)
592  if(!visited[succ.first])
593  s.push(succ.first);
594  }
595 
596  return result;
597 }
598 
605 template <class N>
606 std::vector<typename N::node_indext> grapht<N>::depth_limited_search(
607  const typename N::node_indext src,
608  std::size_t limit) const
609 {
610  std::vector<node_indext> start_vector(1, src);
611  return depth_limited_search(start_vector, limit);
612 }
613 
620 template <class N>
621 std::vector<typename N::node_indext> grapht<N>::depth_limited_search(
622  std::vector<typename N::node_indext> &src,
623  std::size_t limit) const
624 {
625  std::vector<bool> visited(nodes.size(), false);
626 
627  for(const auto &node : src)
628  {
629  PRECONDITION(node < nodes.size());
630  visited[node] = true;
631  }
632 
633  return depth_limited_search(src, limit, visited);
634 }
635 
637 // from multiple source nodes, to find the nodes reachable within n steps
642 template <class N>
643 std::vector<typename N::node_indext> grapht<N>::depth_limited_search(
644  std::vector<typename N::node_indext> &src,
645  std::size_t limit,
646  std::vector<bool> &visited) const
647 {
648  if(limit == 0)
649  return src;
650 
651  std::vector<node_indext> next_ring;
652 
653  for(const auto &n : src)
654  {
655  for(const auto &o : nodes[n].out)
656  {
657  if(!visited[o.first])
658  {
659  next_ring.push_back(o.first);
660  visited[o.first] = true;
661  }
662  }
663  }
664 
665  if(next_ring.empty())
666  return src;
667 
668  limit--;
669 
670  for(const auto &succ : depth_limited_search(next_ring, limit, visited))
671  src.push_back(succ);
672 
673  return src;
674 }
675 
681 template<class N>
683  std::vector<node_indext> &subgraph_nr)
684 {
685  std::vector<bool> visited;
686 
687  visited.resize(nodes.size(), false);
688  subgraph_nr.resize(nodes.size(), 0);
689 
690  std::size_t nr=0;
691 
692  for(node_indext src=0; src<size(); src++)
693  {
694  if(visited[src])
695  continue;
696 
697  // DFS
698 
699  std::stack<node_indext> s;
700  s.push(src);
701 
702  while(!s.empty())
703  {
704  node_indext n=s.top();
705  s.pop();
706 
707  visited[n]=true;
708  subgraph_nr[n]=nr;
709 
710  const nodet &node=nodes[n];
711 
712  for(const auto &o : node.out)
713  {
714  if(!visited[o.first])
715  s.push(o.first);
716  }
717  }
718 
719  nr++;
720  }
721 
722  return nr;
723 }
724 
725 template<class N>
726 void grapht<N>::tarjan(tarjant &t, node_indext v) const
727 {
728  t.scc_stack.push(v);
729  t.in_scc[v]=true;
730  t.depth[v]=t.max_dfs;
731  t.lowlink[v]=t.max_dfs;
732  t.visited[v]=true;
733  t.max_dfs++;
734 
735  const nodet &node=nodes[v];
736  for(typename edgest::const_iterator
737  it=node.out.begin();
738  it!=node.out.end();
739  it++)
740  {
741  node_indext vp=it->first;
742  if(!t.visited[vp])
743  {
744  tarjan(t, vp);
745  t.lowlink[v]=std::min(t.lowlink[v], t.lowlink[vp]);
746  }
747  else if(t.in_scc[vp])
748  t.lowlink[v]=std::min(t.lowlink[v], t.depth[vp]);
749  }
750 
751  // check if root of SCC
752  if(t.lowlink[v]==t.depth[v])
753  {
754  while(true)
755  {
756  assert(!t.scc_stack.empty());
757  node_indext vp=t.scc_stack.top();
758  t.scc_stack.pop();
759  t.in_scc[vp]=false;
760  t.subgraph_nr[vp]=t.scc_count;
761  if(vp==v)
762  break;
763  }
764 
765  t.scc_count++;
766  }
767 }
768 
781 template<class N>
782 std::size_t grapht<N>::SCCs(std::vector<node_indext> &subgraph_nr) const
783 {
784  tarjant t(nodes.size(), subgraph_nr);
785 
786  for(node_indext v0=0; v0<size(); v0++)
787  if(!t.visited[v0])
788  tarjan(t, v0);
789 
790  return t.scc_count;
791 }
792 
797 template<class N>
799 {
800  grapht tmp(*this);
801 
802  // This assumes an undirected graph.
803  // 1. remove all nodes in tmp, reconnecting the remaining ones
804  // 2. the chordal graph is the old one plus the new edges
805 
806  for(node_indext i=0; i<tmp.size(); i++)
807  {
808  const nodet &n=tmp[i];
809 
810  // connect all the nodes in n.out with each other
811  for(const auto &o1 : n.out)
812  for(const auto &o2 : n.out)
813  {
814  if(o1.first!=o2.first)
815  {
816  tmp.add_undirected_edge(o1.first, o2.first);
817  this->add_undirected_edge(o1.first, o2.first);
818  }
819  }
820 
821  // remove node from tmp graph
822  tmp.remove_edges(i);
823  }
824 }
825 
828 template<class N>
829 std::list<typename grapht<N>::node_indext> grapht<N>::topsort() const
830 {
831  // list of topologically sorted nodes
832  std::list<node_indext> nodelist;
833  // queue of working set nodes with in-degree zero
834  std::queue<node_indext> indeg0_nodes;
835  // in-degree for each node
836  std::vector<size_t> in_deg(nodes.size(), 0);
837 
838  // abstract graph as in-degree of each node
839  for(node_indext idx=0; idx<nodes.size(); idx++)
840  {
841  in_deg[idx]=in(idx).size();
842  if(in_deg[idx]==0)
843  indeg0_nodes.push(idx);
844  }
845 
846  while(!indeg0_nodes.empty())
847  {
848  node_indext source=indeg0_nodes.front();
849  indeg0_nodes.pop();
850  nodelist.push_back(source);
851 
852  for(const auto &edge : out(source))
853  {
854  const node_indext target=edge.first;
855  INVARIANT(in_deg[target]!=0, "in-degree of node cannot be zero here");
856 
857  // remove edge from graph, by decrementing the in-degree of target
858  // outgoing edges from source will not be traversed again
859  in_deg[target]--;
860  if(in_deg[target]==0)
861  indeg0_nodes.push(target);
862  }
863  }
864 
865  // if all nodes are sorted, the graph is acyclic
866  // return empty list in case of cyclic graph
867  if(nodelist.size()!=nodes.size())
868  nodelist.clear();
869  return nodelist;
870 }
871 
872 template <typename node_index_type>
874  std::ostream &out,
875  const std::function<void(std::function<void(const node_index_type &)>)>
876  &for_each_node,
877  const std::function<
878  void(const node_index_type &, std::function<void(const node_index_type &)>)>
879  &for_each_succ,
880  const std::function<std::string(const node_index_type &)> node_to_string)
881 {
882  for_each_node([&](const node_index_type &i) {
883  for_each_succ(i, [&](const node_index_type &n) {
884  out << node_to_string(i) << " -> " << node_to_string(n) << '\n';
885  });
886  });
887 }
888 
889 template <class N>
890 std::vector<typename grapht<N>::node_indext>
892 {
893  std::vector<node_indext> result;
894  std::transform(
895  nodes[n].out.begin(),
896  nodes[n].out.end(),
897  std::back_inserter(result),
898  [&](const std::pair<node_indext, edget> &edge) { return edge.first; });
899  return result;
900 }
901 
902 template <class N>
904  const node_indext &n,
905  std::function<void(const node_indext &)> f) const
906 {
907  std::for_each(
908  nodes[n].out.begin(),
909  nodes[n].out.end(),
910  [&](const std::pair<node_indext, edget> &edge) { f(edge.first); });
911 }
912 
913 template <class N>
914 void grapht<N>::output_dot(std::ostream &out) const
915 {
916  const auto for_each_node =
917  [&](const std::function<void(const node_indext &)> &f) {
918  for(node_indext i = 0; i < nodes.size(); ++i)
919  f(i);
920  };
921 
922  const auto for_each_succ = [&](
923  const node_indext &i, const std::function<void(const node_indext &)> &f) {
924  for_each_successor(i, f);
925  };
926 
927  const auto to_string = [](const node_indext &i) { return std::to_string(i); };
928  output_dot_generic<node_indext>(out, for_each_node, for_each_succ, to_string);
929 }
930 
931 #endif // CPROVER_UTIL_GRAPH_H
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)
Definition: graph.h:873
void remove_in_edges(node_indext n)
Definition: graph.h:351
std::size_t max_dfs
Definition: graph.h:303
A generic directed graph with a parametric node type.
Definition: graph.h:133
visited_nodet()
Definition: graph.h:75
nodest nodes
Definition: graph.h:143
std::vector< unsigned > lowlink
Definition: graph.h:298
void clear()
Definition: graph.h:226
std::size_t SCCs(std::vector< node_indext > &subgraph_nr) const
Computes strongly-connected components of a graph and yields a vector expressing a mapping from nodes...
Definition: graph.h:782
void add_undirected_edge(node_indext a, node_indext b)
Definition: graph.h:327
A node type with an extra bit.
Definition: graph.h:67
std::size_t connected_subgraphs(std::vector< node_indext > &subgraph_nr)
Find connected subgraphs in an undirected graph.
Definition: graph.h:682
bool is_dag() const
Definition: graph.h:274
void visit_reachable(node_indext src)
Definition: graph.h:472
#define INVARIANT(CONDITION, REASON)
Definition: invariant.h:204
edgest in
Definition: graph.h:42
void shortest_path(node_indext src, node_indext dest, patht &path) const
Definition: graph.h:233
bool has_edge(node_indext i, node_indext j) const
Definition: graph.h:158
edgest out
Definition: graph.h:42
void remove_edges(node_indext n)
Definition: graph.h:220
nodet::edget edget
Definition: graph.h:139
void erase_in(node_indext n)
Definition: graph.h:54
std::vector< bool > visited
Definition: graph.h:296
N nodet
Definition: graph.h:136
bool visited
Definition: graph.h:73
const edgest & out(node_indext n) const
Definition: graph.h:193
std::list< path_nodet > patht
Definition: path.h:45
bool empty() const
Definition: graph.h:183
#define PRECONDITION(CONDITION)
Definition: invariant.h:242
std::vector< bool > in_scc
Definition: graph.h:299
std::size_t size() const
Definition: graph.h:178
std::list< node_indext > patht
Definition: graph.h:231
std::list< node_indext > topsort() const
Find a topological order of the nodes if graph is DAG, return empty list for non-DAG or empty graph...
Definition: graph.h:829
nodet::node_indext node_indext
Definition: graph.h:140
void remove_undirected_edge(node_indext a, node_indext b)
Definition: graph.h:340
std::vector< node_indext > get_successors(const node_indext &n) const
Definition: graph.h:891
void add_in(node_indext n)
Definition: graph.h:44
edget & edge(node_indext a, node_indext b)
Definition: graph.h:210
std::size_t node_indext
Definition: graph.h:37
void output_dot(std::ostream &out) const
Definition: graph.h:914
std::map< node_indext, edget > edgest
Definition: graph.h:40
void tarjan(class tarjant &t, node_indext v) const
Definition: graph.h:726
void make_chordal()
Ensure a graph is chordal (contains no 4+-cycles without an edge crossing the cycle) by adding extra ...
Definition: graph.h:798
void erase_out(node_indext n)
Definition: graph.h:59
void remove_edge(node_indext a, node_indext b)
Definition: graph.h:204
const nodet & operator[](node_indext n) const
Definition: graph.h:163
std::size_t scc_count
Definition: graph.h:303
std::vector< node_indext > & subgraph_nr
Definition: graph.h:301
node_indext add_node()
Definition: graph.h:146
std::vector< typename N::node_indext > depth_limited_search(typename N::node_indext src, std::size_t limit) const
Run recursive depth-limited search on the graph, starting from multiple source nodes, to find the nodes reachable within n steps.
Definition: graph.h:606
void for_each_successor(const node_indext &n, std::function< void(const node_indext &)> f) const
Definition: graph.h:903
void remove_out_edges(node_indext n)
Definition: graph.h:366
std::stack< node_indext > scc_stack
Definition: graph.h:300
nodet::edgest edgest
Definition: graph.h:137
void shortest_loop(node_indext node, patht &path) const
Definition: graph.h:241
std::string to_string(const string_constraintt &expr)
Used for debug printing.
void add_edge(node_indext a, node_indext b)
Definition: graph.h:198
std::vector< unsigned > depth
Definition: graph.h:297
void add_out(node_indext n)
Definition: graph.h:49
const edgest & in(node_indext n) const
Definition: graph.h:188
void swap(grapht &other)
Definition: graph.h:153
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: graph.h:82
std::vector< nodet > nodest
Definition: graph.h:138
tarjant(std::size_t n, std::vector< node_indext > &_subgraph_nr)
Definition: graph.h:305
void resize(node_indext s)
Definition: graph.h:173
E edget
Definition: graph.h:39
nodet & operator[](node_indext n)
Definition: graph.h:168
graph_nodet< E >::edgest edgest
Definition: graph.h:71
#define stack(x)
Definition: parser.h:144
This class represents a node in a directed graph.
Definition: graph.h:34
graph_nodet< E >::edget edget
Definition: graph.h:70
std::vector< node_indext > get_reachable(node_indext src, bool forwards) const
Run depth-first search on the graph, starting from a single source node.
Definition: graph.h:555
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.
Definition: graph.h:526
void disconnect_unreachable(node_indext src)
Removes any edges between nodes in a graph that are unreachable from a given start node...
Definition: graph.h:488