File: cycle_detector.hh

package info (click to toggle)
monotone 0.48-3
  • links: PTS
  • area: main
  • in suites: squeeze
  • size: 20,096 kB
  • ctags: 8,077
  • sloc: cpp: 81,000; sh: 6,402; perl: 1,241; lisp: 1,045; makefile: 655; python: 566; sql: 112; ansic: 52
file content (100 lines) | stat: -rw-r--r-- 2,567 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// Copyright (C) 2002 Graydon Hoare <graydon@pobox.com>
//
// This program is made available under the GNU GPL version 2.0 or
// greater. See the accompanying file COPYING for details.
//
// This program is distributed WITHOUT ANY WARRANTY; without even the
// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
// PURPOSE.

#ifndef __CYCLE_DETECTOR_HH__
#define __CYCLE_DETECTOR_HH__

#include "vector.hh"
#include <stack>
#include <set>

#include "quick_alloc.hh"
#include "sanity.hh"

template <typename T>
struct cycle_detector
{

  typedef std::vector< T > edge_vec;
  typedef std::vector <edge_vec > edge_map;
  typedef std::pair <typename edge_vec::const_iterator,
                     typename edge_vec::const_iterator> state;
  typedef std::stack <state > edge_stack;

  edge_map edges;
  edge_stack stk;
  std::set<T> global_in_edges;

  void put_edge (T const & src, T const & dst)
  {
    if (src >= edges.size())
      edges.resize(src + 1);
    edge_vec & src_edges = edges.at(src);
    for (typename edge_vec::const_iterator i = src_edges.begin();
         i != src_edges.end(); ++i)
      if (*i == dst)
        return;
    src_edges.push_back(dst);
    global_in_edges.insert(dst);
  }


  bool edge_makes_cycle(T const & src, T const & dst)
  {
    if (src == dst)
        return true;

    if (dst >= edges.size() || edges.at(dst).empty())
        return false;

    if (global_in_edges.find(src) == global_in_edges.end())
        return false;

    while (!stk.empty())
      stk.pop();

    stk.push(make_pair(edges.at(dst).begin(),
                       edges.at(dst).end()));

    std::set<T> visited;
    while (!stk.empty())
      {
        bool pushed = false;
        for (state & curr = stk.top(); curr.first != curr.second && !pushed; ++curr.first)
          {
            T val = *(curr.first);
            if (val == src)
              {
                return true;
              }
            if (val < edges.size() && ! edges.at(val).empty()
                && visited.find(val) == visited.end())
              {
                visited.insert(val);
                stk.push(make_pair(edges.at(val).begin(),
                                   edges.at(val).end()));
                pushed = true;
              }
          }
        if (!pushed)
            stk.pop();
      }
    return false;
  }
};

#endif // __CYCLE_DETECTOR_HH__

// Local Variables:
// mode: C++
// fill-column: 76
// c-file-style: "gnu"
// indent-tabs-mode: nil
// End:
// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s: