monotone

monotone Mtn Source Tree

Root/cycle_detector.hh

1#ifndef __CYCLE_DETECTOR_HH__
2#define __CYCLE_DETECTOR_HH__
3
4// Copyright (C) 2002 Graydon Hoare <graydon@pobox.com>
5//
6// This program is made available under the GNU GPL version 2.0 or
7// greater. See the accompanying file COPYING for details.
8//
9// This program is distributed WITHOUT ANY WARRANTY; without even the
10// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
11// PURPOSE.
12
13#include "vector.hh"
14#include <stack>
15#include <set>
16
17#include "quick_alloc.hh"
18#include "sanity.hh"
19
20template <typename T>
21struct cycle_detector
22{
23
24 typedef std::vector< T > edge_vec;
25 typedef std::vector <edge_vec > edge_map;
26 typedef std::pair <typename edge_vec::const_iterator,
27 typename edge_vec::const_iterator> state;
28 typedef std::stack <state > edge_stack;
29
30 edge_map edges;
31 edge_stack stk;
32 std::set<T> global_in_edges;
33
34 void put_edge (T const & src, T const & dst)
35 {
36 if (src >= edges.size())
37 edges.resize(src + 1);
38 edge_vec & src_edges = edges.at(src);
39 for (typename edge_vec::const_iterator i = src_edges.begin();
40 i != src_edges.end(); ++i)
41 if (*i == dst)
42 return;
43 src_edges.push_back(dst);
44 global_in_edges.insert(dst);
45 }
46
47
48 bool edge_makes_cycle(T const & src, T const & dst)
49 {
50 if (src == dst)
51 return true;
52
53 if (dst >= edges.size() || edges.at(dst).empty())
54 return false;
55
56 if (global_in_edges.find(src) == global_in_edges.end())
57 return false;
58
59 while (!stk.empty())
60 stk.pop();
61
62 stk.push(make_pair(edges.at(dst).begin(),
63 edges.at(dst).end()));
64
65 std::set<T> visited;
66 while (!stk.empty())
67 {
68 bool pushed = false;
69 for (state & curr = stk.top(); curr.first != curr.second && !pushed; ++curr.first)
70 {
71 T val = *(curr.first);
72 if (val == src)
73 {
74 return true;
75 }
76 if (val < edges.size() && ! edges.at(val).empty()
77 && visited.find(val) == visited.end())
78 {
79 visited.insert(val);
80 stk.push(make_pair(edges.at(val).begin(),
81 edges.at(val).end()));
82 pushed = true;
83 }
84 }
85 if (!pushed)
86 stk.pop();
87 }
88 return false;
89 }
90};
91
92// Local Variables:
93// mode: C++
94// fill-column: 76
95// c-file-style: "gnu"
96// indent-tabs-mode: nil
97// End:
98// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:
99
100#endif // __CYCLE_DETECTOR_HH__

Archive Download this file

Branches

Tags

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