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

     1 /* -*- C++ -*-

     2  *

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

     4  *

     5  * Copyright (C) 2003-2008

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

     8  *

     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.

    12  *

    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

    15  * purpose.

    16  *

    17  */

    19 #ifndef LEMON_BITS_PRED_MAP_PATH_H

    20 #define LEMON_BITS_PRED_MAP_PATH_H

    22 namespace lemon {

    24   template <typename _Graph, typename _PredMap>

    25   class PredMapPath {

    26   public:

    27     typedef True RevPathTag;

    29     typedef _Graph Graph;

    30     typedef typename Graph::Edge Edge;

    31     typedef _PredMap PredMap;

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

    34                 typename Graph::Node _target)

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

    37     int length() const {

    38       int len = 0;

    39       typename Graph::Node node = target;

    40       typename Graph::Edge edge;

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

    42         node = graph.source(edge);

    43         ++len;

    44       }

    45       return len;

    46     }

    48     bool empty() const {

    49       return predMap[target] != INVALID;

    50     }

    52     class RevEdgeIt {

    53     public:

    54       RevEdgeIt() {}

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

    56       RevEdgeIt(const PredMapPath& _path)

    57         : path(&_path), current(_path.target) {

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

    59       }

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

    62         return path->predMap[current];

    63       }

    65       RevEdgeIt& operator++() {

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

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

    68         return *this;

    69       }

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

    72         return current == e.current;

    73       }

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

    76         return current != e.current;

    77       }

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

    80         return current < e.current;

    81       }

    83     private:

    84       const PredMapPath* path;

    85       typename Graph::Node current;

    86     };

    88   private:

    89     const Graph& graph;

    90     const PredMap& predMap;

    91     typename Graph::Node target;

    92   };

    95   template <typename _Graph, typename _PredMatrixMap>

    96   class PredMatrixMapPath {

    97   public:

    98     typedef True RevPathTag;

   100     typedef _Graph Graph;

   101     typedef typename Graph::Edge Edge;

   102     typedef _PredMatrixMap PredMatrixMap;

   104     PredMatrixMapPath(const Graph& _graph,

   105                       const PredMatrixMap& _predMatrixMap,

   106                       typename Graph::Node _source,

   107                       typename Graph::Node _target)

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

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

   111     int length() const {

   112       int len = 0;

   113       typename Graph::Node node = target;

   114       typename Graph::Edge edge;

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

   116         node = graph.source(edge);

   117         ++len;

   118       }

   119       return len;

   120     }

   122     bool empty() const {

   123       return source != target;

   124     }

   126     class RevEdgeIt {

   127     public:

   128       RevEdgeIt() {}

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

   130       RevEdgeIt(const PredMatrixMapPath& _path)

   131         : path(&_path), current(_path.target) {

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

   133           current = INVALID;

   134       }

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

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

   138       }

   140       RevEdgeIt& operator++() {

   141         current =

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

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

   144           current = INVALID;

   145         return *this;

   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       bool operator<(const RevEdgeIt& e) const {

   157         return current < e.current;

   158       }

   160     private:

   161       const PredMatrixMapPath* path;

   162       typename Graph::Node current;

   163     };

   165   private:

   166     const Graph& graph;

   167     const PredMatrixMap& predMatrixMap;

   168     typename Graph::Node source;

   169     typename Graph::Node target;

   170   };

   172 }

   174 #endif

author	kpeter
	Mon, 18 Feb 2008 03:30:12 +0000
changeset 2573	a9758ea1f01c
parent 2467	2025a571895e
permissions	-rw-r--r--