alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- alpar@100: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. alpar@100: * alpar@440: * Copyright (C) 2003-2009 alpar@100: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@100: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@100: * alpar@100: * Permission to use, modify and distribute this software is granted alpar@100: * provided that this copyright notice appears in all copies. For alpar@100: * precise terms see the accompanying LICENSE file. alpar@100: * alpar@100: * This software is provided "AS IS" with no warranty of any kind, alpar@100: * express or implied, and with no claim as to its suitability for any alpar@100: * purpose. alpar@100: * alpar@100: */ alpar@100: alpar@100: #ifndef LEMON_BITS_PRED_MAP_PATH_H alpar@100: #define LEMON_BITS_PRED_MAP_PATH_H alpar@100: deba@519: #include deba@519: #include deba@519: alpar@100: namespace lemon { alpar@100: alpar@100: template alpar@100: class PredMapPath { alpar@100: public: alpar@100: typedef True RevPathTag; alpar@100: alpar@100: typedef _Digraph Digraph; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef _PredMap PredMap; alpar@100: alpar@100: PredMapPath(const Digraph& _digraph, const PredMap& _predMap, alpar@100: typename Digraph::Node _target) alpar@100: : digraph(_digraph), predMap(_predMap), target(_target) {} alpar@100: alpar@100: int length() const { alpar@100: int len = 0; alpar@100: typename Digraph::Node node = target; alpar@100: typename Digraph::Arc arc; alpar@100: while ((arc = predMap[node]) != INVALID) { alpar@100: node = digraph.source(arc); alpar@100: ++len; alpar@100: } alpar@100: return len; alpar@100: } alpar@100: alpar@100: bool empty() const { alpar@100: return predMap[target] != INVALID; alpar@100: } alpar@100: alpar@100: class RevArcIt { alpar@100: public: alpar@100: RevArcIt() {} alpar@100: RevArcIt(Invalid) : path(0), current(INVALID) {} alpar@209: RevArcIt(const PredMapPath& _path) alpar@100: : path(&_path), current(_path.target) { alpar@100: if (path->predMap[current] == INVALID) current = INVALID; alpar@100: } alpar@100: alpar@100: operator const typename Digraph::Arc() const { alpar@100: return path->predMap[current]; alpar@100: } alpar@100: alpar@100: RevArcIt& operator++() { alpar@100: current = path->digraph.source(path->predMap[current]); alpar@100: if (path->predMap[current] == INVALID) current = INVALID; alpar@100: return *this; alpar@100: } alpar@100: alpar@209: bool operator==(const RevArcIt& e) const { alpar@209: return current == e.current; alpar@100: } alpar@100: alpar@100: bool operator!=(const RevArcIt& e) const { alpar@209: return current != e.current; alpar@100: } alpar@100: alpar@209: bool operator<(const RevArcIt& e) const { alpar@209: return current < e.current; alpar@100: } alpar@209: alpar@100: private: alpar@100: const PredMapPath* path; alpar@100: typename Digraph::Node current; alpar@100: }; alpar@100: alpar@100: private: alpar@100: const Digraph& digraph; alpar@100: const PredMap& predMap; alpar@100: typename Digraph::Node target; alpar@100: }; alpar@100: alpar@100: alpar@100: template alpar@100: class PredMatrixMapPath { alpar@100: public: alpar@100: typedef True RevPathTag; alpar@100: alpar@100: typedef _Digraph Digraph; alpar@100: typedef typename Digraph::Arc Arc; alpar@100: typedef _PredMatrixMap PredMatrixMap; alpar@100: alpar@209: PredMatrixMapPath(const Digraph& _digraph, alpar@100: const PredMatrixMap& _predMatrixMap, alpar@209: typename Digraph::Node _source, alpar@100: typename Digraph::Node _target) alpar@209: : digraph(_digraph), predMatrixMap(_predMatrixMap), alpar@100: source(_source), target(_target) {} alpar@100: alpar@100: int length() const { alpar@100: int len = 0; alpar@100: typename Digraph::Node node = target; alpar@100: typename Digraph::Arc arc; alpar@100: while ((arc = predMatrixMap(source, node)) != INVALID) { alpar@100: node = digraph.source(arc); alpar@100: ++len; alpar@100: } alpar@100: return len; alpar@100: } alpar@100: alpar@100: bool empty() const { alpar@100: return source != target; alpar@100: } alpar@100: alpar@100: class RevArcIt { alpar@100: public: alpar@100: RevArcIt() {} alpar@100: RevArcIt(Invalid) : path(0), current(INVALID) {} alpar@209: RevArcIt(const PredMatrixMapPath& _path) alpar@100: : path(&_path), current(_path.target) { alpar@209: if (path->predMatrixMap(path->source, current) == INVALID) alpar@100: current = INVALID; alpar@100: } alpar@100: alpar@100: operator const typename Digraph::Arc() const { alpar@100: return path->predMatrixMap(path->source, current); alpar@100: } alpar@100: alpar@100: RevArcIt& operator++() { alpar@209: current = alpar@100: path->digraph.source(path->predMatrixMap(path->source, current)); alpar@209: if (path->predMatrixMap(path->source, current) == INVALID) alpar@100: current = INVALID; alpar@100: return *this; alpar@100: } alpar@100: alpar@209: bool operator==(const RevArcIt& e) const { alpar@209: return current == e.current; alpar@100: } alpar@100: alpar@100: bool operator!=(const RevArcIt& e) const { alpar@209: return current != e.current; alpar@100: } alpar@100: alpar@209: bool operator<(const RevArcIt& e) const { alpar@209: return current < e.current; alpar@100: } alpar@209: alpar@100: private: alpar@100: const PredMatrixMapPath* path; alpar@100: typename Digraph::Node current; alpar@100: }; alpar@100: alpar@100: private: alpar@100: const Digraph& digraph; alpar@100: const PredMatrixMap& predMatrixMap; alpar@100: typename Digraph::Node source; alpar@100: typename Digraph::Node target; alpar@100: }; alpar@100: alpar@100: } alpar@100: alpar@100: #endif