lemon-main: comparison lemon/static

equal deleted inserted replaced

-:8c97bbea62db
+:cde5cdb1c9db
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
-* This file is a part of LEMON, a generic C++ optimization library
+* This file is a part of LEMON, a generic C++ optimization library.
 *
-* Copyright (C) 2003-2008
+* Copyright (C) 2003-2010
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 namespace lemon {
 class StaticDigraphBase {
 public:
 StaticDigraphBase()
 : built(false), node_num(0), arc_num(0),
 node_first_out(NULL), node_first_in(NULL),
 arc_source(NULL), arc_target(NULL),
 arc_next_in(NULL), arc_next_out(NULL) {}
 ~StaticDigraphBase() {
 if (built) {
 delete[] node_first_out;
 delete[] node_first_in;
 delete[] arc_source;
 bool operator!=(const Node& node) const { return id != node.id; }
 bool operator<(const Node& node) const { return id < node.id; }
 };
 class Arc {
 friend class StaticDigraphBase;
 protected:
 int id;
 Arc(int _id) : id(_id) {}
 public:
 Arc() { }
 static void next(Node& n) { --n.id; }
 void first(Arc& e) const { e.id = arc_num - 1; }
 static void next(Arc& e) { --e.id; }
 void firstOut(Arc& e, const Node& n) const {
 e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
 node_first_out[n.id] : -1;
 }
 void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }
 void firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; }
 template <typename Digraph, typename NodeRefMap>
 class ArcLess {
 public:
 typedef typename Digraph::Arc Arc;
 ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
 : digraph(_graph), nodeRef(_nodeRef) {}
 bool operator()(const Arc& left, const Arc& right) const {
-	return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
+return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
 }
 private:
 const Digraph& digraph;
 const NodeRefMap& nodeRef;
 };
 public:
 typedef True BuildTag;
 void clear() {
 if (built) {
 delete[] node_first_out;
 delete[] node_first_in;
 delete[] arc_source;
 }
 built = false;
 node_num = 0;
 arc_num = 0;
 }
 template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
 void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
 typedef typename Digraph::Node GNode;
 typedef typename Digraph::Arc GArc;
 std::sort(arcs.begin(), arcs.end(), arcLess);
 for (typename std::vector<GArc>::iterator it = arcs.begin();
 it != arcs.end(); ++it) {
 int target = nodeRef[digraph.target(*it)].id;
 arcRef[*it] = Arc(arc_index);
 arc_source[arc_index] = source;
 arc_target[arc_index] = target;
 arc_next_in[arc_index] = node_first_in[target];
 node_first_in[target] = arc_index;
 arc_next_out[arc_index] = arc_index + 1;
 ++arc_index;
 node_first_out[source] = arc_index;
 }
 }
 node_first_out[node_num] = arc_num;
 }
 template <typename ArcListIterator>
 void build(int n, ArcListIterator first, ArcListIterator last) {
 built = true;
 node_num = n;
 arc_source = new int[arc_num];
 arc_target = new int[arc_num];
 arc_next_out = new int[arc_num];
 arc_next_in = new int[arc_num];
 for (int i = 0; i != node_num; ++i) {
 node_first_in[i] = -1;
 }
 int arc_index = 0;
 for (int i = 0; i != node_num; ++i) {
 node_first_out[i] = arc_index;
 for ( ; first != last && (*first).first == i; ++first) {
 int j = (*first).second;
 /// However it only provides build() and clear() functions and does not
 /// support any other modification of the digraph.
 ///
 /// Since this digraph structure is completely static, its nodes and arcs
 /// can be indexed with integers from the ranges <tt>[0..nodeNum()-1]</tt>
 /// and <tt>[0..arcNum()-1]</tt>, respectively.
 /// The index of an item is the same as its ID, it can be obtained
 /// using the corresponding \ref index() or \ref concepts::Digraph::id()
 /// "id()" function. A node or arc with a certain index can be obtained
 /// using node() or arc().
 ///
 /// \sa concepts::Digraph
 class StaticDigraph : public ExtendedStaticDigraphBase {
 public:
 typedef ExtendedStaticDigraphBase Parent;
 public:
 /// \brief Constructor
 ///
 /// Default constructor.
 StaticDigraph() : Parent() {}
 /// kind. It can be called more than once, but in such case, the whole
 /// structure and all maps will be cleared and rebuilt.
 ///
 /// This method also makes possible to copy a digraph to a StaticDigraph
 /// structure using \ref DigraphCopy.
 ///
 /// \param digraph An existing digraph to be copied.
 /// \param nodeRef The node references will be copied into this map.
 /// Its key type must be \c Digraph::Node and its value type must be
 /// \c StaticDigraph::Node.
 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
 template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
 void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
 if (built) Parent::clear();
 Parent::build(digraph, nodeRef, arcRef);
 }
 /// \brief Build the digraph from an arc list.
 ///
 /// This function builds the digraph from the given arc list.
 /// It can be called more than once, but in such case, the whole
 /// structure and all maps will be cleared and rebuilt.
 protected:
 using Parent::fastFirstOut;
 using Parent::fastNextOut;
 using Parent::fastLastOut;
 public:
 class OutArcIt : public Arc {
 public:
 OutArcIt() { }
 OutArcIt(Invalid i) : Arc(i) { }
 OutArcIt(const StaticDigraph& digraph, const Node& node) {
-	digraph.fastFirstOut(*this, node);
+digraph.fastFirstOut(*this, node);
-	digraph.fastLastOut(last, node);
+digraph.fastLastOut(last, node);
 if (last == *this) *this = INVALID;
 }
 OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
 if (arc != INVALID) {
 digraph.fastLastOut(last, digraph.source(arc));
 }
 }
 OutArcIt& operator++() {
 StaticDigraph::fastNextOut(*this);
 if (last == *this) *this = INVALID;
 return *this;
 }
 private:
 Arc last;
 };

changeset 1183	cd72eae05bdf
parent 787	c2230649a493
child 1124	d51126dc39fa