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

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

     2  *

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

     4  *

     5  * Copyright (C) 2003-2007

     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) {}

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

    60         return path->predMap[current];

    61       }

    63       RevEdgeIt& operator++() {

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

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

    66         return *this;

    67       }

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

    70         return current == e.current;

    71       }

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

    74         return current != e.current;

    75       }

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

    78         return current < e.current;

    79       }

    81     private:

    82       const PredMapPath* path;

    83       typename Graph::Node current;

    84     };

    86   private:

    87     const Graph& graph;

    88     const PredMap& predMap;

    89     typename Graph::Node target;

    90   };

    93   template <typename _Graph, typename _PredMatrixMap>

    94   class PredMatrixMapPath {

    95   public:

    96     typedef True RevPathTag;

    98     typedef _Graph Graph;

    99     typedef typename Graph::Edge Edge;

   100     typedef _PredMatrixMap PredMatrixMap;

   102     PredMatrixMapPath(const Graph& _graph,

   103                       const PredMatrixMap& _predMatrixMap,

   104                       typename Graph::Node _source,

   105                       typename Graph::Node _target)

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

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

   109     int length() const {

   110       int len = 0;

   111       typename Graph::Node node = target;

   112       typename Graph::Edge edge;

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

   114         node = graph.source(edge);

   115         ++len;

   116       }

   117       return len;

   118     }

   120     bool empty() const {

   121       return source != target;

   122     }

   124     class RevEdgeIt {

   125     public:

   126       RevEdgeIt() {}

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

   128       RevEdgeIt(const PredMatrixMapPath& _path)

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

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

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

   133       }

   135       RevEdgeIt& operator++() {

   136         current =

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

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

   139           current = INVALID;

   140         return *this;

   141       }

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

   144         return current == e.current;

   145       }

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

   148         return current != e.current;

   149       }

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

   152         return current < e.current;

   153       }

   155     private:

   156       const PredMatrixMapPath* path;

   157       typename Graph::Node current;

   158     };

   160   private:

   161     const Graph& graph;

   162     const PredMatrixMap& predMatrixMap;

   163     typename Graph::Node source;

   164     typename Graph::Node target;

   165   };

   167 }

   169 #endif

author	athos
	Tue, 27 Mar 2007 09:23:33 +0000
changeset 2415	ef13597d249a
parent 2357	5365600a7a5c
child 2467	2025a571895e
permissions	-rw-r--r--