1.1 --- a/src/work/alpar/dijkstra/dijkstra.cc Sat May 08 16:04:28 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,117 +0,0 @@
1.4 -#include <iostream>
1.5 -#include <fstream>
1.6 -
1.7 -#include <smart_graph.h>
1.8 -#include <list_graph.h>
1.9 -#include <dimacs.h>
1.10 -#include <dijkstra.h>
1.11 -#include <time_measure.h>
1.12 -
1.13 -#include <bin_heap.h>
1.14 -#include <fib_heap.h>
1.15 -
1.16 -using namespace hugo;
1.17 -
1.18 -int main(int, char **) {
1.19 - typedef SmartGraph::Node Node;
1.20 - typedef SmartGraph::NodeIt NodeIt;
1.21 - typedef SmartGraph::InEdgeIt InEdgeIt;
1.22 -
1.23 - SmartGraph G;
1.24 - Node s, t;
1.25 - SmartGraph::EdgeMap<int> cap(G);
1.26 - Timer tim;
1.27 - std::cout << "DIMACS load ..." << std::endl;
1.28 - readDimacsMaxFlow(std::cin, G, s, t, cap);
1.29 - std::cout << " " << tim <<std::endl;
1.30 -
1.31 - std::cout << "dijkstra demo ..." << std::endl;
1.32 -
1.33 - //double pre_time=currTime();
1.34 - tim.reset();
1.35 -// Dijkstra <SmartGraph,
1.36 -// SmartGraph::EdgeMap<int>,
1.37 -// FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> >
1.38 -// > dijkstra_test(G, cap);
1.39 -
1.40 - Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, FibHeap >
1.41 - dijkstra_test(G, cap);
1.42 -
1.43 - dijkstra_test.run(s);
1.44 - //double post_time=currTime();
1.45 -
1.46 - std::cout << "running time with fib_heap: "
1.47 - // << post_time-pre_time << " sec"
1.48 - << tim
1.49 - << std::endl;
1.50 -
1.51 - //pre_time=currTime();
1.52 - tim.reset();
1.53 -// Dijkstra < SmartGraph,
1.54 -// SmartGraph::EdgeMap<int>,
1.55 -// BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > >
1.56 -// dijkstra_test2(G, cap);
1.57 -
1.58 - Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, BinHeap >
1.59 - dijkstra_test2(G, cap);
1.60 -
1.61 - dijkstra_test2.run(s);
1.62 - //post_time=currTime();
1.63 -
1.64 - std::cout << "running time with bin_heap: "
1.65 - // << post_time-pre_time << " sec"
1.66 - << tim
1.67 - << std::endl;
1.68 -
1.69 -
1.70 - int hiba_fib=0;
1.71 - int hiba_bin=0;
1.72 - NodeIt u;
1.73 - for ( G.first(u) ; G.valid(u); G.next(u) ) {
1.74 - InEdgeIt e;
1.75 - for ( G.first(e,u); G.valid(e); G.next(e) ) {
1.76 - Node v=G.tail(e);
1.77 - if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
1.78 - {
1.79 - std::cout<<"Hibas el a fibonaccis Dijkstraban: "
1.80 - << dijkstra_test.dist(u) - dijkstra_test.dist(v) -
1.81 - cap[e]<<std::endl;
1.82 - ++hiba_fib;
1.83 - }
1.84 - if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
1.85 - {
1.86 - std::cout<<"Hibas el a binarisos Dijkstraban: "
1.87 - << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) -
1.88 - cap[e]<<std::endl;
1.89 - ++hiba_bin;
1.90 - }
1.91 - if ( e==dijkstra_test.pred(u) &&
1.92 - dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
1.93 - {
1.94 - std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
1.95 - dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
1.96 - ++hiba_fib;
1.97 - }
1.98 - if ( e==dijkstra_test2.pred(u) &&
1.99 - dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
1.100 - {
1.101 - std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
1.102 - dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
1.103 - ++hiba_bin;
1.104 - }
1.105 - }
1.106 -
1.107 - if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) )
1.108 - std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
1.109 -
1.110 -
1.111 - }
1.112 -
1.113 - std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
1.114 - << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
1.115 -
1.116 - std::cout << "Hibas elek szama a binarisos Dijkstraban: "
1.117 - << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
1.118 -
1.119 - return 0;
1.120 -}
2.1 --- a/src/work/alpar/dijkstra/makefile Sat May 08 16:04:28 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,16 +0,0 @@
2.4 -CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
2.5 -CXX2 = g++-2.95
2.6 -CXXFLAGS = -W -Wall -ansi -pedantic
2.7 -LEDAROOT ?= /ledasrc/LEDA-4.1
2.8 -
2.9 -BINARIES = dijkstra
2.10 -
2.11 -all: $(BINARIES)
2.12 -
2.13 -dijkstra:
2.14 - $(CXX3) $(CXXFLAGS) -O3 -I. -I../../../include -I../../../include/skeleton -I../../jacint -I../.. -I../../marci -I../../alpar -o dijkstra dijkstra.cc
2.15 -
2.16 -clean:
2.17 - $(RM) *.o $(BINARIES) .depend
2.18 -
2.19 -.PHONY: all clean dep depend
3.1 --- a/src/work/alpar/smart_graph.h Sat May 08 16:04:28 2004 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,595 +0,0 @@
3.4 -// -*- mode:C++ -*-
3.5 -
3.6 -#ifndef HUGO_SMART_GRAPH_H
3.7 -#define HUGO_SMART_GRAPH_H
3.8 -
3.9 -///\file
3.10 -///\brief SmartGraph and SymSmartGraph classes.
3.11 -
3.12 -#include <vector>
3.13 -#include <limits.h>
3.14 -
3.15 -#include "invalid.h"
3.16 -
3.17 -namespace hugo {
3.18 -
3.19 - class SymSmartGraph;
3.20 -
3.21 - ///A smart graph class.
3.22 -
3.23 - ///This is a simple and fast graph implementation.
3.24 - ///It is also quite memory efficient, but at the price
3.25 - ///that <b> it does not support node and edge deletion</b>.
3.26 - ///It conforms to the graph interface documented under
3.27 - ///the description of \ref GraphSkeleton.
3.28 - ///\sa \ref GraphSkeleton.
3.29 - class SmartGraph {
3.30 -
3.31 - struct NodeT
3.32 - {
3.33 - int first_in,first_out;
3.34 - NodeT() : first_in(-1), first_out(-1) {}
3.35 - };
3.36 - struct EdgeT
3.37 - {
3.38 - int head, tail, next_in, next_out;
3.39 - //FIXME: is this necessary?
3.40 - EdgeT() : next_in(-1), next_out(-1) {}
3.41 - };
3.42 -
3.43 - std::vector<NodeT> nodes;
3.44 -
3.45 - std::vector<EdgeT> edges;
3.46 -
3.47 - protected:
3.48 -
3.49 - template <typename Key> class DynMapBase
3.50 - {
3.51 - protected:
3.52 - const SmartGraph* G;
3.53 - public:
3.54 - virtual void add(const Key k) = NULL;
3.55 - virtual void erase(const Key k) = NULL;
3.56 - DynMapBase(const SmartGraph &_G) : G(&_G) {}
3.57 - virtual ~DynMapBase() {}
3.58 - friend class SmartGraph;
3.59 - };
3.60 -
3.61 - public:
3.62 - template <typename T> class EdgeMap;
3.63 - template <typename T> class EdgeMap;
3.64 -
3.65 - class Node;
3.66 - class Edge;
3.67 -
3.68 - // protected:
3.69 - // HELPME:
3.70 - protected:
3.71 - ///\bug It must be public because of SymEdgeMap.
3.72 - ///
3.73 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
3.74 - ///\bug It must be public because of SymEdgeMap.
3.75 - ///
3.76 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
3.77 -
3.78 - public:
3.79 -
3.80 - class NodeIt;
3.81 - class EdgeIt;
3.82 - class OutEdgeIt;
3.83 - class InEdgeIt;
3.84 -
3.85 - template <typename T> class NodeMap;
3.86 - template <typename T> class EdgeMap;
3.87 -
3.88 - public:
3.89 -
3.90 - SmartGraph() : nodes(), edges() { }
3.91 - SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
3.92 -
3.93 - ~SmartGraph()
3.94 - {
3.95 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
3.96 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
3.97 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
3.98 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
3.99 - }
3.100 -
3.101 - int nodeNum() const { return nodes.size(); } //FIXME: What is this?
3.102 - int edgeNum() const { return edges.size(); } //FIXME: What is this?
3.103 -
3.104 - ///\bug This function does something different than
3.105 - ///its name would suggests...
3.106 - int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
3.107 - ///\bug This function does something different than
3.108 - ///its name would suggests...
3.109 - int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
3.110 -
3.111 - Node tail(Edge e) const { return edges[e.n].tail; }
3.112 - Node head(Edge e) const { return edges[e.n].head; }
3.113 -
3.114 - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
3.115 - Node aNode(InEdgeIt e) const { return edges[e.n].head; }
3.116 -
3.117 - Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
3.118 - Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
3.119 -
3.120 - NodeIt& first(NodeIt& v) const {
3.121 - v=NodeIt(*this); return v; }
3.122 - EdgeIt& first(EdgeIt& e) const {
3.123 - e=EdgeIt(*this); return e; }
3.124 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
3.125 - e=OutEdgeIt(*this,v); return e; }
3.126 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
3.127 - e=InEdgeIt(*this,v); return e; }
3.128 -
3.129 -// template< typename It >
3.130 -// It first() const { It e; first(e); return e; }
3.131 -
3.132 -// template< typename It >
3.133 -// It first(Node v) const { It e; first(e,v); return e; }
3.134 -
3.135 - bool valid(Edge e) const { return e.n!=-1; }
3.136 - bool valid(Node n) const { return n.n!=-1; }
3.137 -
3.138 - void setInvalid(Edge &e) { e.n=-1; }
3.139 - void setInvalid(Node &n) { n.n=-1; }
3.140 -
3.141 - template <typename It> It getNext(It it) const
3.142 - { It tmp(it); return next(tmp); }
3.143 -
3.144 - NodeIt& next(NodeIt& it) const {
3.145 - it.n=(it.n+2)%(nodes.size()+1)-1;
3.146 - return it;
3.147 - }
3.148 - OutEdgeIt& next(OutEdgeIt& it) const
3.149 - { it.n=edges[it.n].next_out; return it; }
3.150 - InEdgeIt& next(InEdgeIt& it) const
3.151 - { it.n=edges[it.n].next_in; return it; }
3.152 - EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
3.153 -
3.154 - int id(Node v) const { return v.n; }
3.155 - int id(Edge e) const { return e.n; }
3.156 -
3.157 - Node addNode() {
3.158 - Node n; n.n=nodes.size();
3.159 - nodes.push_back(NodeT()); //FIXME: Hmmm...
3.160 -
3.161 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
3.162 - i!=dyn_node_maps.end(); ++i) (**i).add(n);
3.163 -
3.164 - return n;
3.165 - }
3.166 -
3.167 - Edge addEdge(Node u, Node v) {
3.168 - Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
3.169 - edges[e.n].tail=u.n; edges[e.n].head=v.n;
3.170 - edges[e.n].next_out=nodes[u.n].first_out;
3.171 - edges[e.n].next_in=nodes[v.n].first_in;
3.172 - nodes[u.n].first_out=nodes[v.n].first_in=e.n;
3.173 -
3.174 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
3.175 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
3.176 -
3.177 - return e;
3.178 - }
3.179 -
3.180 - void clear() {nodes.clear();edges.clear();}
3.181 -
3.182 - class Node {
3.183 - friend class SmartGraph;
3.184 - template <typename T> friend class NodeMap;
3.185 -
3.186 - friend class Edge;
3.187 - friend class OutEdgeIt;
3.188 - friend class InEdgeIt;
3.189 - friend class SymEdge;
3.190 -
3.191 - protected:
3.192 - int n;
3.193 - friend int SmartGraph::id(Node v) const;
3.194 - Node(int nn) {n=nn;}
3.195 - public:
3.196 - Node() {}
3.197 - Node (Invalid i) { n=-1; }
3.198 - bool operator==(const Node i) const {return n==i.n;}
3.199 - bool operator!=(const Node i) const {return n!=i.n;}
3.200 - bool operator<(const Node i) const {return n<i.n;}
3.201 - };
3.202 -
3.203 - class NodeIt : public Node {
3.204 - friend class SmartGraph;
3.205 - public:
3.206 - NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
3.207 - NodeIt() : Node() { }
3.208 - };
3.209 -
3.210 - class Edge {
3.211 - friend class SmartGraph;
3.212 - template <typename T> friend class EdgeMap;
3.213 -
3.214 - //template <typename T> friend class SymSmartGraph::SymEdgeMap;
3.215 - //friend Edge SymSmartGraph::opposite(Edge) const;
3.216 -
3.217 - friend class Node;
3.218 - friend class NodeIt;
3.219 - protected:
3.220 - int n;
3.221 - friend int SmartGraph::id(Edge e) const;
3.222 -
3.223 - Edge(int nn) {n=nn;}
3.224 - public:
3.225 - Edge() { }
3.226 - Edge (Invalid) { n=-1; }
3.227 - bool operator==(const Edge i) const {return n==i.n;}
3.228 - bool operator!=(const Edge i) const {return n!=i.n;}
3.229 - bool operator<(const Edge i) const {return n<i.n;}
3.230 - ///\bug This is a workaround until somebody tells me how to
3.231 - ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
3.232 - int &idref() {return n;}
3.233 - const int &idref() const {return n;}
3.234 - };
3.235 -
3.236 - class EdgeIt : public Edge {
3.237 - friend class SmartGraph;
3.238 - public:
3.239 - EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
3.240 - EdgeIt (Invalid i) : Edge(i) { }
3.241 - EdgeIt() : Edge() { }
3.242 - ///\bug This is a workaround until somebody tells me how to
3.243 - ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
3.244 - int &idref() {return n;}
3.245 - };
3.246 -
3.247 - class OutEdgeIt : public Edge {
3.248 - friend class SmartGraph;
3.249 - public:
3.250 - OutEdgeIt() : Edge() { }
3.251 - OutEdgeIt (Invalid i) : Edge(i) { }
3.252 -
3.253 - OutEdgeIt(const SmartGraph& G,const Node v)
3.254 - : Edge(G.nodes[v.n].first_out) {}
3.255 - };
3.256 -
3.257 - class InEdgeIt : public Edge {
3.258 - friend class SmartGraph;
3.259 - public:
3.260 - InEdgeIt() : Edge() { }
3.261 - InEdgeIt (Invalid i) : Edge(i) { }
3.262 - InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
3.263 - };
3.264 -
3.265 - template <typename T> class NodeMap : public DynMapBase<Node>
3.266 - {
3.267 - std::vector<T> container;
3.268 -
3.269 - public:
3.270 - typedef T ValueType;
3.271 - typedef Node KeyType;
3.272 -
3.273 - NodeMap(const SmartGraph &_G) :
3.274 - DynMapBase<Node>(_G), container(_G.maxNodeId())
3.275 - {
3.276 - G->dyn_node_maps.push_back(this);
3.277 - }
3.278 - NodeMap(const SmartGraph &_G,const T &t) :
3.279 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
3.280 - {
3.281 - G->dyn_node_maps.push_back(this);
3.282 - }
3.283 -
3.284 - NodeMap(const NodeMap<T> &m) :
3.285 - DynMapBase<Node>(*m.G), container(m.container)
3.286 - {
3.287 - G->dyn_node_maps.push_back(this);
3.288 - }
3.289 -
3.290 - template<typename TT> friend class NodeMap;
3.291 -
3.292 - ///\todo It can copy between different types.
3.293 - ///
3.294 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
3.295 - DynMapBase<Node>(*m.G)
3.296 - {
3.297 - G->dyn_node_maps.push_back(this);
3.298 - typename std::vector<TT>::const_iterator i;
3.299 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
3.300 - i!=m.container.end();
3.301 - i++)
3.302 - container.push_back(*i);
3.303 - }
3.304 - ~NodeMap()
3.305 - {
3.306 - if(G) {
3.307 - std::vector<DynMapBase<Node>* >::iterator i;
3.308 - for(i=G->dyn_node_maps.begin();
3.309 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
3.310 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
3.311 - //A better way to do that: (Is this really important?)
3.312 - if(*i==this) {
3.313 - *i=G->dyn_node_maps.back();
3.314 - G->dyn_node_maps.pop_back();
3.315 - }
3.316 - }
3.317 - }
3.318 -
3.319 - void add(const Node k)
3.320 - {
3.321 - if(k.n>=int(container.size())) container.resize(k.n+1);
3.322 - }
3.323 -
3.324 - void erase(const Node) { }
3.325 -
3.326 - void set(Node n, T a) { container[n.n]=a; }
3.327 - //'T& operator[](Node n)' would be wrong here
3.328 - typename std::vector<T>::reference
3.329 - operator[](Node n) { return container[n.n]; }
3.330 - //'const T& operator[](Node n)' would be wrong here
3.331 - typename std::vector<T>::const_reference
3.332 - operator[](Node n) const { return container[n.n]; }
3.333 -
3.334 - ///\warning There is no safety check at all!
3.335 - ///Using operator = between maps attached to different graph may
3.336 - ///cause serious problem.
3.337 - ///\todo Is this really so?
3.338 - ///\todo It can copy between different types.
3.339 - const NodeMap<T>& operator=(const NodeMap<T> &m)
3.340 - {
3.341 - container = m.container;
3.342 - return *this;
3.343 - }
3.344 - template<typename TT>
3.345 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
3.346 - {
3.347 - copy(m.container.begin(), m.container.end(), container.begin());
3.348 - return *this;
3.349 - }
3.350 -
3.351 - void update() {} //Useless for Dynamic Maps
3.352 - void update(T a) {} //Useless for Dynamic Maps
3.353 - };
3.354 -
3.355 - template <typename T> class EdgeMap : public DynMapBase<Edge>
3.356 - {
3.357 - std::vector<T> container;
3.358 -
3.359 - public:
3.360 - typedef T ValueType;
3.361 - typedef Edge KeyType;
3.362 -
3.363 - EdgeMap(const SmartGraph &_G) :
3.364 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
3.365 - {
3.366 - //FIXME: What if there are empty Id's?
3.367 - //FIXME: Can I use 'this' in a constructor?
3.368 - G->dyn_edge_maps.push_back(this);
3.369 - }
3.370 - EdgeMap(const SmartGraph &_G,const T &t) :
3.371 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
3.372 - {
3.373 - G->dyn_edge_maps.push_back(this);
3.374 - }
3.375 - EdgeMap(const EdgeMap<T> &m) :
3.376 - DynMapBase<Edge>(*m.G), container(m.container)
3.377 - {
3.378 - G->dyn_node_maps.push_back(this);
3.379 - }
3.380 -
3.381 - template<typename TT> friend class EdgeMap;
3.382 -
3.383 - ///\todo It can copy between different types.
3.384 - ///
3.385 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
3.386 - DynMapBase<Edge>(*m.G)
3.387 - {
3.388 - G->dyn_node_maps.push_back(this);
3.389 - typename std::vector<TT>::const_iterator i;
3.390 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
3.391 - i!=m.container.end();
3.392 - i++)
3.393 - container.push_back(*i);
3.394 - }
3.395 - ~EdgeMap()
3.396 - {
3.397 - if(G) {
3.398 - std::vector<DynMapBase<Edge>* >::iterator i;
3.399 - for(i=G->dyn_edge_maps.begin();
3.400 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
3.401 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
3.402 - //A better way to do that: (Is this really important?)
3.403 - if(*i==this) {
3.404 - *i=G->dyn_edge_maps.back();
3.405 - G->dyn_edge_maps.pop_back();
3.406 - }
3.407 - }
3.408 - }
3.409 -
3.410 - void add(const Edge k)
3.411 - {
3.412 - if(k.n>=int(container.size())) container.resize(k.n+1);
3.413 - }
3.414 - void erase(const Edge) { }
3.415 -
3.416 - void set(Edge n, T a) { container[n.n]=a; }
3.417 - //T get(Edge n) const { return container[n.n]; }
3.418 - typename std::vector<T>::reference
3.419 - operator[](Edge n) { return container[n.n]; }
3.420 - typename std::vector<T>::const_reference
3.421 - operator[](Edge n) const { return container[n.n]; }
3.422 -
3.423 - ///\warning There is no safety check at all!
3.424 - ///Using operator = between maps attached to different graph may
3.425 - ///cause serious problem.
3.426 - ///\todo Is this really so?
3.427 - ///\todo It can copy between different types.
3.428 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
3.429 - {
3.430 - container = m.container;
3.431 - return *this;
3.432 - }
3.433 - template<typename TT>
3.434 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
3.435 - {
3.436 - copy(m.container.begin(), m.container.end(), container.begin());
3.437 - return *this;
3.438 - }
3.439 -
3.440 - void update() {} //Useless for DynMaps
3.441 - void update(T a) {} //Useless for DynMaps
3.442 - };
3.443 -
3.444 - };
3.445 -
3.446 - ///Graph for bidirectional edges.
3.447 -
3.448 - ///The purpose of this graph structure is to handle graphs
3.449 - ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
3.450 - ///of oppositely directed edges.
3.451 - ///There is a new edge map type called
3.452 - ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
3.453 - ///that complements this
3.454 - ///feature by
3.455 - ///storing shared values for the edge pairs. The usual
3.456 - ///\ref GraphSkeleton::EdgeMap "EdgeMap"
3.457 - ///can be used
3.458 - ///as well.
3.459 - ///
3.460 - ///The oppositely directed edge can also be obtained easily
3.461 - ///using \ref opposite.
3.462 - ///\warning It shares the similarity with \ref SmartGraph that
3.463 - ///it is not possible to delete edges or nodes from the graph.
3.464 - //\sa \ref SmartGraph.
3.465 -
3.466 - class SymSmartGraph : public SmartGraph
3.467 - {
3.468 - public:
3.469 - template<typename T> class SymEdgeMap;
3.470 - template<typename T> friend class SymEdgeMap;
3.471 -
3.472 - SymSmartGraph() : SmartGraph() { }
3.473 - SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
3.474 - ///Adds a pair of oppositely directed edges to the graph.
3.475 - Edge addEdge(Node u, Node v)
3.476 - {
3.477 - Edge e = SmartGraph::addEdge(u,v);
3.478 - SmartGraph::addEdge(v,u);
3.479 - return e;
3.480 - }
3.481 -
3.482 - ///The oppositely directed edge.
3.483 -
3.484 - ///Returns the oppositely directed
3.485 - ///pair of the edge \c e.
3.486 - Edge opposite(Edge e) const
3.487 - {
3.488 - Edge f;
3.489 - f.idref() = e.idref() - 2*(e.idref()%2) + 1;
3.490 - return f;
3.491 - }
3.492 -
3.493 - ///Common data storage for the edge pairs.
3.494 -
3.495 - ///This map makes it possible to store data shared by the oppositely
3.496 - ///directed pairs of edges.
3.497 - template <typename T> class SymEdgeMap : public DynMapBase<Edge>
3.498 - {
3.499 - std::vector<T> container;
3.500 -
3.501 - public:
3.502 - typedef T ValueType;
3.503 - typedef Edge KeyType;
3.504 -
3.505 - SymEdgeMap(const SymSmartGraph &_G) :
3.506 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
3.507 - {
3.508 - static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
3.509 - }
3.510 - SymEdgeMap(const SymSmartGraph &_G,const T &t) :
3.511 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
3.512 - {
3.513 - G->dyn_edge_maps.push_back(this);
3.514 - }
3.515 -
3.516 - SymEdgeMap(const SymEdgeMap<T> &m) :
3.517 - DynMapBase<SymEdge>(*m.G), container(m.container)
3.518 - {
3.519 - G->dyn_node_maps.push_back(this);
3.520 - }
3.521 -
3.522 - // template<typename TT> friend class SymEdgeMap;
3.523 -
3.524 - ///\todo It can copy between different types.
3.525 - ///
3.526 -
3.527 - template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
3.528 - DynMapBase<SymEdge>(*m.G)
3.529 - {
3.530 - G->dyn_node_maps.push_back(this);
3.531 - typename std::vector<TT>::const_iterator i;
3.532 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
3.533 - i!=m.container.end();
3.534 - i++)
3.535 - container.push_back(*i);
3.536 - }
3.537 -
3.538 - ~SymEdgeMap()
3.539 - {
3.540 - if(G) {
3.541 - std::vector<DynMapBase<Edge>* >::iterator i;
3.542 - for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
3.543 - i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
3.544 - && *i!=this; ++i) ;
3.545 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
3.546 - //A better way to do that: (Is this really important?)
3.547 - if(*i==this) {
3.548 - *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
3.549 - static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
3.550 - }
3.551 - }
3.552 - }
3.553 -
3.554 - void add(const Edge k)
3.555 - {
3.556 - if(!k.idref()%2&&k.idref()/2>=int(container.size()))
3.557 - container.resize(k.idref()/2+1);
3.558 - }
3.559 - void erase(const Edge k) { }
3.560 -
3.561 - void set(Edge n, T a) { container[n.idref()/2]=a; }
3.562 - //T get(Edge n) const { return container[n.idref()/2]; }
3.563 - typename std::vector<T>::reference
3.564 - operator[](Edge n) { return container[n.idref()/2]; }
3.565 - typename std::vector<T>::const_reference
3.566 - operator[](Edge n) const { return container[n.idref()/2]; }
3.567 -
3.568 - ///\warning There is no safety check at all!
3.569 - ///Using operator = between maps attached to different graph may
3.570 - ///cause serious problem.
3.571 - ///\todo Is this really so?
3.572 - ///\todo It can copy between different types.
3.573 - const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
3.574 - {
3.575 - container = m.container;
3.576 - return *this;
3.577 - }
3.578 - template<typename TT>
3.579 - const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
3.580 - {
3.581 - copy(m.container.begin(), m.container.end(), container.begin());
3.582 - return *this;
3.583 - }
3.584 -
3.585 - void update() {} //Useless for DynMaps
3.586 - void update(T a) {} //Useless for DynMaps
3.587 -
3.588 - };
3.589 -
3.590 - };
3.591 -
3.592 -
3.593 -} //namespace hugo
3.594 -
3.595 -
3.596 -
3.597 -
3.598 -#endif //SMART_GRAPH_H