1.1 --- a/lemon/smart_graph.h Fri Nov 13 12:33:33 2009 +0100
1.2 +++ b/lemon/smart_graph.h Thu Dec 10 17:05:35 2009 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2008
1.8 + * Copyright (C) 2003-2009
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -55,7 +55,7 @@
1.13
1.14 public:
1.15
1.16 - typedef SmartDigraphBase Graph;
1.17 + typedef SmartDigraphBase Digraph;
1.18
1.19 class Node;
1.20 class Arc;
1.21 @@ -67,7 +67,7 @@
1.22 : nodes(_g.nodes), arcs(_g.arcs) { }
1.23
1.24 typedef True NodeNumTag;
1.25 - typedef True EdgeNumTag;
1.26 + typedef True ArcNumTag;
1.27
1.28 int nodeNum() const { return nodes.size(); }
1.29 int arcNum() const { return arcs.size(); }
1.30 @@ -191,14 +191,10 @@
1.31 ///It is also quite memory efficient, but at the price
1.32 ///that <b> it does support only limited (only stack-like)
1.33 ///node and arc deletions</b>.
1.34 - ///It conforms to the \ref concepts::Digraph "Digraph concept" with
1.35 - ///an important extra feature that its maps are real \ref
1.36 - ///concepts::ReferenceMap "reference map"s.
1.37 + ///It fully conforms to the \ref concepts::Digraph "Digraph concept".
1.38 ///
1.39 ///\sa concepts::Digraph.
1.40 class SmartDigraph : public ExtendedSmartDigraphBase {
1.41 - public:
1.42 -
1.43 typedef ExtendedSmartDigraphBase Parent;
1.44
1.45 private:
1.46 @@ -225,15 +221,15 @@
1.47
1.48 ///Add a new node to the digraph.
1.49
1.50 - /// \return the new node.
1.51 - ///
1.52 + /// Add a new node to the digraph.
1.53 + /// \return The new node.
1.54 Node addNode() { return Parent::addNode(); }
1.55
1.56 ///Add a new arc to the digraph.
1.57
1.58 ///Add a new arc to the digraph with source node \c s
1.59 ///and target node \c t.
1.60 - ///\return the new arc.
1.61 + ///\return The new arc.
1.62 Arc addArc(const Node& s, const Node& t) {
1.63 return Parent::addArc(s, t);
1.64 }
1.65 @@ -305,7 +301,9 @@
1.66 Node b = addNode();
1.67 nodes[b._id].first_out=nodes[n._id].first_out;
1.68 nodes[n._id].first_out=-1;
1.69 - for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
1.70 + for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
1.71 + arcs[i].source=b._id;
1.72 + }
1.73 if(connect) addArc(n,b);
1.74 return b;
1.75 }
1.76 @@ -420,7 +418,7 @@
1.77
1.78 public:
1.79
1.80 - typedef SmartGraphBase Digraph;
1.81 + typedef SmartGraphBase Graph;
1.82
1.83 class Node;
1.84 class Arc;
1.85 @@ -464,8 +462,8 @@
1.86 explicit Arc(int id) { _id = id;}
1.87
1.88 public:
1.89 - operator Edge() const {
1.90 - return _id != -1 ? edgeFromId(_id / 2) : INVALID;
1.91 + operator Edge() const {
1.92 + return _id != -1 ? edgeFromId(_id / 2) : INVALID;
1.93 }
1.94
1.95 Arc() {}
1.96 @@ -480,6 +478,13 @@
1.97 SmartGraphBase()
1.98 : nodes(), arcs() {}
1.99
1.100 + typedef True NodeNumTag;
1.101 + typedef True EdgeNumTag;
1.102 + typedef True ArcNumTag;
1.103 +
1.104 + int nodeNum() const { return nodes.size(); }
1.105 + int edgeNum() const { return arcs.size() / 2; }
1.106 + int arcNum() const { return arcs.size(); }
1.107
1.108 int maxNodeId() const { return nodes.size()-1; }
1.109 int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.110 @@ -620,16 +625,12 @@
1.111 /// It is also quite memory efficient, but at the price
1.112 /// that <b> it does support only limited (only stack-like)
1.113 /// node and arc deletions</b>.
1.114 - /// Except from this it conforms to
1.115 - /// the \ref concepts::Graph "Graph concept".
1.116 - ///
1.117 - /// It also has an
1.118 - /// important extra feature that
1.119 - /// its maps are real \ref concepts::ReferenceMap "reference map"s.
1.120 + /// It fully conforms to the \ref concepts::Graph "Graph concept".
1.121 ///
1.122 /// \sa concepts::Graph.
1.123 - ///
1.124 class SmartGraph : public ExtendedSmartGraphBase {
1.125 + typedef ExtendedSmartGraphBase Parent;
1.126 +
1.127 private:
1.128
1.129 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
1.130 @@ -647,8 +648,6 @@
1.131
1.132 public:
1.133
1.134 - typedef ExtendedSmartGraphBase Parent;
1.135 -
1.136 /// Constructor
1.137
1.138 /// Constructor.
1.139 @@ -657,15 +656,15 @@
1.140
1.141 ///Add a new node to the graph.
1.142
1.143 - /// \return the new node.
1.144 - ///
1.145 + /// Add a new node to the graph.
1.146 + /// \return The new node.
1.147 Node addNode() { return Parent::addNode(); }
1.148
1.149 ///Add a new edge to the graph.
1.150
1.151 ///Add a new edge to the graph with node \c s
1.152 ///and \c t.
1.153 - ///\return the new edge.
1.154 + ///\return The new edge.
1.155 Edge addEdge(const Node& s, const Node& t) {
1.156 return Parent::addEdge(s, t);
1.157 }
1.158 @@ -728,8 +727,8 @@
1.159 dir.push_back(arcFromId(n));
1.160 dir.push_back(arcFromId(n-1));
1.161 Parent::notifier(Arc()).erase(dir);
1.162 - nodes[arcs[n].target].first_out=arcs[n].next_out;
1.163 - nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
1.164 + nodes[arcs[n-1].target].first_out=arcs[n].next_out;
1.165 + nodes[arcs[n].target].first_out=arcs[n-1].next_out;
1.166 arcs.pop_back();
1.167 arcs.pop_back();
1.168 }