1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_BITS_PRED_MAP_PATH_H
20 #define LEMON_BITS_PRED_MAP_PATH_H
24 template <typename _Digraph, typename _PredMap>
27 typedef True RevPathTag;
29 typedef _Digraph Digraph;
30 typedef typename Digraph::Arc Arc;
31 typedef _PredMap PredMap;
33 PredMapPath(const Digraph& _digraph, const PredMap& _predMap,
34 typename Digraph::Node _target)
35 : digraph(_digraph), predMap(_predMap), target(_target) {}
39 typename Digraph::Node node = target;
40 typename Digraph::Arc arc;
41 while ((arc = predMap[node]) != INVALID) {
42 node = digraph.source(arc);
49 return predMap[target] != INVALID;
55 RevArcIt(Invalid) : path(0), current(INVALID) {}
56 RevArcIt(const PredMapPath& _path)
57 : path(&_path), current(_path.target) {
58 if (path->predMap[current] == INVALID) current = INVALID;
61 operator const typename Digraph::Arc() const {
62 return path->predMap[current];
65 RevArcIt& operator++() {
66 current = path->digraph.source(path->predMap[current]);
67 if (path->predMap[current] == INVALID) current = INVALID;
71 bool operator==(const RevArcIt& e) const {
72 return current == e.current;
75 bool operator!=(const RevArcIt& e) const {
76 return current != e.current;
79 bool operator<(const RevArcIt& e) const {
80 return current < e.current;
84 const PredMapPath* path;
85 typename Digraph::Node current;
89 const Digraph& digraph;
90 const PredMap& predMap;
91 typename Digraph::Node target;
95 template <typename _Digraph, typename _PredMatrixMap>
96 class PredMatrixMapPath {
98 typedef True RevPathTag;
100 typedef _Digraph Digraph;
101 typedef typename Digraph::Arc Arc;
102 typedef _PredMatrixMap PredMatrixMap;
104 PredMatrixMapPath(const Digraph& _digraph,
105 const PredMatrixMap& _predMatrixMap,
106 typename Digraph::Node _source,
107 typename Digraph::Node _target)
108 : digraph(_digraph), predMatrixMap(_predMatrixMap),
109 source(_source), target(_target) {}
113 typename Digraph::Node node = target;
114 typename Digraph::Arc arc;
115 while ((arc = predMatrixMap(source, node)) != INVALID) {
116 node = digraph.source(arc);
123 return source != target;
129 RevArcIt(Invalid) : path(0), current(INVALID) {}
130 RevArcIt(const PredMatrixMapPath& _path)
131 : path(&_path), current(_path.target) {
132 if (path->predMatrixMap(path->source, current) == INVALID)
136 operator const typename Digraph::Arc() const {
137 return path->predMatrixMap(path->source, current);
140 RevArcIt& operator++() {
142 path->digraph.source(path->predMatrixMap(path->source, current));
143 if (path->predMatrixMap(path->source, current) == INVALID)
148 bool operator==(const RevArcIt& e) const {
149 return current == e.current;
152 bool operator!=(const RevArcIt& e) const {
153 return current != e.current;
156 bool operator<(const RevArcIt& e) const {
157 return current < e.current;
161 const PredMatrixMapPath* path;
162 typename Digraph::Node current;
166 const Digraph& digraph;
167 const PredMatrixMap& predMatrixMap;
168 typename Digraph::Node source;
169 typename Digraph::Node target;