lemon-1.2: lemon/bits/path_dump.h@a42f46828cc1

     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-2009

     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_PATH_DUMP_H

    20 #define LEMON_BITS_PATH_DUMP_H

    22 #include <lemon/core.h>

    23 #include <lemon/concept_check.h>

    25 namespace lemon {

    27   template <typename _Digraph, typename _PredMap>

    28   class PredMapPath {

    29   public:

    30     typedef True RevPathTag;

    32     typedef _Digraph Digraph;

    33     typedef typename Digraph::Arc Arc;

    34     typedef _PredMap PredMap;

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

    37                 typename Digraph::Node _target)

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

    40     int length() const {

    41       int len = 0;

    42       typename Digraph::Node node = target;

    43       typename Digraph::Arc arc;

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

    45         node = digraph.source(arc);

    46         ++len;

    47       }

    48       return len;

    49     }

    51     bool empty() const {

    52       return predMap[target] != INVALID;

    53     }

    55     class RevArcIt {

    56     public:

    57       RevArcIt() {}

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

    59       RevArcIt(const PredMapPath& _path)

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

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

    62       }

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

    65         return path->predMap[current];

    66       }

    68       RevArcIt& operator++() {

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

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

    71         return *this;

    72       }

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

    75         return current == e.current;

    76       }

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

    79         return current != e.current;

    80       }

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

    83         return current < e.current;

    84       }

    86     private:

    87       const PredMapPath* path;

    88       typename Digraph::Node current;

    89     };

    91   private:

    92     const Digraph& digraph;

    93     const PredMap& predMap;

    94     typename Digraph::Node target;

    95   };

    98   template <typename _Digraph, typename _PredMatrixMap>

    99   class PredMatrixMapPath {

   100   public:

   101     typedef True RevPathTag;

   103     typedef _Digraph Digraph;

   104     typedef typename Digraph::Arc Arc;

   105     typedef _PredMatrixMap PredMatrixMap;

   107     PredMatrixMapPath(const Digraph& _digraph,

   108                       const PredMatrixMap& _predMatrixMap,

   109                       typename Digraph::Node _source,

   110                       typename Digraph::Node _target)

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

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

   114     int length() const {

   115       int len = 0;

   116       typename Digraph::Node node = target;

   117       typename Digraph::Arc arc;

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

   119         node = digraph.source(arc);

   120         ++len;

   121       }

   122       return len;

   123     }

   125     bool empty() const {

   126       return source != target;

   127     }

   129     class RevArcIt {

   130     public:

   131       RevArcIt() {}

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

   133       RevArcIt(const PredMatrixMapPath& _path)

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

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

   136           current = INVALID;

   137       }

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

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

   141       }

   143       RevArcIt& operator++() {

   144         current =

   145           path->digraph.source(path->predMatrixMap(path->source, current));

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

   147           current = INVALID;

   148         return *this;

   149       }

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

   152         return current == e.current;

   153       }

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

   156         return current != e.current;

   157       }

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

   160         return current < e.current;

   161       }

   163     private:

   164       const PredMatrixMapPath* path;

   165       typename Digraph::Node current;

   166     };

   168   private:

   169     const Digraph& digraph;

   170     const PredMatrixMap& predMatrixMap;

   171     typename Digraph::Node source;

   172     typename Digraph::Node target;

   173   };

   175 }

   177 #endif

author	Alpar Juttner <alpar@cs.elte.hu>
	Mon, 05 Oct 2009 09:48:57 +0200
changeset 747	a42f46828cc1
parent 519	c786cd201266
child 890	e26ad33d1fbc
permissions	-rw-r--r--