1.1 --- a/lemon/static_graph.h Wed Mar 17 12:35:52 2010 +0100
1.2 +++ b/lemon/static_graph.h Sat Mar 06 14:35:12 2010 +0000
1.3 @@ -1,8 +1,8 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 - * Copyright (C) 2003-2008
1.11 + * Copyright (C) 2003-2010
1.12 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.13 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.14 *
1.15 @@ -31,12 +31,12 @@
1.16 class StaticDigraphBase {
1.17 public:
1.18
1.19 - StaticDigraphBase()
1.20 - : built(false), node_num(0), arc_num(0),
1.21 + StaticDigraphBase()
1.22 + : built(false), node_num(0), arc_num(0),
1.23 node_first_out(NULL), node_first_in(NULL),
1.24 - arc_source(NULL), arc_target(NULL),
1.25 + arc_source(NULL), arc_target(NULL),
1.26 arc_next_in(NULL), arc_next_out(NULL) {}
1.27 -
1.28 +
1.29 ~StaticDigraphBase() {
1.30 if (built) {
1.31 delete[] node_first_out;
1.32 @@ -62,7 +62,7 @@
1.33 };
1.34
1.35 class Arc {
1.36 - friend class StaticDigraphBase;
1.37 + friend class StaticDigraphBase;
1.38 protected:
1.39 int id;
1.40 Arc(int _id) : id(_id) {}
1.41 @@ -83,8 +83,8 @@
1.42 void first(Arc& e) const { e.id = arc_num - 1; }
1.43 static void next(Arc& e) { --e.id; }
1.44
1.45 - void firstOut(Arc& e, const Node& n) const {
1.46 - e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
1.47 + void firstOut(Arc& e, const Node& n) const {
1.48 + e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
1.49 node_first_out[n.id] : -1;
1.50 }
1.51 void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }
1.52 @@ -113,21 +113,21 @@
1.53 public:
1.54 typedef typename Digraph::Arc Arc;
1.55
1.56 - ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
1.57 + ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
1.58 : digraph(_graph), nodeRef(_nodeRef) {}
1.59 -
1.60 +
1.61 bool operator()(const Arc& left, const Arc& right) const {
1.62 - return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
1.63 + return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
1.64 }
1.65 private:
1.66 const Digraph& digraph;
1.67 const NodeRefMap& nodeRef;
1.68 };
1.69 -
1.70 +
1.71 public:
1.72
1.73 typedef True BuildTag;
1.74 -
1.75 +
1.76 void clear() {
1.77 if (built) {
1.78 delete[] node_first_out;
1.79 @@ -141,7 +141,7 @@
1.80 node_num = 0;
1.81 arc_num = 0;
1.82 }
1.83 -
1.84 +
1.85 template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
1.86 void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
1.87 typedef typename Digraph::Node GNode;
1.88 @@ -183,7 +183,7 @@
1.89 it != arcs.end(); ++it) {
1.90 int target = nodeRef[digraph.target(*it)].id;
1.91 arcRef[*it] = Arc(arc_index);
1.92 - arc_source[arc_index] = source;
1.93 + arc_source[arc_index] = source;
1.94 arc_target[arc_index] = target;
1.95 arc_next_in[arc_index] = node_first_in[target];
1.96 node_first_in[target] = arc_index;
1.97 @@ -197,7 +197,7 @@
1.98 }
1.99 node_first_out[node_num] = arc_num;
1.100 }
1.101 -
1.102 +
1.103 template <typename ArcListIterator>
1.104 void build(int n, ArcListIterator first, ArcListIterator last) {
1.105 built = true;
1.106 @@ -212,11 +212,11 @@
1.107 arc_target = new int[arc_num];
1.108 arc_next_out = new int[arc_num];
1.109 arc_next_in = new int[arc_num];
1.110 -
1.111 +
1.112 for (int i = 0; i != node_num; ++i) {
1.113 node_first_in[i] = -1;
1.114 - }
1.115 -
1.116 + }
1.117 +
1.118 int arc_index = 0;
1.119 for (int i = 0; i != node_num; ++i) {
1.120 node_first_out[i] = arc_index;
1.121 @@ -282,7 +282,7 @@
1.122 ///
1.123 /// Since this digraph structure is completely static, its nodes and arcs
1.124 /// can be indexed with integers from the ranges <tt>[0..nodeNum()-1]</tt>
1.125 - /// and <tt>[0..arcNum()-1]</tt>, respectively.
1.126 + /// and <tt>[0..arcNum()-1]</tt>, respectively.
1.127 /// The index of an item is the same as its ID, it can be obtained
1.128 /// using the corresponding \ref index() or \ref concepts::Digraph::id()
1.129 /// "id()" function. A node or arc with a certain index can be obtained
1.130 @@ -299,9 +299,9 @@
1.131 public:
1.132
1.133 typedef ExtendedStaticDigraphBase Parent;
1.134 -
1.135 +
1.136 public:
1.137 -
1.138 +
1.139 /// \brief Constructor
1.140 ///
1.141 /// Default constructor.
1.142 @@ -349,7 +349,7 @@
1.143 ///
1.144 /// This method also makes possible to copy a digraph to a StaticDigraph
1.145 /// structure using \ref DigraphCopy.
1.146 - ///
1.147 + ///
1.148 /// \param digraph An existing digraph to be copied.
1.149 /// \param nodeRef The node references will be copied into this map.
1.150 /// Its key type must be \c Digraph::Node and its value type must be
1.151 @@ -370,7 +370,7 @@
1.152 if (built) Parent::clear();
1.153 Parent::build(digraph, nodeRef, arcRef);
1.154 }
1.155 -
1.156 +
1.157 /// \brief Build the digraph from an arc list.
1.158 ///
1.159 /// This function builds the digraph from the given arc list.
1.160 @@ -421,7 +421,7 @@
1.161 using Parent::fastFirstOut;
1.162 using Parent::fastNextOut;
1.163 using Parent::fastLastOut;
1.164 -
1.165 +
1.166 public:
1.167
1.168 class OutArcIt : public Arc {
1.169 @@ -432,8 +432,8 @@
1.170 OutArcIt(Invalid i) : Arc(i) { }
1.171
1.172 OutArcIt(const StaticDigraph& digraph, const Node& node) {
1.173 - digraph.fastFirstOut(*this, node);
1.174 - digraph.fastLastOut(last, node);
1.175 + digraph.fastFirstOut(*this, node);
1.176 + digraph.fastLastOut(last, node);
1.177 if (last == *this) *this = INVALID;
1.178 }
1.179
1.180 @@ -443,10 +443,10 @@
1.181 }
1.182 }
1.183
1.184 - OutArcIt& operator++() {
1.185 + OutArcIt& operator++() {
1.186 StaticDigraph::fastNextOut(*this);
1.187 if (last == *this) *this = INVALID;
1.188 - return *this;
1.189 + return *this;
1.190 }
1.191
1.192 private: