lemon-0.x: lemon/bits/path_dump.h@df6a32249b46

     2 /* -*- C++ -*-

     3  *

     4  * This file is a part of LEMON, a generic C++ optimization library

     5  *

     6  * Copyright (C) 2003-2006

     7  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     8  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     9  *

    10  * Permission to use, modify and distribute this software is granted

    11  * provided that this copyright notice appears in all copies. For

    12  * precise terms see the accompanying LICENSE file.

    13  *

    14  * This software is provided "AS IS" with no warranty of any kind,

    15  * express or implied, and with no claim as to its suitability for any

    16  * purpose.

    17  *

    18  */

    20 #ifndef LEMON_BITS_PRED_MAP_PATH_H

    21 #define LEMON_BITS_PRED_MAP_PATH_H

    23 namespace lemon {

    25   template <typename _Graph, typename _PredMap>

    26   class PredMapPath {

    27   public:

    28     typedef True RevPathTag;

    30     typedef _Graph Graph;

    31     typedef typename Graph::Edge Edge;

    32     typedef _PredMap PredMap;

    34     PredMapPath(const Graph& _graph, const PredMap& _predMap,

    35                 typename Graph::Node _target)

    36       : graph(_graph), predMap(_predMap), target(_target) {}

    38     int length() const {

    39       int len = 0;

    40       typename Graph::Node node = target;

    41       typename Graph::Edge edge;

    42       while ((edge = predMap[node]) != INVALID) {

    43         node = graph.source(edge);

    44         ++len;

    45       }

    46       return len;

    47     }

    49     bool empty() const {

    50       return predMap[target] != INVALID;

    51     }

    53     class RevEdgeIt {

    54     public:

    55       RevEdgeIt() {}

    56       RevEdgeIt(Invalid) : path(0), current(INVALID) {}

    57       RevEdgeIt(const PredMapPath& _path)

    58         : path(&_path), current(_path.target) {}

    60       operator const typename Graph::Edge() const {

    61         return path->predMap[current];

    62       }

    64       RevEdgeIt& operator++() {

    65         current = path->graph.source(path->predMap[current]);

    66         if (path->predMap[current] == INVALID) current = INVALID;

    67         return *this;

    68       }

    70       bool operator==(const RevEdgeIt& e) const {

    71         return current == e.current;

    72       }

    74       bool operator!=(const RevEdgeIt& e) const {

    75         return current != e.current;

    76       }

    78       bool operator<(const RevEdgeIt& e) const {

    79         return current < e.current;

    80       }

    82     private:

    83       const PredMapPath* path;

    84       typename Graph::Node current;

    85     };

    87   private:

    88     const Graph& graph;

    89     const PredMap& predMap;

    90     typename Graph::Node target;

    91   };

    94   template <typename _Graph, typename _PredMatrixMap>

    95   class PredMatrixMapPath {

    96   public:

    97     typedef True RevPathTag;

    99     typedef _Graph Graph;

   100     typedef typename Graph::Edge Edge;

   101     typedef _PredMatrixMap PredMatrixMap;

   103     PredMatrixMapPath(const Graph& _graph,

   104                       const PredMatrixMap& _predMatrixMap,

   105                       typename Graph::Node _source,

   106                       typename Graph::Node _target)

   107       : graph(_graph), predMatrixMap(_predMatrixMap),

   108         source(_source), target(_target) {}

   110     int length() const {

   111       int len = 0;

   112       typename Graph::Node node = target;

   113       typename Graph::Edge edge;

   114       while ((edge = predMatrixMap(source, node)) != INVALID) {

   115         node = graph.source(edge);

   116         ++len;

   117       }

   118       return len;

   119     }

   121     bool empty() const {

   122       return source != target;

   123     }

   125     class RevEdgeIt {

   126     public:

   127       RevEdgeIt() {}

   128       RevEdgeIt(Invalid) : path(0), current(INVALID) {}

   129       RevEdgeIt(const PredMatrixMapPath& _path)

   130         : path(&_path), current(_path.target) {}

   132       operator const typename Graph::Edge() const {

   133         return path->predMatrixMap(path->source, current);

   134       }

   136       RevEdgeIt& operator++() {

   137         current =

   138           path->graph.source(path->predMatrixMap(path->source, current));

   139         if (path->predMatrixMap(path->source, current) == INVALID)

   140           current = INVALID;

   141         return *this;

   142       }

   144       bool operator==(const RevEdgeIt& e) const {

   145         return current == e.current;

   146       }

   148       bool operator!=(const RevEdgeIt& e) const {

   149         return current != e.current;

   150       }

   152       bool operator<(const RevEdgeIt& e) const {

   153         return current < e.current;

   154       }

   156     private:

   157       const PredMatrixMapPath* path;

   158       typename Graph::Node current;

   159     };

   161   private:

   162     const Graph& graph;

   163     const PredMatrixMap& predMatrixMap;

   164     typename Graph::Node source;

   165     typename Graph::Node target;

   166   };

   168 }

   170 #endif

author	alpar
	Sat, 03 Mar 2007 12:05:05 +0000
changeset 2389	df6a32249b46
parent 2335	27aa03cd3121
child 2391	14a343be7a5a
permissions	-rw-r--r--