lemon-main: lemon/bits/path_dump.h@b9c6a47c977b

     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-

     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 _Digraph, typename _PredMap>

    25   class PredMapPath {

    26   public:

    27     typedef True RevPathTag;

    29     typedef _Digraph Digraph;

    30     typedef typename Digraph::Arc Arc;

    31     typedef _PredMap PredMap;

    33     PredMapPath(const Digraph& _digraph, const PredMap& _predMap,

    34                 typename Digraph::Node _target)

    35       : digraph(_digraph), predMap(_predMap), target(_target) {}

    37     int length() const {

    38       int len = 0;

    39       typename Digraph::Node node = target;

    40       typename Digraph::Arc arc;

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

    42         node = digraph.source(arc);

    43         ++len;

    44       }

    45       return len;

    46     }

    48     bool empty() const {

    49       return predMap[target] != INVALID;

    50     }

    52     class RevArcIt {

    53     public:

    54       RevArcIt() {}

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

    56       RevArcIt(const PredMapPath& _path)

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

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

    59       }

    61       operator const typename Digraph::Arc() const {

    62         return path->predMap[current];

    63       }

    65       RevArcIt& operator++() {

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

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

    68         return *this;

    69       }

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

    72         return current == e.current;

    73       }

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

    76         return current != e.current;

    77       }

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

    80         return current < e.current;

    81       }

    83     private:

    84       const PredMapPath* path;

    85       typename Digraph::Node current;

    86     };

    88   private:

    89     const Digraph& digraph;

    90     const PredMap& predMap;

    91     typename Digraph::Node target;

    92   };

    95   template <typename _Digraph, typename _PredMatrixMap>

    96   class PredMatrixMapPath {

    97   public:

    98     typedef True RevPathTag;

   100     typedef _Digraph Digraph;

   101     typedef typename Digraph::Arc Arc;

   102     typedef _PredMatrixMap PredMatrixMap;

   104     PredMatrixMapPath(const Digraph& _digraph,

   105                       const PredMatrixMap& _predMatrixMap,

   106                       typename Digraph::Node _source,

   107                       typename Digraph::Node _target)

   108       : digraph(_digraph), predMatrixMap(_predMatrixMap),

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

   111     int length() const {

   112       int len = 0;

   113       typename Digraph::Node node = target;

   114       typename Digraph::Arc arc;

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

   116         node = digraph.source(arc);

   117         ++len;

   118       }

   119       return len;

   120     }

   122     bool empty() const {

   123       return source != target;

   124     }

   126     class RevArcIt {

   127     public:

   128       RevArcIt() {}

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

   130       RevArcIt(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 Digraph::Arc() const {

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

   138       }

   140       RevArcIt& operator++() {

   141         current =

   142           path->digraph.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 RevArcIt& e) const {

   149         return current == e.current;

   150       }

   152       bool operator!=(const RevArcIt& e) const {

   153         return current != e.current;

   154       }

   156       bool operator<(const RevArcIt& e) const {

   157         return current < e.current;

   158       }

   160     private:

   161       const PredMatrixMapPath* path;

   162       typename Digraph::Node current;

   163     };

   165   private:

   166     const Digraph& digraph;

   167     const PredMatrixMap& predMatrixMap;

   168     typename Digraph::Node source;

   169     typename Digraph::Node target;

   170   };

   172 }

   174 #endif

author	Alpar Juttner <alpar@cs.elte.hu>
	Tue, 15 Jul 2008 18:43:41 +0100
changeset 219	b9c6a47c977b
parent 100	4f754b4cf82b
child 440	88ed40ad0d4f
child 885	1f2a734581f8
permissions	-rw-r--r--