COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/path_dump.h @ 519:c786cd201266

Last change on this file since 519:c786cd201266 was 519:c786cd201266, checked in by Balazs Dezso <deba@…>, 15 years ago

Fix several missing includes (#232)

File size: 4.5 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
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
22#include <lemon/core.h>
23#include <lemon/concept_check.h>
24
25namespace lemon {
26
27  template <typename _Digraph, typename _PredMap>
28  class PredMapPath {
29  public:
30    typedef True RevPathTag;
31
32    typedef _Digraph Digraph;
33    typedef typename Digraph::Arc Arc;
34    typedef _PredMap PredMap;
35
36    PredMapPath(const Digraph& _digraph, const PredMap& _predMap,
37                typename Digraph::Node _target)
38      : digraph(_digraph), predMap(_predMap), target(_target) {}
39
40    int length() const {
41      int len = 0;
42      typename Digraph::Node node = target;
43      typename Digraph::Arc arc;
44      while ((arc = predMap[node]) != INVALID) {
45        node = digraph.source(arc);
46        ++len;
47      }
48      return len;
49    }
50
51    bool empty() const {
52      return predMap[target] != INVALID;
53    }
54
55    class RevArcIt {
56    public:
57      RevArcIt() {}
58      RevArcIt(Invalid) : path(0), current(INVALID) {}
59      RevArcIt(const PredMapPath& _path)
60        : path(&_path), current(_path.target) {
61        if (path->predMap[current] == INVALID) current = INVALID;
62      }
63
64      operator const typename Digraph::Arc() const {
65        return path->predMap[current];
66      }
67
68      RevArcIt& operator++() {
69        current = path->digraph.source(path->predMap[current]);
70        if (path->predMap[current] == INVALID) current = INVALID;
71        return *this;
72      }
73
74      bool operator==(const RevArcIt& e) const {
75        return current == e.current;
76      }
77
78      bool operator!=(const RevArcIt& e) const {
79        return current != e.current;
80      }
81
82      bool operator<(const RevArcIt& e) const {
83        return current < e.current;
84      }
85
86    private:
87      const PredMapPath* path;
88      typename Digraph::Node current;
89    };
90
91  private:
92    const Digraph& digraph;
93    const PredMap& predMap;
94    typename Digraph::Node target;
95  };
96
97
98  template <typename _Digraph, typename _PredMatrixMap>
99  class PredMatrixMapPath {
100  public:
101    typedef True RevPathTag;
102
103    typedef _Digraph Digraph;
104    typedef typename Digraph::Arc Arc;
105    typedef _PredMatrixMap PredMatrixMap;
106
107    PredMatrixMapPath(const Digraph& _digraph,
108                      const PredMatrixMap& _predMatrixMap,
109                      typename Digraph::Node _source,
110                      typename Digraph::Node _target)
111      : digraph(_digraph), predMatrixMap(_predMatrixMap),
112        source(_source), target(_target) {}
113
114    int length() const {
115      int len = 0;
116      typename Digraph::Node node = target;
117      typename Digraph::Arc arc;
118      while ((arc = predMatrixMap(source, node)) != INVALID) {
119        node = digraph.source(arc);
120        ++len;
121      }
122      return len;
123    }
124
125    bool empty() const {
126      return source != target;
127    }
128
129    class RevArcIt {
130    public:
131      RevArcIt() {}
132      RevArcIt(Invalid) : path(0), current(INVALID) {}
133      RevArcIt(const PredMatrixMapPath& _path)
134        : path(&_path), current(_path.target) {
135        if (path->predMatrixMap(path->source, current) == INVALID)
136          current = INVALID;
137      }
138
139      operator const typename Digraph::Arc() const {
140        return path->predMatrixMap(path->source, current);
141      }
142
143      RevArcIt& operator++() {
144        current =
145          path->digraph.source(path->predMatrixMap(path->source, current));
146        if (path->predMatrixMap(path->source, current) == INVALID)
147          current = INVALID;
148        return *this;
149      }
150
151      bool operator==(const RevArcIt& e) const {
152        return current == e.current;
153      }
154
155      bool operator!=(const RevArcIt& e) const {
156        return current != e.current;
157      }
158
159      bool operator<(const RevArcIt& e) const {
160        return current < e.current;
161      }
162
163    private:
164      const PredMatrixMapPath* path;
165      typename Digraph::Node current;
166    };
167
168  private:
169    const Digraph& digraph;
170    const PredMatrixMap& predMatrixMap;
171    typename Digraph::Node source;
172    typename Digraph::Node target;
173  };
174
175}
176
177#endif
Note: See TracBrowser for help on using the repository browser.