COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/path_dump.h @ 2335:27aa03cd3121

Last change on this file since 2335:27aa03cd3121 was 2335:27aa03cd3121, checked in by Balazs Dezso, 13 years ago

New path concept and path structures

TODO: BellmanFord::negativeCycle()

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