lemon/bits/path_dump.h
author Peter Kovacs <kpeter@inf.elte.hu>
Mon, 30 Jan 2012 20:21:45 +0100
changeset 984 fcb6ad1e67d0
parent 529 f5bc148f7e1f
parent 886 1aa7eba26af5
child 1092 dceba191c00d
permissions -rw-r--r--
Improve the Altering List pivot rule for NetworkSimplex (#435)
Much less candidate arcs are preserved from an iteration to the
next one and partial_sort() is used instead of heap operations.
     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  */
    18 
    19 #ifndef LEMON_BITS_PATH_DUMP_H
    20 #define LEMON_BITS_PATH_DUMP_H
    21 
    22 #include <lemon/core.h>
    23 #include <lemon/concept_check.h>
    24 
    25 namespace lemon {
    26 
    27   template <typename _Digraph, typename _PredMap>
    28   class PredMapPath {
    29   public:
    30     typedef True RevPathTag;
    31 
    32     typedef _Digraph Digraph;
    33     typedef typename Digraph::Arc Arc;
    34     typedef _PredMap PredMap;
    35 
    36     PredMapPath(const Digraph& _digraph, const PredMap& _predMap,
    37                 typename Digraph::Node _target)
    38       : digraph(_digraph), predMap(_predMap), target(_target) {}
    39 
    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     }
    50 
    51     bool empty() const {
    52       return predMap[target] == INVALID;
    53     }
    54 
    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       }
    63 
    64       operator const typename Digraph::Arc() const {
    65         return path->predMap[current];
    66       }
    67 
    68       RevArcIt& operator++() {
    69         current = path->digraph.source(path->predMap[current]);
    70         if (path->predMap[current] == INVALID) current = INVALID;
    71         return *this;
    72       }
    73 
    74       bool operator==(const RevArcIt& e) const {
    75         return current == e.current;
    76       }
    77 
    78       bool operator!=(const RevArcIt& e) const {
    79         return current != e.current;
    80       }
    81 
    82       bool operator<(const RevArcIt& e) const {
    83         return current < e.current;
    84       }
    85 
    86     private:
    87       const PredMapPath* path;
    88       typename Digraph::Node current;
    89     };
    90 
    91   private:
    92     const Digraph& digraph;
    93     const PredMap& predMap;
    94     typename Digraph::Node target;
    95   };
    96 
    97 
    98   template <typename _Digraph, typename _PredMatrixMap>
    99   class PredMatrixMapPath {
   100   public:
   101     typedef True RevPathTag;
   102 
   103     typedef _Digraph Digraph;
   104     typedef typename Digraph::Arc Arc;
   105     typedef _PredMatrixMap PredMatrixMap;
   106 
   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) {}
   113 
   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     }
   124 
   125     bool empty() const {
   126       return predMatrixMap(source, target) == INVALID;
   127     }
   128 
   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       }
   138 
   139       operator const typename Digraph::Arc() const {
   140         return path->predMatrixMap(path->source, current);
   141       }
   142 
   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       }
   150 
   151       bool operator==(const RevArcIt& e) const {
   152         return current == e.current;
   153       }
   154 
   155       bool operator!=(const RevArcIt& e) const {
   156         return current != e.current;
   157       }
   158 
   159       bool operator<(const RevArcIt& e) const {
   160         return current < e.current;
   161       }
   162 
   163     private:
   164       const PredMatrixMapPath* path;
   165       typename Digraph::Node current;
   166     };
   167 
   168   private:
   169     const Digraph& digraph;
   170     const PredMatrixMap& predMatrixMap;
   171     typename Digraph::Node source;
   172     typename Digraph::Node target;
   173   };
   174 
   175 }
   176 
   177 #endif