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