lemon/bits/path_dump.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 519 c786cd201266
child 890 e26ad33d1fbc
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
     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 source != target;
   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