lemon-1.3: comparison lemon/list

equal deleted inserted replaced

-:1f4723c94176
+:fbfc9b3c92d5
-/* -*- 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
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 protected:
 struct NodeT {
 int first_in, first_out;
 int prev, next;
 };
 struct ArcT {
 int target, source;
 int prev_in, prev_out;
 int next_in, next_out;
 };
 int first_free_node;
 std::vector<ArcT> arcs;
 int first_free_arc;
 public:
 typedef ListDigraphBase Digraph;
 class Node {
 friend class ListDigraphBase;
 protected:
 int id;
 ListDigraphBase()
 : nodes(), first_node(-1),
-	first_free_node(-1), arcs(), first_free_arc(-1) {}
+first_free_node(-1), arcs(), first_free_arc(-1) {}
 int maxNodeId() const { return nodes.size()-1; }
 int maxArcId() const { return arcs.size()-1; }
 Node source(Arc e) const { return Node(arcs[e.id].source); }
 Node target(Arc e) const { return Node(arcs[e.id].target); }
 void first(Node& node) const {
 node.id = first_node;
 }
 void next(Node& node) const {
 node.id = nodes[node.id].next;
 }
 void first(Arc& arc) const {
 int n;
 for(n = first_node;
-	  n!=-1 && nodes[n].first_in == -1;
+n!=-1 && nodes[n].first_in == -1;
-	  n = nodes[n].next) {}
+n = nodes[n].next) {}
 arc.id = (n == -1) ? -1 : nodes[n].first_in;
 }
 void next(Arc& arc) const {
 if (arcs[arc.id].next_in != -1) {
-	arc.id = arcs[arc.id].next_in;
+arc.id = arcs[arc.id].next_in;
 } else {
-	int n;
+int n;
-	for(n = nodes[arcs[arc.id].target].next;
+for(n = nodes[arcs[arc.id].target].next;
-	    n!=-1 && nodes[n].first_in == -1;
+n!=-1 && nodes[n].first_in == -1;
-	    n = nodes[n].next) {}
+n = nodes[n].next) {}
-	arc.id = (n == -1) ? -1 : nodes[n].first_in;
+arc.id = (n == -1) ? -1 : nodes[n].first_in;
 }
 }
 void firstOut(Arc &e, const Node& v) const {
 e.id = nodes[v.id].first_out;
 }
 }
 void nextIn(Arc &e) const {
 e.id=arcs[e.id].next_in;
 }
 static int id(Node v) { return v.id; }
 static int id(Arc e) { return e.id; }
 static Node nodeFromId(int id) { return Node(id);}
 static Arc arcFromId(int id) { return Arc(id);}
 bool valid(Node n) const {
 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
-	nodes[n.id].prev != -2;
+nodes[n.id].prev != -2;
 }
 bool valid(Arc a) const {
 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
-	arcs[a.id].prev_in != -2;
+arcs[a.id].prev_in != -2;
 }
 Node addNode() {
 int n;
 if(first_free_node==-1) {
-	n = nodes.size();
+n = nodes.size();
-	nodes.push_back(NodeT());
+nodes.push_back(NodeT());
 } else {
-	n = first_free_node;
+n = first_free_node;
-	first_free_node = nodes[n].next;
+first_free_node = nodes[n].next;
 }
 nodes[n].next = first_node;
 if(first_node != -1) nodes[first_node].prev = n;
 first_node = n;
 nodes[n].prev = -1;
 nodes[n].first_in = nodes[n].first_out = -1;
 return Node(n);
 }
 Arc addArc(Node u, Node v) {
 int n;
 if (first_free_arc == -1) {
-	n = arcs.size();
+n = arcs.size();
-	arcs.push_back(ArcT());
+arcs.push_back(ArcT());
 } else {
-	n = first_free_arc;
+n = first_free_arc;
-	first_free_arc = arcs[n].next_in;
+first_free_arc = arcs[n].next_in;
 }
 arcs[n].source = u.id;
 arcs[n].target = v.id;
 arcs[n].next_out = nodes[u.id].first_out;
 if(nodes[u.id].first_out != -1) {
-	arcs[nodes[u.id].first_out].prev_out = n;
+arcs[nodes[u.id].first_out].prev_out = n;
 }
 arcs[n].next_in = nodes[v.id].first_in;
 if(nodes[v.id].first_in != -1) {
-	arcs[nodes[v.id].first_in].prev_in = n;
+arcs[nodes[v.id].first_in].prev_in = n;
 }
 arcs[n].prev_in = arcs[n].prev_out = -1;
 nodes[u.id].first_out = nodes[v.id].first_in = n;
 return Arc(n);
 }
 void erase(const Node& node) {
 int n = node.id;
 if(nodes[n].next != -1) {
-	nodes[nodes[n].next].prev = nodes[n].prev;
+nodes[nodes[n].next].prev = nodes[n].prev;
 }
 if(nodes[n].prev != -1) {
-	nodes[nodes[n].prev].next = nodes[n].next;
+nodes[nodes[n].prev].next = nodes[n].next;
 } else {
-	first_node = nodes[n].next;
+first_node = nodes[n].next;
 }
 nodes[n].next = first_free_node;
 first_free_node = n;
 nodes[n].prev = -2;
 }
 void erase(const Arc& arc) {
 int n = arc.id;
 if(arcs[n].next_in!=-1) {
-	arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
+arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
 }
 if(arcs[n].prev_in!=-1) {
-	arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
+arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
 } else {
-	nodes[arcs[n].target].first_in = arcs[n].next_in;
+nodes[arcs[n].target].first_in = arcs[n].next_in;
 }
 if(arcs[n].next_out!=-1) {
-	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
+arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
 }
 if(arcs[n].prev_out!=-1) {
-	arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
+arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 } else {
-	nodes[arcs[n].source].first_out = arcs[n].next_out;
+nodes[arcs[n].source].first_out = arcs[n].next_out;
 }
 arcs[n].next_in = first_free_arc;
 first_free_arc = n;
 arcs[n].prev_in = -2;
 }
 nodes.clear();
 first_node = first_free_node = first_free_arc = -1;
 }
 protected:
 void changeTarget(Arc e, Node n)
 {
 if(arcs[e.id].next_in != -1)
-	arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
+arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
 if(arcs[e.id].prev_in != -1)
-	arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
+arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
 else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
 if (nodes[n.id].first_in != -1) {
-	arcs[nodes[n.id].first_in].prev_in = e.id;
+arcs[nodes[n.id].first_in].prev_in = e.id;
 }
 arcs[e.id].target = n.id;
 arcs[e.id].prev_in = -1;
 arcs[e.id].next_in = nodes[n.id].first_in;
 nodes[n.id].first_in = e.id;
 }
 void changeSource(Arc e, Node n)
 {
 if(arcs[e.id].next_out != -1)
-	arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
+arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
 if(arcs[e.id].prev_out != -1)
-	arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
+arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
 else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
 if (nodes[n.id].first_out != -1) {
-	arcs[nodes[n.id].first_out].prev_out = e.id;
+arcs[nodes[n.id].first_out].prev_out = e.id;
 }
 arcs[e.id].source = n.id;
 arcs[e.id].prev_out = -1;
 arcs[e.id].next_out = nodes[n.id].first_out;
 nodes[n.id].first_out = e.id;
 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
 /// \addtogroup graphs
 /// @{
 ///A general directed graph structure.
 ///\ref ListDigraph is a simple and fast <em>directed graph</em>
 ///implementation based on static linked lists that are stored in
 ///\c std::vector structures.
 ///
 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
 ///also provides several useful additional functionalities.
 ///Most of the member functions and nested classes are documented
 ///only in the concept class.
 ///\sa concepts::Digraph
 class ListDigraph : public ExtendedListDigraphBase {
 private:
 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
 ///
 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
 ///\brief Assignment of ListDigraph to another one is \e not allowed.
 ///Use copyDigraph() instead.
 public:
 typedef ExtendedListDigraphBase Parent;
 /// Constructor
 /// Constructor.
 ///
 ListDigraph() {}
 ///Add a new node to the digraph.
 ///Add a new node to the digraph.
 ///\return the new node.
 Node addNode() { return Parent::addNode(); }
 ///Add a new arc to the digraph.
 ///Add a new arc to the digraph with source node \c s
 ///and target node \c t.
 ///\return the new arc.
 Arc addArc(const Node& s, const Node& t) {
 return Parent::addArc(s, t);
 }
 /// Node validity check
 /// This function gives back true if the given node is valid,
 /// ie. it is a real node of the graph.
 ///
 /// \warning A Node pointing to a removed item
 /// could become valid again later if new nodes are
 /// added to the graph.
 bool valid(Node n) const { return Parent::valid(n); }
 /// Arc validity check
 /// This function gives back true if the given arc is valid,
 /// ie. it is a real arc of the graph.
 ///
 /// \warning An Arc pointing to a removed item
 /// could become valid again later if new nodes are
 /// added to the graph.
 bool valid(Arc a) const { return Parent::valid(a); }
 ///the changed arc remain valid. However <tt>InArcIt</tt>s are
 ///invalidated.
 ///
 ///\warning This functionality cannot be used together with the Snapshot
 ///feature.
 void changeTarget(Arc e, Node n) {
 Parent::changeTarget(e,n);
 }
 /// Change the source of \c e to \c n
 /// Change the source of \c e to \c n
 ///
 ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
 ///invalidated.
 ///
 ///\warning This functionality cannot be used together with the Snapshot
 ///feature.
 void changeSource(Arc e, Node n) {
 Parent::changeSource(e,n);
 }
 /// Invert the direction of an arc.
 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
 ///may be invalidated.
 ///
 ///\warning This functionality cannot be used together with the Snapshot
 ///feature.
 void contract(Node a, Node b, bool r = true)
 {
 for(OutArcIt e(*this,b);e!=INVALID;) {
-	OutArcIt f=e;
+OutArcIt f=e;
-	++f;
+++f;
-	if(r && target(e)==a) erase(e);
+if(r && target(e)==a) erase(e);
-	else changeSource(e,a);
+else changeSource(e,a);
-	e=f;
+e=f;
 }
 for(InArcIt e(*this,b);e!=INVALID;) {
-	InArcIt f=e;
+InArcIt f=e;
-	++f;
+++f;
-	if(r && source(e)==a) erase(e);
+if(r && source(e)==a) erase(e);
-	else changeTarget(e,a);
+else changeTarget(e,a);
-	e=f;
+e=f;
 }
 erase(b);
 }
 ///Split a node.
 ///from \c n to the newly created node is also added.
 ///\return The newly created node.
 ///
 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
 ///be invalidated.
 ///
 ///\warning This functionality cannot be used together with the
 ///Snapshot feature.
 ///
 ///\todo It could be implemented in a bit faster way.
 Node split(Node n, bool connect = true) {
 Node b = addNode();
 for(OutArcIt e(*this,n);e!=INVALID;) {
-	OutArcIt f=e;
+OutArcIt f=e;
-	++f;
+++f;
-	changeSource(e,b);
+changeSource(e,b);
-	e=f;
+e=f;
 }
 if (connect) addArc(n,b);
 return b;
 }
 ///Split an arc.
 ///This function splits an arc. First a new node \c b is added to
 ///the digraph, then the original arc is re-targeted to \c
 ///b. Finally an arc from \c b to the original target is added.
 Node b = addNode();
 addArc(b,target(e));
 changeTarget(e,b);
 return b;
 }
 /// \brief Class to make a snapshot of the digraph and restore
 /// it later.
 ///
 /// Class to make a snapshot of the digraph and restore it later.
 ///
 /// The newly added nodes and arcs can be removed using the
 /// restore() function.
 ///
 /// \warning Arc and node deletions and other modifications (e.g.
 /// contracting, splitting, reversing arcs or nodes) cannot be
 /// restored. These events invalidate the snapshot.
 class Snapshot {
 protected:
 typedef Parent::NodeNotifier NodeNotifier;
 : snapshot(_snapshot) {}
 using NodeNotifier::ObserverBase::attach;
 using NodeNotifier::ObserverBase::detach;
 using NodeNotifier::ObserverBase::attached;
 protected:
 virtual void add(const Node& node) {
 snapshot.addNode(node);
 }
 virtual void add(const std::vector<Node>& nodes) {
 for (int i = nodes.size() - 1; i >= 0; ++i) {
 }
 }
 virtual void build() {
 Node node;
 std::vector<Node> nodes;
 for (notifier()->first(node); node != INVALID;
 notifier()->next(node)) {
 nodes.push_back(node);
 }
 for (int i = nodes.size() - 1; i >= 0; --i) {
 snapshot.addNode(nodes[i]);
 }
 }
 virtual void clear() {
 Node node;
 for (notifier()->first(node); node != INVALID;
 notifier()->next(node)) {
 snapshot.eraseNode(node);
 }
 }
 : snapshot(_snapshot) {}
 using ArcNotifier::ObserverBase::attach;
 using ArcNotifier::ObserverBase::detach;
 using ArcNotifier::ObserverBase::attached;
 protected:
 virtual void add(const Arc& arc) {
 snapshot.addArc(arc);
 }
 }
 }
 virtual void build() {
 Arc arc;
 std::vector<Arc> arcs;
 for (notifier()->first(arc); arc != INVALID;
 notifier()->next(arc)) {
 arcs.push_back(arc);
 }
 for (int i = arcs.size() - 1; i >= 0; --i) {
 snapshot.addArc(arcs[i]);
 }
 }
 virtual void clear() {
 Arc arc;
 for (notifier()->first(arc); arc != INVALID;
 notifier()->next(arc)) {
 snapshot.eraseArc(arc);
 }
 }
 Snapshot& snapshot;
 };
 ListDigraph *digraph;
 NodeObserverProxy node_observer_proxy;
 ArcObserverProxy arc_observer_proxy;
 std::list<Node> added_nodes;
 std::list<Arc> added_arcs;
 void addNode(const Node& node) {
 added_nodes.push_front(node);
 }
 void eraseNode(const Node& node) {
 std::list<Node>::iterator it =
 std::find(added_nodes.begin(), added_nodes.end(), node);
 if (it == added_nodes.end()) {
 clear();
 arc_observer_proxy.detach();
 throw NodeNotifier::ImmediateDetach();
 added_nodes.erase(it);
 }
 }
 void addArc(const Arc& arc) {
 added_arcs.push_front(arc);
 }
 void eraseArc(const Arc& arc) {
 std::list<Arc>::iterator it =
 std::find(added_arcs.begin(), added_arcs.end(), arc);
 if (it == added_arcs.end()) {
 clear();
 node_observer_proxy.detach();
 throw ArcNotifier::ImmediateDetach();
 } else {
 added_arcs.erase(it);
 }
 }
 void attach(ListDigraph &_digraph) {
-	digraph = &_digraph;
+digraph = &_digraph;
-	node_observer_proxy.attach(digraph->notifier(Node()));
+node_observer_proxy.attach(digraph->notifier(Node()));
 arc_observer_proxy.attach(digraph->notifier(Arc()));
 }
 void detach() {
-	node_observer_proxy.detach();
+node_observer_proxy.detach();
-	arc_observer_proxy.detach();
+arc_observer_proxy.detach();
 }
 bool attached() const {
 return node_observer_proxy.attached();
 }
 void clear() {
 added_nodes.clear();
 added_arcs.clear();
 }
 public:
 /// \brief Default constructor.
 ///
 /// Default constructor.
 /// To actually make a snapshot you must call save().
 Snapshot()
 : digraph(0), node_observer_proxy(*this),
 arc_observer_proxy(*this) {}
 /// \brief Constructor that immediately makes a snapshot.
 ///
 /// This constructor immediately makes a snapshot of the digraph.
 /// \param _digraph The digraph we make a snapshot of.
 Snapshot(ListDigraph &_digraph)
 : node_observer_proxy(*this),
 arc_observer_proxy(*this) {
-	attach(_digraph);
+attach(_digraph);
 }
 /// \brief Make a snapshot.
 ///
 /// Make a snapshot of the digraph.
 ///
 /// This function can be called more than once. In case of a repeated
 detach();
 clear();
 }
 attach(_digraph);
 }
 /// \brief Undo the changes until the last snapshot.
 //
 /// Undo the changes until the last snapshot created by save().
 void restore() {
-	detach();
+detach();
-	for(std::list<Arc>::iterator it = added_arcs.begin();
+for(std::list<Arc>::iterator it = added_arcs.begin();
 it != added_arcs.end(); ++it) {
-	  digraph->erase(*it);
+digraph->erase(*it);
-	}
+}
-	for(std::list<Node>::iterator it = added_nodes.begin();
+for(std::list<Node>::iterator it = added_nodes.begin();
 it != added_nodes.end(); ++it) {
-	  digraph->erase(*it);
+digraph->erase(*it);
-	}
+}
 clear();
 }
 /// \brief Gives back true when the snapshot is valid.
 ///
 /// Gives back true when the snapshot is valid.
 bool valid() const {
 return attached();
 }
 };
 };
 ///@}
 class ListGraphBase {
 struct NodeT {
 int first_out;
 int prev, next;
 };
 struct ArcT {
 int target;
 int prev_out, next_out;
 };
 int first_free_node;
 std::vector<ArcT> arcs;
 int first_free_arc;
 public:
 typedef ListGraphBase Digraph;
 class Node;
 class Arc;
 class Edge;
 class Node {
 friend class ListGraphBase;
 protected:
 int id;
 ListGraphBase()
 : nodes(), first_node(-1),
-	first_free_node(-1), arcs(), first_free_arc(-1) {}
+first_free_node(-1), arcs(), first_free_arc(-1) {}
 int maxNodeId() const { return nodes.size()-1; }
 int maxEdgeId() const { return arcs.size() / 2 - 1; }
 int maxArcId() const { return arcs.size()-1; }
 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
 Node target(Arc e) const { return Node(arcs[e.id].target); }
 static Arc direct(Edge e, bool d) {
 return Arc(e.id * 2 + (d ? 1 : 0));
 }
 void first(Node& node) const {
 node.id = first_node;
 }
 void next(Node& node) const {
 node.id = nodes[node.id].next;
 }
 void first(Arc& e) const {
 int n = first_node;
 while (n != -1 && nodes[n].first_out == -1) {
 n = nodes[n].next;
 }
 e.id = (n == -1) ? -1 : nodes[n].first_out;
 }
 void next(Arc& e) const {
 if (arcs[e.id].next_out != -1) {
-	e.id = arcs[e.id].next_out;
+e.id = arcs[e.id].next_out;
 } else {
-	int n = nodes[arcs[e.id ^ 1].target].next;
+int n = nodes[arcs[e.id ^ 1].target].next;
 while(n != -1 && nodes[n].first_out == -1) {
 n = nodes[n].next;
 }
-	e.id = (n == -1) ? -1 : nodes[n].first_out;
+e.id = (n == -1) ? -1 : nodes[n].first_out;
 }
 }
 void first(Edge& e) const {
 int n = first_node;
 while (n != -1) {
 e.id = nodes[n].first_out;
 while ((e.id & 1) != 1) {
 e.id = arcs[e.id].next_out;
 }
 if (e.id != -1) {
 e.id /= 2;
 return;
 }
 n = nodes[n].next;
 }
 e.id = -1;
 }
 e.id = arcs[e.id].next_out;
 }
 if (e.id != -1) {
 e.id /= 2;
 return;
 }
 n = nodes[n].next;
 while (n != -1) {
 e.id = nodes[n].first_out;
 while ((e.id & 1) != 1) {
 e.id = arcs[e.id].next_out;
 }
 if (e.id != -1) {
 e.id /= 2;
 return;
 }
 n = nodes[n].next;
 }
 e.id = -1;
 }
 } else {
 e.id = -1;
 d = true;
 }
 }
 static int id(Node v) { return v.id; }
 static int id(Arc e) { return e.id; }
 static int id(Edge e) { return e.id; }
 static Node nodeFromId(int id) { return Node(id);}
 static Arc arcFromId(int id) { return Arc(id);}
 static Edge edgeFromId(int id) { return Edge(id);}
 bool valid(Node n) const {
 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
-	nodes[n.id].prev != -2;
+nodes[n.id].prev != -2;
 }
 bool valid(Arc a) const {
 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
-	arcs[a.id].prev_out != -2;
+arcs[a.id].prev_out != -2;
 }
 bool valid(Edge e) const {
 return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
-	arcs[2 * e.id].prev_out != -2;
+arcs[2 * e.id].prev_out != -2;
 }
 Node addNode() {
 int n;
 if(first_free_node==-1) {
-	n = nodes.size();
+n = nodes.size();
-	nodes.push_back(NodeT());
+nodes.push_back(NodeT());
 } else {
-	n = first_free_node;
+n = first_free_node;
-	first_free_node = nodes[n].next;
+first_free_node = nodes[n].next;
 }
 nodes[n].next = first_node;
 if (first_node != -1) nodes[first_node].prev = n;
 first_node = n;
 nodes[n].prev = -1;
 nodes[n].first_out = -1;
 return Node(n);
 }
 Edge addEdge(Node u, Node v) {
 int n;
 if (first_free_arc == -1) {
-	n = arcs.size();
+n = arcs.size();
-	arcs.push_back(ArcT());
+arcs.push_back(ArcT());
-	arcs.push_back(ArcT());
+arcs.push_back(ArcT());
 } else {
-	n = first_free_arc;
+n = first_free_arc;
-	first_free_arc = arcs[n].next_out;
+first_free_arc = arcs[n].next_out;
 }
 arcs[n].target = u.id;
 arcs[n | 1].target = v.id;
 arcs[n].next_out = nodes[v.id].first_out;
 if (nodes[v.id].first_out != -1) {
-	arcs[nodes[v.id].first_out].prev_out = n;
+arcs[nodes[v.id].first_out].prev_out = n;
 }
 arcs[n].prev_out = -1;
 nodes[v.id].first_out = n;
 arcs[n | 1].next_out = nodes[u.id].first_out;
 if (nodes[u.id].first_out != -1) {
-	arcs[nodes[u.id].first_out].prev_out = (n | 1);
+arcs[nodes[u.id].first_out].prev_out = (n | 1);
 }
 arcs[n | 1].prev_out = -1;
 nodes[u.id].first_out = (n | 1);
 return Edge(n / 2);
 }
 void erase(const Node& node) {
 int n = node.id;
 if(nodes[n].next != -1) {
-	nodes[nodes[n].next].prev = nodes[n].prev;
+nodes[nodes[n].next].prev = nodes[n].prev;
 }
 if(nodes[n].prev != -1) {
-	nodes[nodes[n].prev].next = nodes[n].next;
+nodes[nodes[n].prev].next = nodes[n].next;
 } else {
-	first_node = nodes[n].next;
+first_node = nodes[n].next;
 }
 nodes[n].next = first_free_node;
 first_free_node = n;
 nodes[n].prev = -2;
 }
 void erase(const Edge& edge) {
 int n = edge.id * 2;
 if (arcs[n].next_out != -1) {
-	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
+arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
 }
 if (arcs[n].prev_out != -1) {
-	arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
+arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 } else {
-	nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
+nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
 }
 if (arcs[n | 1].next_out != -1) {
-	arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
+arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
 }
 if (arcs[n | 1].prev_out != -1) {
-	arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
+arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
 } else {
-	nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
+nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
 }
 arcs[n].next_out = first_free_arc;
 first_free_arc = n;
 arcs[n].prev_out = -2;
 arcs[n | 1].prev_out = -2;
 }
 protected:
 void changeTarget(Edge e, Node n) {
 if(arcs[2 * e.id].next_out != -1) {
-	arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
+arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
 }
 if(arcs[2 * e.id].prev_out != -1) {
-	arcs[arcs[2 * e.id].prev_out].next_out =
+arcs[arcs[2 * e.id].prev_out].next_out =
 arcs[2 * e.id].next_out;
 } else {
 nodes[arcs[(2 * e.id) | 1].target].first_out =
 arcs[2 * e.id].next_out;
 }
 if (nodes[n.id].first_out != -1) {
-	arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
+arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
 }
 arcs[(2 * e.id) | 1].target = n.id;
 arcs[2 * e.id].prev_out = -1;
 arcs[2 * e.id].next_out = nodes[n.id].first_out;
 nodes[n.id].first_out = 2 * e.id;
 }
 void changeSource(Edge e, Node n) {
 if(arcs[(2 * e.id) | 1].next_out != -1) {
-	arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
+arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
 arcs[(2 * e.id) | 1].prev_out;
 }
 if(arcs[(2 * e.id) | 1].prev_out != -1) {
-	arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
+arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
 arcs[(2 * e.id) | 1].next_out;
 } else {
 nodes[arcs[2 * e.id].target].first_out =
 arcs[(2 * e.id) | 1].next_out;
 }
 if (nodes[n.id].first_out != -1) {
-	arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
+arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
 }
 arcs[2 * e.id].target = n.id;
 arcs[(2 * e.id) | 1].prev_out = -1;
 arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
 nodes[n.id].first_out = ((2 * e.id) | 1);
 /// \addtogroup graphs
 /// @{
 ///A general undirected graph structure.
 ///\ref ListGraph is a simple and fast <em>undirected graph</em>
 ///implementation based on static linked lists that are stored in
 ///\c std::vector structures.
 ///
 ///It conforms to the \ref concepts::Graph "Graph concept" and it
 ///also provides several useful additional functionalities.
 ///Most of the member functions and nested classes are documented
 ///only in the concept class.
 ///Assignment of ListGraph to another one is \e not allowed.
 ///Use copyGraph() instead.
 void operator=(const ListGraph &) {}
 public:
 /// Constructor
 /// Constructor.
 ///
 ListGraph() {}
 typedef ExtendedListGraphBase Parent;
 /// \brief Add a new edge to the graph.
 ///
 /// Add a new edge to the graph with source node \c s
 /// and target node \c t.
 /// \return the new edge.
 Edge addEdge(const Node& s, const Node& t) {
 return Parent::addEdge(s, t);
 }
 /// Node validity check
 /// This function gives back true if the given node is valid,
 /// ie. it is a real node of the graph.
 ///
 /// \warning A Node pointing to a removed item
 /// could become valid again later if new nodes are
 /// added to the graph.
 bool valid(Node n) const { return Parent::valid(n); }
 /// Arc validity check
 /// This function gives back true if the given arc is valid,
 /// ie. it is a real arc of the graph.
 ///
 /// \warning An Arc pointing to a removed item
 /// could become valid again later if new edges are
 /// added to the graph.
 bool valid(Arc a) const { return Parent::valid(a); }
 /// Edge validity check
 /// This function gives back true if the given edge is valid,
 /// ie. it is a real arc of the graph.
 ///
 /// \warning A Edge pointing to a removed item
 /// could become valid again later if new edges are
 /// added to the graph.
 bool valid(Edge e) const { return Parent::valid(e); }
 ///referencing the changed arc remain
 ///valid. However <tt>OutArcIt</tt>s are invalidated.
 ///
 ///\warning This functionality cannot be used together with the
 ///Snapshot feature.
 void changeSource(Edge e, Node n) {
 Parent::changeSource(e,n);
 }
 /// \brief Change the target of \c e to \c n
 ///
 /// This function changes the target of \c e to \c n.
 ///
 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
 /// valid. However the other iterators may be invalidated.
 ///
 ///\warning This functionality cannot be used together with the
 ///Snapshot feature.
 void changeTarget(Edge e, Node n) {
 Parent::changeTarget(e,n);
 }
 /// \brief Change the source of \c e to \c n
 ///
 /// This function changes the source of \c e to \c n.
 /// It also changes the proper node of the represented edge.
 ///
 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
 ///referencing the changed arc remain
 ///valid. However <tt>OutArcIt</tt>s are invalidated.
 ///
 ///\warning This functionality cannot be used together with the
 ///Snapshot feature.
 void changeSource(Arc e, Node n) {
 if (Parent::direction(e)) {
 Parent::changeSource(e,n);
 } else {
 Parent::changeTarget(e,n);
 }
 }
 /// \brief Change the target of \c e to \c n
 ///
 /// This function changes the target of \c e to \c n.
 /// It also changes the proper node of the represented edge.
 ///
 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
 ///referencing the changed arc remain
 ///valid. However <tt>InArcIt</tt>s are invalidated.
 ///
 ///\warning This functionality cannot be used together with the
 ///Snapshot feature.
 void changeTarget(Arc e, Node n) {
 if (Parent::direction(e)) {
 Parent::changeTarget(e,n);
 } else {
 Parent::changeSource(e,n);
 }
 }
 /// \brief Contract two nodes.
 ///
 /// This function contracts two nodes.
 /// Node \p b will be removed but instead of deleting
 ///
 ///\warning This functionality cannot be used together with the
 ///Snapshot feature.
 void contract(Node a, Node b, bool r = true) {
 for(IncEdgeIt e(*this, b); e!=INVALID;) {
-	IncEdgeIt f = e; ++f;
+IncEdgeIt f = e; ++f;
-	if (r && runningNode(e) == a) {
+if (r && runningNode(e) == a) {
-	  erase(e);
+erase(e);
-	} else if (source(e) == b) {
+} else if (source(e) == b) {
-	  changeSource(e, a);
+changeSource(e, a);
-	} else {
+} else {
-	  changeTarget(e, a);
+changeTarget(e, a);
-	}
+}
-	e = f;
+e = f;
 }
 erase(b);
 }
 ///
 /// The newly added nodes and edges can be removed
 /// using the restore() function.
 ///
 /// \warning Edge and node deletions and other modifications
 /// (e.g. changing nodes of edges, contracting nodes) cannot be
 /// restored. These events invalidate the snapshot.
 class Snapshot {
 protected:
 typedef Parent::NodeNotifier NodeNotifier;
 : snapshot(_snapshot) {}
 using NodeNotifier::ObserverBase::attach;
 using NodeNotifier::ObserverBase::detach;
 using NodeNotifier::ObserverBase::attached;
 protected:
 virtual void add(const Node& node) {
 snapshot.addNode(node);
 }
 virtual void add(const std::vector<Node>& nodes) {
 for (int i = nodes.size() - 1; i >= 0; ++i) {
 }
 }
 virtual void build() {
 Node node;
 std::vector<Node> nodes;
 for (notifier()->first(node); node != INVALID;
 notifier()->next(node)) {
 nodes.push_back(node);
 }
 for (int i = nodes.size() - 1; i >= 0; --i) {
 snapshot.addNode(nodes[i]);
 }
 }
 virtual void clear() {
 Node node;
 for (notifier()->first(node); node != INVALID;
 notifier()->next(node)) {
 snapshot.eraseNode(node);
 }
 }
 : snapshot(_snapshot) {}
 using EdgeNotifier::ObserverBase::attach;
 using EdgeNotifier::ObserverBase::detach;
 using EdgeNotifier::ObserverBase::attached;
 protected:
 virtual void add(const Edge& edge) {
 snapshot.addEdge(edge);
 }
 }
 }
 virtual void build() {
 Edge edge;
 std::vector<Edge> edges;
 for (notifier()->first(edge); edge != INVALID;
 notifier()->next(edge)) {
 edges.push_back(edge);
 }
 for (int i = edges.size() - 1; i >= 0; --i) {
 snapshot.addEdge(edges[i]);
 }
 }
 virtual void clear() {
 Edge edge;
 for (notifier()->first(edge); edge != INVALID;
 notifier()->next(edge)) {
 snapshot.eraseEdge(edge);
 }
 }
 std::list<Node> added_nodes;
 std::list<Edge> added_edges;
 void addNode(const Node& node) {
 added_nodes.push_front(node);
 }
 void eraseNode(const Node& node) {
 std::list<Node>::iterator it =
 std::find(added_nodes.begin(), added_nodes.end(), node);
 if (it == added_nodes.end()) {
 clear();
 edge_observer_proxy.detach();
 throw NodeNotifier::ImmediateDetach();
 added_nodes.erase(it);
 }
 }
 void addEdge(const Edge& edge) {
 added_edges.push_front(edge);
 }
 void eraseEdge(const Edge& edge) {
 std::list<Edge>::iterator it =
 std::find(added_edges.begin(), added_edges.end(), edge);
 if (it == added_edges.end()) {
 clear();
 node_observer_proxy.detach();
 throw EdgeNotifier::ImmediateDetach();
 added_edges.erase(it);
 }
 }
 void attach(ListGraph &_graph) {
-	graph = &_graph;
+graph = &_graph;
-	node_observer_proxy.attach(graph->notifier(Node()));
+node_observer_proxy.attach(graph->notifier(Node()));
 edge_observer_proxy.attach(graph->notifier(Edge()));
 }
 void detach() {
-	node_observer_proxy.detach();
+node_observer_proxy.detach();
-	edge_observer_proxy.detach();
+edge_observer_proxy.detach();
 }
 bool attached() const {
 return node_observer_proxy.attached();
 }
 void clear() {
 added_nodes.clear();
 added_edges.clear();
 }
 public:
 /// \brief Default constructor.
 ///
 /// Default constructor.
 /// To actually make a snapshot you must call save().
 Snapshot()
 : graph(0), node_observer_proxy(*this),
 edge_observer_proxy(*this) {}
 /// \brief Constructor that immediately makes a snapshot.
 ///
 /// This constructor immediately makes a snapshot of the graph.
 /// \param _graph The graph we make a snapshot of.
 Snapshot(ListGraph &_graph)
 : node_observer_proxy(*this),
 edge_observer_proxy(*this) {
-	attach(_graph);
+attach(_graph);
 }
 /// \brief Make a snapshot.
 ///
 /// Make a snapshot of the graph.
 ///
 /// This function can be called more than once. In case of a repeated
 detach();
 clear();
 }
 attach(_graph);
 }
 /// \brief Undo the changes until the last snapshot.
 //
 /// Undo the changes until the last snapshot created by save().
 void restore() {
-	detach();
+detach();
-	for(std::list<Edge>::iterator it = added_edges.begin();
+for(std::list<Edge>::iterator it = added_edges.begin();
 it != added_edges.end(); ++it) {
-	  graph->erase(*it);
+graph->erase(*it);
-	}
+}
-	for(std::list<Node>::iterator it = added_nodes.begin();
+for(std::list<Node>::iterator it = added_nodes.begin();
 it != added_nodes.end(); ++it) {
-	  graph->erase(*it);
+graph->erase(*it);
-	}
+}
 clear();
 }
 /// \brief Gives back true when the snapshot is valid.
 ///
 bool valid() const {
 return attached();
 }
 };
 };
 /// @}
 } //namespace lemon
 #endif

changeset 211	542dd614cbb4
parent 184	716b220697a0
child 212	1ae84dea7d09