COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/path_dump.h @ 2357:5365600a7a5c

Last change on this file since 2357:5365600a7a5c was 2357:5365600a7a5c, checked in by Balazs Dezso, 16 years ago

Some bug fix
RevIt? => RevEdgeIt? renaming

File size: 4.3 KB
Line 
1
2/* -*- C++ -*-
3 *
4 * This file is a part of LEMON, a generic C++ optimization library
5 *
6 * Copyright (C) 2003-2006
7 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
8 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 *
10 * Permission to use, modify and distribute this software is granted
11 * provided that this copyright notice appears in all copies. For
12 * precise terms see the accompanying LICENSE file.
13 *
14 * This software is provided "AS IS" with no warranty of any kind,
15 * express or implied, and with no claim as to its suitability for any
16 * purpose.
17 *
18 */
19
20#ifndef LEMON_BITS_PRED_MAP_PATH_H
21#define LEMON_BITS_PRED_MAP_PATH_H
22
23namespace lemon {
24
25  template <typename _Graph, typename _PredMap>
26  class PredMapPath {
27  public:
28    typedef True RevPathTag;
29
30    typedef _Graph Graph;
31    typedef typename Graph::Edge Edge;
32    typedef _PredMap PredMap;
33
34    PredMapPath(const Graph& _graph, const PredMap& _predMap,
35                typename Graph::Node _target)
36      : graph(_graph), predMap(_predMap), target(_target) {}
37
38    int length() const {
39      int len = 0;
40      typename Graph::Node node = target;
41      typename Graph::Edge edge;
42      while ((edge = predMap[node]) != INVALID) {
43        node = graph.source(edge);
44        ++len;
45      }
46      return len;
47    }
48
49    bool empty() const {
50      return predMap[target] != INVALID;
51    }
52
53    class RevEdgeIt {
54    public:
55      RevEdgeIt() {}
56      RevEdgeIt(Invalid) : path(0), current(INVALID) {}
57      RevEdgeIt(const PredMapPath& _path)
58        : path(&_path), current(_path.target) {}
59
60      operator const typename Graph::Edge() const {
61        return path->predMap[current];
62      }
63
64      RevEdgeIt& operator++() {
65        current = path->graph.source(path->predMap[current]);
66        if (path->predMap[current] == INVALID) current = INVALID;
67        return *this;
68      }
69
70      bool operator==(const RevEdgeIt& e) const {
71        return current == e.current;
72      }
73
74      bool operator!=(const RevEdgeIt& e) const {
75        return current != e.current;
76      }
77
78      bool operator<(const RevEdgeIt& e) const {
79        return current < e.current;
80      }
81     
82    private:
83      const PredMapPath* path;
84      typename Graph::Node current;
85    };
86
87  private:
88    const Graph& graph;
89    const PredMap& predMap;
90    typename Graph::Node target;
91  };
92
93
94  template <typename _Graph, typename _PredMatrixMap>
95  class PredMatrixMapPath {
96  public:
97    typedef True RevPathTag;
98
99    typedef _Graph Graph;
100    typedef typename Graph::Edge Edge;
101    typedef _PredMatrixMap PredMatrixMap;
102
103    PredMatrixMapPath(const Graph& _graph,
104                      const PredMatrixMap& _predMatrixMap,
105                      typename Graph::Node _source,
106                      typename Graph::Node _target)
107      : graph(_graph), predMatrixMap(_predMatrixMap),
108        source(_source), target(_target) {}
109
110    int length() const {
111      int len = 0;
112      typename Graph::Node node = target;
113      typename Graph::Edge edge;
114      while ((edge = predMatrixMap(source, node)) != INVALID) {
115        node = graph.source(edge);
116        ++len;
117      }
118      return len;
119    }
120
121    bool empty() const {
122      return source != target;
123    }
124
125    class RevEdgeIt {
126    public:
127      RevEdgeIt() {}
128      RevEdgeIt(Invalid) : path(0), current(INVALID) {}
129      RevEdgeIt(const PredMatrixMapPath& _path)
130        : path(&_path), current(_path.target) {}
131
132      operator const typename Graph::Edge() const {
133        return path->predMatrixMap(path->source, current);
134      }
135
136      RevEdgeIt& operator++() {
137        current =
138          path->graph.source(path->predMatrixMap(path->source, current));
139        if (path->predMatrixMap(path->source, current) == INVALID)
140          current = INVALID;
141        return *this;
142      }
143
144      bool operator==(const RevEdgeIt& e) const {
145        return current == e.current;
146      }
147
148      bool operator!=(const RevEdgeIt& e) const {
149        return current != e.current;
150      }
151
152      bool operator<(const RevEdgeIt& e) const {
153        return current < e.current;
154      }
155     
156    private:
157      const PredMatrixMapPath* path;
158      typename Graph::Node current;
159    };
160
161  private:
162    const Graph& graph;
163    const PredMatrixMap& predMatrixMap;
164    typename Graph::Node source;
165    typename Graph::Node target;
166  };
167
168}
169
170#endif
Note: See TracBrowser for help on using the repository browser.