deba@2335: /* -*- C++ -*-
deba@2335:  *
deba@2335:  * This file is a part of LEMON, a generic C++ optimization library
deba@2335:  *
alpar@2553:  * Copyright (C) 2003-2008
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 <typename _Graph, typename _PredMap>
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 <typename _Graph, typename _PredMatrixMap>
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