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 <sstream>
23 #include <stack>
24 #include <vector>
25 
26 #include "invariant.h"
27 
29 {
30 };
31 
34 template<class E=empty_edget>
36 {
37 public:
38  typedef std::size_t node_indext;
39 
40  typedef E edget;
41  typedef std::map<node_indext, edget> edgest;
42 
44 
46  {
47  in.insert(std::pair<node_indext, edget>(n, edget()));
48  }
49 
51  {
52  out.insert(std::pair<node_indext, edget>(n, edget()));
53  }
54 
56  {
57  in.erase(n);
58  }
59 
61  {
62  out.erase(n);
63  }
64 
65 private:
81  virtual std::string dot_attributes(const node_indext &) const
82  {
83  return "";
84  }
85 
86 public:
87  std::string pretty(const node_indext &idx) const
88  {
89  std::stringstream ss;
90  ss << std::to_string(idx) << " " << dot_attributes(idx);
91  return ss.str();
92  }
93 
94  virtual ~graph_nodet()
95  {
96  }
97 };
98 
100 template<class E>
101 class visited_nodet:public graph_nodet<E>
102 {
103 public:
104  typedef typename graph_nodet<E>::edget edget;
105  typedef typename graph_nodet<E>::edgest edgest;
106 
107  bool visited;
108 
110  {
111  }
112 };
113 
115 template<class E>
117  const typename graph_nodet<E>::edgest &a,
118  const typename graph_nodet<E>::edgest &b,
119  typename graph_nodet<E>::edgest &dest)
120 {
122  it_a=a.begin(),
123  it_b=b.begin();
124 
125  while(it_a!=a.end() && it_b!=b.end())
126  {
127  if(*it_a==*it_b)
128  {
129  dest.insert(*it_a);
130  it_a++;
131  it_b++;
132  }
133  else if(*it_a<*it_b)
134  it_a++;
135  else // *it_a>*it_b
136  it_b++;
137  }
138 }
139 
166 template<class N=graph_nodet<empty_edget> >
167 class grapht
168 {
169 public:
170  typedef N nodet;
171  typedef typename nodet::edgest edgest;
172  typedef std::vector<nodet> nodest;
173  typedef typename nodet::edget edget;
174  typedef typename nodet::node_indext node_indext;
175 
176 protected:
178 
179 public:
181  {
182  node_indext no=nodes.size();
183  nodes.push_back(nodet());
184  return no;
185  }
186 
187  void swap(grapht &other)
188  {
189  nodes.swap(other.nodes);
190  }
191 
193  {
194  return nodes[i].out.find(j)!=nodes[i].out.end();
195  }
196 
197  const nodet &operator[](node_indext n) const
198  {
199  return nodes[n];
200  }
201 
203  {
204  return nodes[n];
205  }
206 
208  {
209  nodes.resize(s);
210  }
211 
212  std::size_t size() const
213  {
214  return nodes.size();
215  }
216 
217  bool empty() const
218  {
219  return nodes.empty();
220  }
221 
222  const edgest &in(node_indext n) const
223  {
224  return nodes[n].in;
225  }
226 
227  const edgest &out(node_indext n) const
228  {
229  return nodes[n].out;
230  }
231 
233  {
234  nodes[a].add_out(b);
235  nodes[b].add_in(a);
236  }
237 
239  {
240  nodes[a].erase_out(b);
241  nodes[b].erase_in(a);
242  }
243 
245  {
246  return nodes[a].out[b];
247  }
248 
253 
255  {
256  remove_in_edges(n);
257  remove_out_edges(n);
258  }
259 
260  void clear()
261  {
262  nodes.clear();
263  }
264 
265  typedef std::list<node_indext> patht;
266 
268  node_indext src,
269  node_indext dest,
270  patht &path) const
271  {
272  shortest_path(src, dest, path, false);
273  }
274 
276  node_indext node,
277  patht &path) const
278  {
279  shortest_path(node, node, path, true);
280  }
281 
282  void visit_reachable(node_indext src);
283 
284  std::vector<node_indext> get_reachable(node_indext src, bool forwards) const;
285 
286  std::vector<node_indext>
287  get_reachable(const std::vector<node_indext> &src, bool forwards) const;
288 
290  void disconnect_unreachable(const std::vector<node_indext> &src);
291 
292  std::vector<typename N::node_indext>
293  depth_limited_search(typename N::node_indext src, std::size_t limit) const;
294 
295  std::vector<typename N::node_indext> depth_limited_search(
296  std::vector<typename N::node_indext> &src,
297  std::size_t limit) const;
298 
299  void make_chordal();
300 
301  // return value: number of connected subgraphs
302  std::size_t connected_subgraphs(
303  std::vector<node_indext> &subgraph_nr);
304 
305  // return value: number of SCCs
306  std::size_t SCCs(std::vector<node_indext> &subgraph_nr) const;
307 
308  bool is_dag() const
309  {
310  return empty() || !topsort().empty();
311  }
312 
313  std::list<node_indext> topsort() const;
314 
315  std::vector<node_indext> get_successors(const node_indext &n) const;
316  void output_dot(std::ostream &out) const;
317  void for_each_successor(
318  const node_indext &n,
319  std::function<void(const node_indext &)> f) const;
320 
321 protected:
322  std::vector<typename N::node_indext> depth_limited_search(
323  std::vector<typename N::node_indext> &src,
324  std::size_t limit,
325  std::vector<bool> &visited) const;
326 
327  class tarjant
328  {
329  public:
330  std::vector<bool> visited;
331  std::vector<unsigned> depth;
332  std::vector<unsigned> lowlink;
333  std::vector<bool> in_scc;
334  std::stack<node_indext> scc_stack;
335  std::vector<node_indext> &subgraph_nr;
336 
337  std::size_t scc_count, max_dfs;
338 
339  tarjant(std::size_t n, std::vector<node_indext> &_subgraph_nr):
340  subgraph_nr(_subgraph_nr)
341  {
342  visited.resize(n, false);
343  depth.resize(n, 0);
344  lowlink.resize(n, 0);
345  in_scc.resize(n, false);
346  max_dfs=scc_count=0;
347  subgraph_nr.resize(n, 0);
348  }
349  };
350 
351  void tarjan(class tarjant &t, node_indext v) const;
352 
353  void shortest_path(
354  node_indext src,
355  node_indext dest,
356  patht &path,
357  bool non_trivial) const;
358 };
359 
360 template<class N>
362 {
363  PRECONDITION(a < nodes.size());
364  PRECONDITION(b < nodes.size());
365  nodet &na=nodes[a];
366  nodet &nb=nodes[b];
367  na.add_out(b);
368  nb.add_out(a);
369  na.add_in(b);
370  nb.add_in(a);
371 }
372 
373 template<class N>
375 {
376  nodet &na=nodes[a];
377  nodet &nb=nodes[b];
378  na.out.erase(b);
379  nb.out.erase(a);
380  na.in.erase(b);
381  nb.in.erase(a);
382 }
383 
384 template<class N>
386 {
387  nodet &node=nodes[n];
388 
389  // delete all incoming edges
390  for(typename edgest::const_iterator
391  it=node.in.begin();
392  it!=node.in.end();
393  it++)
394  nodes[it->first].erase_out(n);
395 
396  node.in.clear();
397 }
398 
399 template<class N>
401 {
402  nodet &node=nodes[n];
403 
404  // delete all outgoing edges
405  for(typename edgest::const_iterator
406  it=node.out.begin();
407  it!=node.out.end();
408  it++)
409  nodes[it->first].erase_in(n);
410 
411  node.out.clear();
412 }
413 
414 template<class N>
416  node_indext src,
417  node_indext dest,
418  patht &path,
419  bool non_trivial) const
420 {
421  std::vector<bool> visited;
422  std::vector<unsigned> distance;
423  std::vector<unsigned> previous;
424 
425  // initialization
426  visited.resize(nodes.size(), false);
427  distance.resize(nodes.size(), (unsigned)(-1));
428  previous.resize(nodes.size(), 0);
429 
430  if(!non_trivial)
431  {
432  distance[src]=0;
433  visited[src]=true;
434  }
435 
436  // does BFS, not Dijkstra
437  // we hope the graph is sparse
438  std::vector<node_indext> frontier_set, new_frontier_set;
439 
440  frontier_set.reserve(nodes.size());
441 
442  frontier_set.push_back(src);
443 
444  unsigned d=0;
445  bool found=false;
446 
447  while(!frontier_set.empty() && !found)
448  {
449  d++;
450 
451  new_frontier_set.clear();
452  new_frontier_set.reserve(nodes.size());
453 
454  for(typename std::vector<node_indext>::const_iterator
455  f_it=frontier_set.begin();
456  f_it!=frontier_set.end() && !found;
457  f_it++)
458  {
459  node_indext i=*f_it;
460  const nodet &n=nodes[i];
461 
462  // do all neighbors
463  for(typename edgest::const_iterator
464  o_it=n.out.begin();
465  o_it!=n.out.end() && !found;
466  o_it++)
467  {
468  node_indext o=o_it->first;
469 
470  if(!visited[o])
471  {
472  distance[o]=d;
473  previous[o]=i;
474  visited[o]=true;
475 
476  if(o==dest)
477  found=true;
478  else
479  new_frontier_set.push_back(o);
480  }
481  }
482  }
483 
484  frontier_set.swap(new_frontier_set);
485  }
486 
487  // compute path
488  // walk towards 0-distance node
489  path.clear();
490 
491  // reachable at all?
492  if(distance[dest]==(unsigned)(-1))
493  return; // nah
494 
495  while(true)
496  {
497  path.push_front(dest);
498  if(distance[dest]==0 ||
499  previous[dest]==src) break; // we are there
500  INVARIANT(
501  dest != previous[dest], "loops cannot be part of the shortest path");
502  dest=previous[dest];
503  }
504 }
505 
506 template<class N>
508 {
509  std::vector<node_indext> reachable = get_reachable(src, true);
510  for(const auto index : reachable)
511  nodes[index].visited = true;
512 }
513 
522 template <class N>
524 {
525  const std::vector<node_indext> source_nodes(1, src);
526  disconnect_unreachable(source_nodes);
527 }
528 
532 template <class N>
533 void grapht<N>::disconnect_unreachable(const std::vector<node_indext> &src)
534 {
535  std::vector<node_indext> reachable = get_reachable(src, true);
536  std::sort(reachable.begin(), reachable.end());
537  std::size_t reachable_idx = 0;
538  for(std::size_t i = 0; i < nodes.size(); i++)
539  {
540  // Holds since `reachable` contains node indices (i.e., all elements are
541  // smaller than `nodes.size()`), `reachable` is sorted, indices from `0` to
542  // `nodes.size()-1` are iterated over by variable i in order, and
543  // `reachable_idx` is only incremented when `i == reachable[reachable_idx]`
544  // holds.
545  INVARIANT(
546  reachable_idx >= reachable.size() || i <= reachable[reachable_idx],
547  "node index i is smaller or equal to the node index at "
548  "reachable[reachable_idx], when reachable_idx is within bounds");
549 
550  if(reachable_idx >= reachable.size())
551  remove_edges(i);
552  else if(i == reachable[reachable_idx])
553  reachable_idx++;
554  else
555  remove_edges(i);
556  }
557 }
558 
568 template <class Container, typename nodet = typename Container::value_type>
570  Container &set,
571  const std::function<void(
572  const typename Container::value_type &,
573  const std::function<void(const typename Container::value_type &)> &)>
574  &for_each_successor)
575 {
576  std::vector<nodet> stack;
577  for(const auto &elt : set)
578  stack.push_back(elt);
579 
580  while(!stack.empty())
581  {
582  auto n = stack.back();
583  stack.pop_back();
584  for_each_successor(n, [&](const nodet &node) {
585  if(set.insert(node).second)
586  stack.push_back(node);
587  });
588  }
589 }
590 
596 template<class N>
597 std::vector<typename N::node_indext>
598 grapht<N>::get_reachable(node_indext src, bool forwards) const
599 {
600  std::vector<node_indext> src_vector;
601  src_vector.push_back(src);
602 
603  return get_reachable(src_vector, forwards);
604 }
605 
611 template <class N>
612 std::vector<typename N::node_indext> grapht<N>::get_reachable(
613  const std::vector<node_indext> &src,
614  bool forwards) const
615 {
616  std::vector<node_indext> result;
617  std::vector<bool> visited(size(), false);
618 
619  std::stack<node_indext, std::vector<node_indext>> s(src);
620 
621  while(!s.empty())
622  {
623  node_indext n = s.top();
624  s.pop();
625 
626  if(visited[n])
627  continue;
628 
629  result.push_back(n);
630  visited[n] = true;
631 
632  const auto &node = nodes[n];
633  const auto &succs = forwards ? node.out : node.in;
634  for(const auto succ : succs)
635  if(!visited[succ.first])
636  s.push(succ.first);
637  }
638 
639  return result;
640 }
641 
648 template <class N>
649 std::vector<typename N::node_indext> grapht<N>::depth_limited_search(
650  const typename N::node_indext src,
651  std::size_t limit) const
652 {
653  std::vector<node_indext> start_vector(1, src);
654  return depth_limited_search(start_vector, limit);
655 }
656 
663 template <class N>
664 std::vector<typename N::node_indext> grapht<N>::depth_limited_search(
665  std::vector<typename N::node_indext> &src,
666  std::size_t limit) const
667 {
668  std::vector<bool> visited(nodes.size(), false);
669 
670  for(const auto &node : src)
671  {
672  PRECONDITION(node < nodes.size());
673  visited[node] = true;
674  }
675 
676  return depth_limited_search(src, limit, visited);
677 }
678 
680 // from multiple source nodes, to find the nodes reachable within n steps
685 template <class N>
686 std::vector<typename N::node_indext> grapht<N>::depth_limited_search(
687  std::vector<typename N::node_indext> &src,
688  std::size_t limit,
689  std::vector<bool> &visited) const
690 {
691  if(limit == 0)
692  return src;
693 
694  std::vector<node_indext> next_ring;
695 
696  for(const auto &n : src)
697  {
698  for(const auto &o : nodes[n].out)
699  {
700  if(!visited[o.first])
701  {
702  next_ring.push_back(o.first);
703  visited[o.first] = true;
704  }
705  }
706  }
707 
708  if(next_ring.empty())
709  return src;
710 
711  limit--;
712 
713  for(const auto &succ : depth_limited_search(next_ring, limit, visited))
714  src.push_back(succ);
715 
716  return src;
717 }
718 
724 template<class N>
726  std::vector<node_indext> &subgraph_nr)
727 {
728  std::vector<bool> visited;
729 
730  visited.resize(nodes.size(), false);
731  subgraph_nr.resize(nodes.size(), 0);
732 
733  std::size_t nr=0;
734 
735  for(node_indext src=0; src<size(); src++)
736  {
737  if(visited[src])
738  continue;
739 
740  // DFS
741 
742  std::stack<node_indext> s;
743  s.push(src);
744 
745  while(!s.empty())
746  {
747  node_indext n=s.top();
748  s.pop();
749 
750  visited[n]=true;
751  subgraph_nr[n]=nr;
752 
753  const nodet &node=nodes[n];
754 
755  for(const auto &o : node.out)
756  {
757  if(!visited[o.first])
758  s.push(o.first);
759  }
760  }
761 
762  nr++;
763  }
764 
765  return nr;
766 }
767 
768 template<class N>
769 void grapht<N>::tarjan(tarjant &t, node_indext v) const
770 {
771  t.scc_stack.push(v);
772  t.in_scc[v]=true;
773  t.depth[v]=t.max_dfs;
774  t.lowlink[v]=t.max_dfs;
775  t.visited[v]=true;
776  t.max_dfs++;
777 
778  const nodet &node=nodes[v];
779  for(typename edgest::const_iterator
780  it=node.out.begin();
781  it!=node.out.end();
782  it++)
783  {
784  node_indext vp=it->first;
785  if(!t.visited[vp])
786  {
787  tarjan(t, vp);
788  t.lowlink[v]=std::min(t.lowlink[v], t.lowlink[vp]);
789  }
790  else if(t.in_scc[vp])
791  t.lowlink[v]=std::min(t.lowlink[v], t.depth[vp]);
792  }
793 
794  // check if root of SCC
795  if(t.lowlink[v]==t.depth[v])
796  {
797  while(true)
798  {
799  INVARIANT(
800  !t.scc_stack.empty(),
801  "stack of strongly connected components should have another component");
802  node_indext vp=t.scc_stack.top();
803  t.scc_stack.pop();
804  t.in_scc[vp]=false;
805  t.subgraph_nr[vp]=t.scc_count;
806  if(vp==v)
807  break;
808  }
809 
810  t.scc_count++;
811  }
812 }
813 
826 template<class N>
827 std::size_t grapht<N>::SCCs(std::vector<node_indext> &subgraph_nr) const
828 {
829  tarjant t(nodes.size(), subgraph_nr);
830 
831  for(node_indext v0=0; v0<size(); v0++)
832  if(!t.visited[v0])
833  tarjan(t, v0);
834 
835  return t.scc_count;
836 }
837 
842 template<class N>
844 {
845  grapht tmp(*this);
846 
847  // This assumes an undirected graph.
848  // 1. remove all nodes in tmp, reconnecting the remaining ones
849  // 2. the chordal graph is the old one plus the new edges
850 
851  for(node_indext i=0; i<tmp.size(); i++)
852  {
853  const nodet &n=tmp[i];
854 
855  // connect all the nodes in n.out with each other
856  for(const auto &o1 : n.out)
857  for(const auto &o2 : n.out)
858  {
859  if(o1.first!=o2.first)
860  {
861  tmp.add_undirected_edge(o1.first, o2.first);
862  this->add_undirected_edge(o1.first, o2.first);
863  }
864  }
865 
866  // remove node from tmp graph
867  tmp.remove_edges(i);
868  }
869 }
870 
873 template<class N>
874 std::list<typename grapht<N>::node_indext> grapht<N>::topsort() const
875 {
876  // list of topologically sorted nodes
877  std::list<node_indext> nodelist;
878  // queue of working set nodes with in-degree zero
879  std::queue<node_indext> indeg0_nodes;
880  // in-degree for each node
881  std::vector<size_t> in_deg(nodes.size(), 0);
882 
883  // abstract graph as in-degree of each node
884  for(node_indext idx=0; idx<nodes.size(); idx++)
885  {
886  in_deg[idx]=in(idx).size();
887  if(in_deg[idx]==0)
888  indeg0_nodes.push(idx);
889  }
890 
891  while(!indeg0_nodes.empty())
892  {
893  node_indext source=indeg0_nodes.front();
894  indeg0_nodes.pop();
895  nodelist.push_back(source);
896 
897  for(const auto &edge : out(source))
898  {
899  const node_indext target=edge.first;
900  INVARIANT(in_deg[target]!=0, "in-degree of node cannot be zero here");
901 
902  // remove edge from graph, by decrementing the in-degree of target
903  // outgoing edges from source will not be traversed again
904  in_deg[target]--;
905  if(in_deg[target]==0)
906  indeg0_nodes.push(target);
907  }
908  }
909 
910  // if all nodes are sorted, the graph is acyclic
911  // return empty list in case of cyclic graph
912  if(nodelist.size()!=nodes.size())
913  nodelist.clear();
914  return nodelist;
915 }
916 
917 template <typename node_index_type>
919  std::ostream &out,
920  const std::function<void(std::function<void(const node_index_type &)>)>
921  &for_each_node,
922  const std::function<
923  void(const node_index_type &, std::function<void(const node_index_type &)>)>
924  &for_each_succ,
925  const std::function<std::string(const node_index_type &)> node_to_string,
926  const std::function<std::string(const node_index_type &)> node_to_pretty)
927 {
928  for_each_node([&](const node_index_type &i) {
929  out << node_to_pretty(i) << ";\n";
930  for_each_succ(i, [&](const node_index_type &n) {
931  out << node_to_string(i) << " -> " << node_to_string(n) << '\n';
932  });
933  });
934 }
935 
936 template <class N>
937 std::vector<typename grapht<N>::node_indext>
939 {
940  std::vector<node_indext> result;
941  std::transform(
942  nodes[n].out.begin(),
943  nodes[n].out.end(),
944  std::back_inserter(result),
945  [&](const std::pair<node_indext, edget> &edge) { return edge.first; });
946  return result;
947 }
948 
949 template <class N>
951  const node_indext &n,
952  std::function<void(const node_indext &)> f) const
953 {
954  std::for_each(
955  nodes[n].out.begin(),
956  nodes[n].out.end(),
957  [&](const std::pair<node_indext, edget> &edge) { f(edge.first); });
958 }
959 
960 template <class N>
961 void grapht<N>::output_dot(std::ostream &out) const
962 {
963  const auto for_each_node =
964  [this](const std::function<void(const node_indext &)> &f) {
965  for(node_indext i = 0; i < nodes.size(); ++i)
966  f(i);
967  };
968 
969  const auto for_each_succ = [&](
970  const node_indext &i, const std::function<void(const node_indext &)> &f) {
971  for_each_successor(i, f);
972  };
973 
974  const auto to_string = [](const node_indext &i) { return std::to_string(i); };
975  const auto to_pretty_string = [this](const node_indext &i) {
976  return nodes[i].pretty(i);
977  };
978  output_dot_generic<node_indext>(
979  out, for_each_node, for_each_succ, to_string, to_pretty_string);
980 }
981 
982 #endif // CPROVER_UTIL_GRAPH_H
void remove_in_edges(node_indext n)
Definition: graph.h:385
std::size_t max_dfs
Definition: graph.h:337
A generic directed graph with a parametric node type.
Definition: graph.h:167
std::string pretty(const node_indext &idx) const
Definition: graph.h:87
visited_nodet()
Definition: graph.h:109
nodest nodes
Definition: graph.h:177
std::vector< unsigned > lowlink
Definition: graph.h:332
void clear()
Definition: graph.h:260
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:827
void add_undirected_edge(node_indext a, node_indext b)
Definition: graph.h:361
std::string to_string(const string_not_contains_constraintt &expr)
Used for debug printing.
A node type with an extra bit.
Definition: graph.h:101
std::size_t connected_subgraphs(std::vector< node_indext > &subgraph_nr)
Find connected subgraphs in an undirected graph.
Definition: graph.h:725
bool is_dag() const
Definition: graph.h:308
void visit_reachable(node_indext src)
Definition: graph.h:507
#define INVARIANT(CONDITION, REASON)
This macro uses the wrapper function &#39;invariant_violated_string&#39;.
Definition: invariant.h:400
edgest in
Definition: graph.h:43
void shortest_path(node_indext src, node_indext dest, patht &path) const
Definition: graph.h:267
bool has_edge(node_indext i, node_indext j) const
Definition: graph.h:192
edgest out
Definition: graph.h:43
void remove_edges(node_indext n)
Definition: graph.h:254
nodet::edget edget
Definition: graph.h:173
void erase_in(node_indext n)
Definition: graph.h:55
std::vector< bool > visited
Definition: graph.h:330
N nodet
Definition: graph.h:170
bool visited
Definition: graph.h:107
const edgest & out(node_indext n) const
Definition: graph.h:227
std::list< path_nodet > patht
Definition: path.h:45
bool empty() const
Definition: graph.h:217
#define PRECONDITION(CONDITION)
Definition: invariant.h:438
std::vector< bool > in_scc
Definition: graph.h:333
std::size_t size() const
Definition: graph.h:212
std::list< node_indext > patht
Definition: graph.h:265
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:874
nodet::node_indext node_indext
Definition: graph.h:174
void remove_undirected_edge(node_indext a, node_indext b)
Definition: graph.h:374
std::vector< node_indext > get_successors(const node_indext &n) const
Definition: graph.h:938
void add_in(node_indext n)
Definition: graph.h:45
edget & edge(node_indext a, node_indext b)
Definition: graph.h:244
std::size_t node_indext
Definition: graph.h:38
void output_dot(std::ostream &out) const
Definition: graph.h:961
std::map< node_indext, edget > edgest
Definition: graph.h:41
void tarjan(class tarjant &t, node_indext v) const
Definition: graph.h:769
void make_chordal()
Ensure a graph is chordal (contains no 4+-cycles without an edge crossing the cycle) by adding extra ...
Definition: graph.h:843
void erase_out(node_indext n)
Definition: graph.h:60
void remove_edge(node_indext a, node_indext b)
Definition: graph.h:238
const nodet & operator[](node_indext n) const
Definition: graph.h:197
std::size_t scc_count
Definition: graph.h:337
std::vector< node_indext > & subgraph_nr
Definition: graph.h:335
node_indext add_node()
Definition: graph.h:180
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:649
void for_each_successor(const node_indext &n, std::function< void(const node_indext &)> f) const
Definition: graph.h:950
void remove_out_edges(node_indext n)
Definition: graph.h:400
std::stack< node_indext > scc_stack
Definition: graph.h:334
nodet::edgest edgest
Definition: graph.h:171
void shortest_loop(node_indext node, patht &path) const
Definition: graph.h:275
void add_edge(node_indext a, node_indext b)
Definition: graph.h:232
virtual ~graph_nodet()
Definition: graph.h:94
std::vector< unsigned > depth
Definition: graph.h:331
void add_out(node_indext n)
Definition: graph.h:50
const edgest & in(node_indext n) const
Definition: graph.h:222
void swap(grapht &other)
Definition: graph.h:187
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:116
std::vector< nodet > nodest
Definition: graph.h:172
tarjant(std::size_t n, std::vector< node_indext > &_subgraph_nr)
Definition: graph.h:339
void resize(node_indext s)
Definition: graph.h:207
virtual std::string dot_attributes(const node_indext &) const
Node with attributes suitable for Graphviz DOT format.
Definition: graph.h:81
E edget
Definition: graph.h:40
nodet & operator[](node_indext n)
Definition: graph.h:202
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: graph.h:918
graph_nodet< E >::edgest edgest
Definition: graph.h:105
#define stack(x)
Definition: parser.h:144
This class represents a node in a directed graph.
Definition: graph.h:35
graph_nodet< E >::edget edget
Definition: graph.h:104
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:598
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:569
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:523