I hope it works. The 'erase' functions hasn't been tested yet.
1.1 --- a/src/work/alpar/list_graph.h Sun Apr 25 14:25:04 2004 +0000
1.2 +++ b/src/work/alpar/list_graph.h Sun Apr 25 16:53:38 2004 +0000
1.3 @@ -4,7 +4,7 @@
1.4 #define HUGO_SMART_GRAPH_H
1.5
1.6 ///\file
1.7 -///\brief SmartGraph and SymSmartGraph classes.
1.8 +///\brief ListGraph and SymListGraph classes.
1.9
1.10 #include <vector>
1.11 #include <limits.h>
1.12 @@ -13,52 +13,63 @@
1.13
1.14 namespace hugo {
1.15
1.16 - class SymSmartGraph;
1.17 + class SymListGraph;
1.18
1.19 ///A smart graph class.
1.20
1.21 - ///This is a simple and fast graph implementation.
1.22 - ///It is also quite memory efficient, but at the price
1.23 - ///that <b> it does not support node and edge deletion</b>.
1.24 + ///This is a simple and fast erasable graph implementation.
1.25 + ///
1.26 ///It conforms to the graph interface documented under
1.27 ///the description of \ref GraphSkeleton.
1.28 ///\sa \ref GraphSkeleton.
1.29 - class SmartGraph {
1.30 + class ListGraph {
1.31
1.32 + //Nodes are double linked.
1.33 + //The free nodes are only single linked using the "next" field.
1.34 struct NodeT
1.35 {
1.36 - int first_in,first_out;
1.37 - NodeT() : first_in(-1), first_out(-1) {}
1.38 + int first_in,first_out;
1.39 + int prev, next;
1.40 + // NodeT() {}
1.41 };
1.42 + //Edges are double linked.
1.43 + //The free edges are only single linked using the "next_in" field.
1.44 struct EdgeT
1.45 {
1.46 - int head, tail, next_in, next_out;
1.47 + int head, tail;
1.48 + int prev_in, prev_out;
1.49 + int next_in, next_out;
1.50 //FIXME: is this necessary?
1.51 - EdgeT() : next_in(-1), next_out(-1) {}
1.52 + // EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}
1.53 };
1.54
1.55 std::vector<NodeT> nodes;
1.56 -
1.57 + //The first node
1.58 + int first_node;
1.59 + //The first free node
1.60 + int first_free_node;
1.61 std::vector<EdgeT> edges;
1.62 + //The first free edge
1.63 + int first_free_edge;
1.64
1.65 - protected:
1.66 + protected:
1.67
1.68 template <typename Key> class DynMapBase
1.69 {
1.70 protected:
1.71 - const SmartGraph* G;
1.72 + const ListGraph* G;
1.73 public:
1.74 virtual void add(const Key k) = NULL;
1.75 virtual void erase(const Key k) = NULL;
1.76 - DynMapBase(const SmartGraph &_G) : G(&_G) {}
1.77 + DynMapBase(const ListGraph &_G) : G(&_G) {}
1.78 virtual ~DynMapBase() {}
1.79 - friend class SmartGraph;
1.80 + friend class ListGraph;
1.81 };
1.82
1.83 public:
1.84 template <typename T> class EdgeMap;
1.85 template <typename T> class EdgeMap;
1.86 -
1.87 +
1.88 class Node;
1.89 class Edge;
1.90
1.91 @@ -84,10 +95,14 @@
1.92
1.93 public:
1.94
1.95 - SmartGraph() : nodes(), edges() { }
1.96 - SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
1.97 + ListGraph() : nodes(), first_node(-1),
1.98 + first_free_node(-1), edges(), first_free_edge(-1) {}
1.99 + ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
1.100 + first_free_node(_g.first_free_node),
1.101 + edges(_g.edges),
1.102 + first_free_edge(_g.first_free_edge) {}
1.103
1.104 - ~SmartGraph()
1.105 + ~ListGraph()
1.106 {
1.107 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.108 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1.109 @@ -139,45 +154,151 @@
1.110 { It tmp(it); return next(tmp); }
1.111
1.112 NodeIt& next(NodeIt& it) const {
1.113 - it.n=(it.n+2)%(nodes.size()+1)-1;
1.114 + it.n=nodes[it.n].next;
1.115 return it;
1.116 }
1.117 OutEdgeIt& next(OutEdgeIt& it) const
1.118 { it.n=edges[it.n].next_out; return it; }
1.119 InEdgeIt& next(InEdgeIt& it) const
1.120 { it.n=edges[it.n].next_in; return it; }
1.121 - EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
1.122 + EdgeIt& next(EdgeIt& it) const {
1.123 + if(edges[it.n].next_in!=-1) {
1.124 + it.n=edges[it.n].next_in;
1.125 + }
1.126 + else {
1.127 + int n;
1.128 + for(n=nodes[edges[it.n].head].next;
1.129 + n!=-1 && nodes[n].first_in == -1;
1.130 + n = nodes[n].next) ;
1.131 + it.n = (n==-1)?-1:nodes[n].first_in;
1.132 + }
1.133 + return it;
1.134 + }
1.135
1.136 int id(Node v) const { return v.n; }
1.137 int id(Edge e) const { return e.n; }
1.138
1.139 + /// Adds a new node to the graph.
1.140 +
1.141 + /// \todo It adds the nodes in a reversed order.
1.142 + /// (i.e. the lastly added node becomes the first.)
1.143 Node addNode() {
1.144 - Node n; n.n=nodes.size();
1.145 - nodes.push_back(NodeT()); //FIXME: Hmmm...
1.146 + int n;
1.147 +
1.148 + if(first_free_node==-1)
1.149 + {
1.150 + n = nodes.size();
1.151 + nodes.push_back(NodeT());
1.152 + }
1.153 + else {
1.154 + n = first_free_node;
1.155 + first_free_node = nodes[n].next;
1.156 + }
1.157 +
1.158 + nodes[n].next = first_node;
1.159 + if(first_node != -1) nodes[first_node].prev = n;
1.160 + first_node = n;
1.161 + nodes[n].prev = -1;
1.162 +
1.163 + nodes[n].first_in = nodes[n].first_out = -1;
1.164 +
1.165 + Node nn; nn.n=n;
1.166
1.167 + //Update dynamic maps
1.168 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.169 - i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
1.170 + i!=dyn_node_maps.end(); ++i) (**i).add(nn);
1.171
1.172 - return n;
1.173 + return nn;
1.174 }
1.175
1.176 Edge addEdge(Node u, Node v) {
1.177 - Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
1.178 - edges[e.n].tail=u.n; edges[e.n].head=v.n;
1.179 - edges[e.n].next_out=nodes[u.n].first_out;
1.180 - edges[e.n].next_in=nodes[v.n].first_in;
1.181 - nodes[u.n].first_out=nodes[v.n].first_in=e.n;
1.182 + int n;
1.183 +
1.184 + if(first_free_edge==-1)
1.185 + {
1.186 + n = edges.size();
1.187 + edges.push_back(EdgeT());
1.188 + }
1.189 + else {
1.190 + n = first_free_edge;
1.191 + first_free_edge = edges[n].next_in;
1.192 + }
1.193 +
1.194 + edges[n].tail = u.n; edges[n].head = v.n;
1.195
1.196 + edges[n].next_out = nodes[u.n].first_out;
1.197 + if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
1.198 + edges[n].next_in = nodes[v.n].first_in;
1.199 + if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
1.200 + edges[n].prev_in = edges[n].prev_out = -1;
1.201 +
1.202 + nodes[u.n].first_out = nodes[v.n].first_in = n;
1.203 +
1.204 + Edge e; e.n=n;
1.205 +
1.206 + //Update dynamic maps
1.207 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.208 i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1.209
1.210 return e;
1.211 }
1.212
1.213 - void clear() {nodes.clear();edges.clear();}
1.214 + private:
1.215 + void eraseEdge(int n) {
1.216 +
1.217 + if(edges[n].next_in!=-1)
1.218 + edges[edges[n].next_in].prev_in = edges[n].prev_in;
1.219 + if(edges[n].prev_in!=-1)
1.220 + edges[edges[n].prev_in].next_in = edges[n].next_in;
1.221 + else nodes[edges[n].head].first_in = edges[n].next_in;
1.222 +
1.223 + if(edges[n].next_out!=-1)
1.224 + edges[edges[n].next_out].prev_out = edges[n].prev_out;
1.225 + if(edges[n].prev_out!=-1)
1.226 + edges[edges[n].prev_out].next_out = edges[n].next_out;
1.227 + else nodes[edges[n].tail].first_out = edges[n].next_out;
1.228 +
1.229 + edges[n].next_in = first_free_edge;
1.230 + first_free_edge = -1;
1.231 +
1.232 + //Update dynamic maps
1.233 + Edge e; e.n=n;
1.234 + for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.235 + i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1.236 + }
1.237 +
1.238 + public:
1.239 +
1.240 + void erase(Node nn) {
1.241 + int n=nn.n;
1.242 +
1.243 + int m;
1.244 + while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1.245 + while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1.246 +
1.247 + if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
1.248 + if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
1.249 + else first_node = nodes[n].next;
1.250 +
1.251 + nodes[n].next = first_free_node;
1.252 + first_free_node = n;
1.253 +
1.254 + //Update dynamic maps
1.255 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.256 + i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
1.257 + }
1.258 +
1.259 + void erase(Edge e) { eraseEdge(e.n); }
1.260 +
1.261 + ///\bug Dynamic maps must be updated!
1.262 + ///
1.263 + void clear() {
1.264 + nodes.clear();edges.clear();
1.265 + first_node=first_free_node=first_free_edge=-1;
1.266 + }
1.267
1.268 class Node {
1.269 - friend class SmartGraph;
1.270 + friend class ListGraph;
1.271 template <typename T> friend class NodeMap;
1.272
1.273 friend class Edge;
1.274 @@ -187,7 +308,7 @@
1.275
1.276 protected:
1.277 int n;
1.278 - friend int SmartGraph::id(Node v) const;
1.279 + friend int ListGraph::id(Node v) const;
1.280 Node(int nn) {n=nn;}
1.281 public:
1.282 Node() {}
1.283 @@ -198,24 +319,24 @@
1.284 };
1.285
1.286 class NodeIt : public Node {
1.287 - friend class SmartGraph;
1.288 + friend class ListGraph;
1.289 public:
1.290 - NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
1.291 + NodeIt(const ListGraph& G) : Node(G.first_node) { }
1.292 NodeIt() : Node() { }
1.293 };
1.294
1.295 class Edge {
1.296 - friend class SmartGraph;
1.297 + friend class ListGraph;
1.298 template <typename T> friend class EdgeMap;
1.299
1.300 - //template <typename T> friend class SymSmartGraph::SymEdgeMap;
1.301 - //friend Edge SymSmartGraph::opposite(Edge) const;
1.302 + //template <typename T> friend class SymListGraph::SymEdgeMap;
1.303 + //friend Edge SymListGraph::opposite(Edge) const;
1.304
1.305 friend class Node;
1.306 friend class NodeIt;
1.307 protected:
1.308 int n;
1.309 - friend int SmartGraph::id(Edge e) const;
1.310 + friend int ListGraph::id(Edge e) const;
1.311
1.312 Edge(int nn) {n=nn;}
1.313 public:
1.314 @@ -225,38 +346,43 @@
1.315 bool operator!=(const Edge i) const {return n!=i.n;}
1.316 bool operator<(const Edge i) const {return n<i.n;}
1.317 ///\bug This is a workaround until somebody tells me how to
1.318 - ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
1.319 + ///make class \c SymListGraph::SymEdgeMap friend of Edge
1.320 int &idref() {return n;}
1.321 const int &idref() const {return n;}
1.322 };
1.323
1.324 class EdgeIt : public Edge {
1.325 - friend class SmartGraph;
1.326 + friend class ListGraph;
1.327 public:
1.328 - EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
1.329 + EdgeIt(const ListGraph& G) : Edge() {
1.330 + int m;
1.331 + for(m=G.first_node;
1.332 + m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
1.333 + n = (m==-1)?-1:G.nodes[m].first_in;
1.334 + }
1.335 EdgeIt (Invalid i) : Edge(i) { }
1.336 EdgeIt() : Edge() { }
1.337 ///\bug This is a workaround until somebody tells me how to
1.338 - ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
1.339 + ///make class \c SymListGraph::SymEdgeMap friend of Edge
1.340 int &idref() {return n;}
1.341 };
1.342
1.343 class OutEdgeIt : public Edge {
1.344 - friend class SmartGraph;
1.345 + friend class ListGraph;
1.346 public:
1.347 OutEdgeIt() : Edge() { }
1.348 OutEdgeIt (Invalid i) : Edge(i) { }
1.349
1.350 - OutEdgeIt(const SmartGraph& G,const Node v)
1.351 + OutEdgeIt(const ListGraph& G,const Node v)
1.352 : Edge(G.nodes[v.n].first_out) {}
1.353 };
1.354
1.355 class InEdgeIt : public Edge {
1.356 - friend class SmartGraph;
1.357 + friend class ListGraph;
1.358 public:
1.359 InEdgeIt() : Edge() { }
1.360 InEdgeIt (Invalid i) : Edge(i) { }
1.361 - InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
1.362 + InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
1.363 };
1.364
1.365 template <typename T> class NodeMap : public DynMapBase<Node>
1.366 @@ -267,12 +393,12 @@
1.367 typedef T ValueType;
1.368 typedef Node KeyType;
1.369
1.370 - NodeMap(const SmartGraph &_G) :
1.371 + NodeMap(const ListGraph &_G) :
1.372 DynMapBase<Node>(_G), container(_G.maxNodeId())
1.373 {
1.374 G->dyn_node_maps.push_back(this);
1.375 }
1.376 - NodeMap(const SmartGraph &_G,const T &t) :
1.377 + NodeMap(const ListGraph &_G,const T &t) :
1.378 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1.379 {
1.380 G->dyn_node_maps.push_back(this);
1.381 @@ -357,14 +483,14 @@
1.382 typedef T ValueType;
1.383 typedef Edge KeyType;
1.384
1.385 - EdgeMap(const SmartGraph &_G) :
1.386 + EdgeMap(const ListGraph &_G) :
1.387 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1.388 {
1.389 //FIXME: What if there are empty Id's?
1.390 //FIXME: Can I use 'this' in a constructor?
1.391 G->dyn_edge_maps.push_back(this);
1.392 }
1.393 - EdgeMap(const SmartGraph &_G,const T &t) :
1.394 + EdgeMap(const ListGraph &_G,const T &t) :
1.395 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1.396 {
1.397 G->dyn_edge_maps.push_back(this);
1.398 @@ -446,7 +572,7 @@
1.399 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
1.400 ///of oppositely directed edges.
1.401 ///There is a new edge map type called
1.402 - ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
1.403 + ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
1.404 ///that complements this
1.405 ///feature by
1.406 ///storing shared values for the edge pairs. The usual
1.407 @@ -456,25 +582,29 @@
1.408 ///
1.409 ///The oppositely directed edge can also be obtained easily
1.410 ///using \ref opposite.
1.411 - ///\warning It shares the similarity with \ref SmartGraph that
1.412 - ///it is not possible to delete edges or nodes from the graph.
1.413 - //\sa \ref SmartGraph.
1.414 + ///
1.415 + ///Here erase(Edge) deletes a pair of edges.
1.416 + ///
1.417 + ///\todo this date structure need some reconsiderations. Maybe it
1.418 + ///should be implemented independently from ListGraph.
1.419
1.420 - class SymSmartGraph : public SmartGraph
1.421 + class SymListGraph : public ListGraph
1.422 {
1.423 public:
1.424 template<typename T> class SymEdgeMap;
1.425 template<typename T> friend class SymEdgeMap;
1.426
1.427 - SymSmartGraph() : SmartGraph() { }
1.428 - SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
1.429 + SymListGraph() : ListGraph() { }
1.430 + SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
1.431 + ///Adds a pair of oppositely directed edges to the graph.
1.432 Edge addEdge(Node u, Node v)
1.433 {
1.434 - Edge e = SmartGraph::addEdge(u,v);
1.435 - SmartGraph::addEdge(v,u);
1.436 + Edge e = ListGraph::addEdge(u,v);
1.437 + ListGraph::addEdge(v,u);
1.438 return e;
1.439 }
1.440
1.441 + void erase(Node n) { ListGraph::erase(n); }
1.442 ///The oppositely directed edge.
1.443
1.444 ///Returns the oppositely directed
1.445 @@ -486,6 +616,12 @@
1.446 return f;
1.447 }
1.448
1.449 + ///Removes a pair of oppositely directed edges to the graph.
1.450 + void erase(Edge e) {
1.451 + ListGraph::erase(opposite(e));
1.452 + ListGraph::erase(e);
1.453 + }
1.454 +
1.455 ///Common data storage for the edge pairs.
1.456
1.457 ///This map makes it possible to store data shared by the oppositely
1.458 @@ -498,12 +634,12 @@
1.459 typedef T ValueType;
1.460 typedef Edge KeyType;
1.461
1.462 - SymEdgeMap(const SymSmartGraph &_G) :
1.463 + SymEdgeMap(const SymListGraph &_G) :
1.464 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
1.465 {
1.466 - static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
1.467 + static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
1.468 }
1.469 - SymEdgeMap(const SymSmartGraph &_G,const T &t) :
1.470 + SymEdgeMap(const SymListGraph &_G,const T &t) :
1.471 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
1.472 {
1.473 G->dyn_edge_maps.push_back(this);
1.474 @@ -535,14 +671,14 @@
1.475 {
1.476 if(G) {
1.477 std::vector<DynMapBase<Edge>* >::iterator i;
1.478 - for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
1.479 - i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
1.480 + for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
1.481 + i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
1.482 && *i!=this; ++i) ;
1.483 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1.484 //A better way to do that: (Is this really important?)
1.485 if(*i==this) {
1.486 - *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
1.487 - static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
1.488 + *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
1.489 + static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
1.490 }
1.491 }
1.492 }
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/alpar/list_graph_demo.cc Sun Apr 25 16:53:38 2004 +0000
2.3 @@ -0,0 +1,124 @@
2.4 +#include<list_graph.h>
2.5 +#include<skeletons/graph.h>
2.6 +
2.7 +#include <iostream>
2.8 +#include <vector>
2.9 +
2.10 +using namespace hugo;
2.11 +
2.12 +typedef ListGraph Graph;
2.13 +//typedef GraphSkeleton Graph;
2.14 +
2.15 +
2.16 +Graph::OutEdgeIt safeFirstOut(const Graph &G, Graph::Node n)
2.17 +{
2.18 + return G.valid(n) ? Graph::OutEdgeIt(G,n):INVALID;
2.19 +}
2.20 +
2.21 +int main()
2.22 +{
2.23 +
2.24 + typedef Graph::Edge Edge;
2.25 + typedef Graph::InEdgeIt InEdgeIt;
2.26 + typedef Graph::OutEdgeIt OutEdgeIt;
2.27 + typedef Graph::EdgeIt EdgeIt;
2.28 + typedef Graph::Node Node;
2.29 + typedef Graph::NodeIt NodeIt;
2.30 +
2.31 + Graph G;
2.32 +
2.33 + {
2.34 + NodeIt n;
2.35 +
2.36 + for(int i=0;i<10;i++) G.addNode();
2.37 + for(G.first(n);G.valid(n);G.next(n))
2.38 + for(NodeIt m(G);m!=INVALID;G.next(m))
2.39 + if(n!=m) G.addEdge(n,m);
2.40 +
2.41 + OutEdgeIt e = safeFirstOut(G,n);
2.42 + OutEdgeIt f = safeFirstOut(G,NodeIt(G));
2.43 +
2.44 +
2.45 + InEdgeIt i(INVALID), j;
2.46 + InEdgeIt ii(i);
2.47 + ii=G.first(i,n);
2.48 + ii=G.next(i);
2.49 +
2.50 + OutEdgeIt o(INVALID), oo;
2.51 + OutEdgeIt ooo(oo);
2.52 + oo=G.first(o,n);
2.53 + oo=G.next(o);
2.54 +
2.55 + EdgeIt ei(INVALID), eie;
2.56 + EdgeIt eiee(ei);
2.57 + eie=G.first(ei);
2.58 + eie=G.next(ei);
2.59 +
2.60 + Edge eee(i);
2.61 + eee=o;
2.62 + eee=eie;
2.63 +
2.64 +
2.65 + bool tm;
2.66 + tm = G.valid(n) && G.valid(i) && G.valid(o) && G.valid(ei);
2.67 +
2.68 + std::vector<InEdgeIt> v(10);
2.69 + std::vector<InEdgeIt> w(10,INVALID);
2.70 +
2.71 + }
2.72 +
2.73 + // Test of maps
2.74 +
2.75 + G.clear();
2.76 +
2.77 + for(int i=0;i<10;i++) G.addNode();
2.78 + for(NodeIt i(G);G.valid(i);G.next(i))
2.79 + for(NodeIt j(G);G.valid(j);G.next(j))
2.80 + if(i<j) G.addEdge(i,j); //The iterators are comparable
2.81 +
2.82 + Graph::NodeMap<int> n(G);
2.83 + int count=0;
2.84 + for(NodeIt i(G);G.valid(i);G.next(i)) n[i]=count++;
2.85 +
2.86 + Graph::NodeMap<int> nn=n;
2.87 + Graph::NodeMap<double> dd=n;
2.88 +
2.89 + n = nn;
2.90 +
2.91 + dd = nn;
2.92 +
2.93 + Graph::EdgeMap<int> emap(G);
2.94 +
2.95 + // Test of SymListGraph
2.96 +
2.97 + {
2.98 + typedef SymListGraph Graph;
2.99 + typedef Graph::Edge Edge;
2.100 + typedef Graph::InEdgeIt InEdgeIt;
2.101 + typedef Graph::OutEdgeIt OutEdgeIt;
2.102 + typedef Graph::EdgeIt EdgeIt;
2.103 + typedef Graph::Node Node;
2.104 + typedef Graph::NodeIt NodeIt;
2.105 +
2.106 + Graph G;
2.107 +
2.108 + for(int i=0;i<10;i++) G.addNode();
2.109 + for(NodeIt i(G);G.valid(i);G.next(i))
2.110 + for(NodeIt j(G);G.valid(j);G.next(j))
2.111 + if(i<j) G.addEdge(i,j); //The iterators are comparable
2.112 +
2.113 + Graph::EdgeMap<int> em(G);
2.114 + Graph::SymEdgeMap<int> sm(G);
2.115 + for(EdgeIt e(G);G.valid(e);G.next(e)) em[e]=G.id(e);
2.116 + for(EdgeIt e(G);G.valid(e);G.next(e))
2.117 + if(G.tail(e)<G.head(e)) sm[e]=G.id(e);
2.118 +
2.119 + for(EdgeIt e(G);G.valid(e);G.next(e))
2.120 + std::cout << G.id(G.tail(e)) << "->" << G.id(G.head(e))
2.121 + << ": id=" << G.id(e) << " oppid=" << G.id(G.opposite(e))
2.122 + << " em=" << em[e]
2.123 + << " sm=" << sm[e] << "\n";
2.124 +
2.125 + }
2.126 +
2.127 +}