monotone

monotone Mtn Source Tree

Root/cycle_detector.hh

1#ifndef __CYCLE_DETECTOR_HH__
2#define __CYCLE_DETECTOR_HH__
3
4// copyright (C) 2002, 2003 graydon hoare <graydon@pobox.com>
5// all rights reserved.
6// licensed to the public under the terms of the GNU GPL (>= 2)
7// see the file COPYING for details
8
9#include <vector>
10#include <stack>
11#include <set>
12
13#include "quick_alloc.hh"
14#include "sanity.hh"
15
16template <typename T>
17struct cycle_detector
18{
19
20 typedef std::vector< T > edge_vec;
21 typedef std::vector <edge_vec > edge_map;
22 typedef std::pair <typename edge_vec::const_iterator,
23 typename edge_vec::const_iterator> state;
24 typedef std::stack <state > edge_stack;
25
26 edge_map edges;
27 edge_stack stk;
28 std::set<T> global_in_edges;
29
30 void put_edge (T const & src, T const & dst)
31 {
32 if (src >= edges.size())
33 edges.resize(src + 1);
34 edge_vec & src_edges = edges.at(src);
35 for (typename edge_vec::const_iterator i = src_edges.begin();
36 i != src_edges.end(); ++i)
37 if (*i == dst)
38return;
39 src_edges.push_back(dst);
40 global_in_edges.insert(dst);
41 }
42
43
44 bool edge_makes_cycle(T const & src, T const & dst)
45 {
46 if (src == dst)
47return true;
48
49 if (dst >= edges.size() || edges.at(dst).empty())
50return false;
51
52 if (global_in_edges.find(src) == global_in_edges.end())
53return false;
54
55 while (!stk.empty())
56 stk.pop();
57
58 stk.push(make_pair(edges.at(dst).begin(),
59 edges.at(dst).end()));
60
61 std::set<T> visited;
62 while (!stk.empty())
63 {
64bool pushed = false;
65for (state & curr = stk.top(); curr.first != curr.second && !pushed; ++curr.first)
66 {
67 T val = *(curr.first);
68 if (val == src)
69 {
70return true;
71 }
72 if (val < edges.size() && ! edges.at(val).empty()
73&& visited.find(val) == visited.end())
74 {
75visited.insert(val);
76stk.push(make_pair(edges.at(val).begin(),
77 edges.at(val).end()));
78pushed = true;
79 }
80 }
81if (!pushed)
82 stk.pop();
83 }
84 return false;
85 }
86};
87
88#endif // __CYCLE_DETECTOR_HH__

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status