1.1 --- a/src/work/alpar/smart_graph.h Thu Mar 04 19:45:06 2004 +0000
1.2 +++ b/src/work/alpar/smart_graph.h Sun Mar 07 19:33:34 2004 +0000
1.3 @@ -3,27 +3,28 @@
1.4 #ifndef SMART_GRAPH_H
1.5 #define SMART_GRAPH_H
1.6
1.7 -#include <iostream>
1.8 #include <vector>
1.9 #include <limits.h>
1.10
1.11 +struct _Invalid {} Invalid;
1.12 +
1.13 namespace hugo {
1.14
1.15 class SmartGraph {
1.16
1.17 - static const int INVALID_EDGE=-1;
1.18 - static const int INVALID_NODE=INT_MAX;
1.19 +// static const int INVALID=-1;
1.20 +// static const int INVALID_NODE=INT_MAX;
1.21
1.22 struct NodeT
1.23 {
1.24 int first_in,first_out;
1.25 - NodeT() : first_in(INVALID_EDGE), first_out(INVALID_EDGE) {}
1.26 + NodeT() : first_in(-1), first_out(-1) {}
1.27 };
1.28 struct EdgeT
1.29 {
1.30 int head, tail, next_in, next_out;
1.31 //FIXME: is this necessary?
1.32 - EdgeT() : next_in(INVALID_EDGE), next_out(INVALID_EDGE) {}
1.33 + EdgeT() : next_in(-1), next_out(-1) {}
1.34 };
1.35
1.36 std::vector<NodeT> nodes;
1.37 @@ -37,11 +38,10 @@
1.38 public:
1.39 virtual void add(const Key k) = NULL;
1.40 virtual void erase(const Key k) = NULL;
1.41 - DynMapBase(SmartGraph &_G) : G(&_G) {}
1.42 + DynMapBase(const SmartGraph &_G) : G(&_G) {}
1.43 virtual ~DynMapBase() {}
1.44 friend class SmartGraph;
1.45 };
1.46 -
1.47 public:
1.48 template <typename T> class DynEdgeMap;
1.49 template <typename T> class DynEdgeMap;
1.50 @@ -50,8 +50,8 @@
1.51 class EdgeIt;
1.52
1.53 protected:
1.54 - std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
1.55 - std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
1.56 + mutable std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
1.57 + mutable std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
1.58
1.59 public:
1.60
1.61 @@ -60,13 +60,13 @@
1.62 class OutEdgeIt;
1.63 class InEdgeIt;
1.64
1.65 - // class NodeIt { int n; };
1.66 + // class NodeIt { int n; };
1.67 // class EachNodeIt : public NodeIt { };
1.68 // class EdgeIt { int n; };
1.69 // class EachEdgeIt : public EdgeIt {};
1.70 // class OutEdgeIt : public EdgeIt {};
1.71 // class InEdgeIt : public EdgeIt {};
1.72 - // class SymEdgeIt;
1.73 + // class SymEdgeIt;
1.74
1.75 template <typename T> class NodeMap;
1.76 template <typename T> class EdgeMap;
1.77 @@ -96,13 +96,13 @@
1.78 NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
1.79 NodeIt head(EdgeIt e) const { return edges[e.n].head; }
1.80
1.81 - NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
1.82 - NodeIt aNode(const InEdgeIt& e) const { return head(e); }
1.83 - //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
1.84 +// NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
1.85 +// NodeIt aNode(const InEdgeIt& e) const { return head(e); }
1.86 +// //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
1.87
1.88 - NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
1.89 - NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
1.90 - //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
1.91 +// NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
1.92 +// NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
1.93 +// //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
1.94
1.95 EachNodeIt& getFirst(EachNodeIt& v) const {
1.96 v=EachNodeIt(*this); return v; }
1.97 @@ -127,23 +127,23 @@
1.98 return e;
1.99 }
1.100
1.101 - bool valid(EdgeIt e) const { return e.n!=INVALID_EDGE; }
1.102 - bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
1.103 - bool valid(NodeIt n) const { return n.n<int(nodes.size()); }
1.104 + bool valid(EdgeIt e) const { return e.n!=-1; }
1.105 + // bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
1.106 + bool valid(NodeIt n) const { return n.n!=-1; }
1.107
1.108 - void setInvalid(EdgeIt &e) { e.n=INVALID_EDGE; }
1.109 - void setInvalid(NodeIt &n) { n.n=INVALID_NODE; }
1.110 + void setInvalid(EdgeIt &e) { e.n=-1; }
1.111 + void setInvalid(NodeIt &n) { n.n=-1; }
1.112
1.113 - template <typename It> It next(It it) const
1.114 - // { It tmp(it); return goNext(tmp); }
1.115 - { It tmp; tmp.n=it.n+1; return tmp; }
1.116 + template <typename It> It getNext(It it) const
1.117 + { It tmp(it); return next(tmp); }
1.118 + //{ It tmp; tmp.n=it.n+1; return tmp; }
1.119
1.120 - NodeIt& goNext(NodeIt& it) const { ++it.n; return it; }
1.121 - OutEdgeIt& goNext(OutEdgeIt& it) const
1.122 + NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
1.123 + OutEdgeIt& next(OutEdgeIt& it) const
1.124 { it.n=edges[it.n].next_out; return it; }
1.125 - InEdgeIt& goNext(InEdgeIt& it) const
1.126 + InEdgeIt& next(InEdgeIt& it) const
1.127 { it.n=edges[it.n].next_in; return it; }
1.128 - EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; }
1.129 + EachEdgeIt& next(EachEdgeIt& it) const { --it.n; return it; }
1.130
1.131 int id(NodeIt v) const { return v.n; }
1.132 int id(EdgeIt e) const { return e.n; }
1.133 @@ -166,7 +166,7 @@
1.134 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
1.135
1.136 for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
1.137 - i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);
1.138 + i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1.139
1.140 return e;
1.141 }
1.142 @@ -186,17 +186,19 @@
1.143 protected:
1.144 int n;
1.145 friend int SmartGraph::id(NodeIt v) const;
1.146 + NodeIt(int nn) {n=nn;}
1.147 public:
1.148 NodeIt() {}
1.149 - NodeIt(int nn) {n=nn;}
1.150 + NodeIt (_Invalid i) { n=-1; }
1.151 bool operator==(const NodeIt i) const {return n==i.n;}
1.152 bool operator!=(const NodeIt i) const {return n!=i.n;}
1.153 + bool operator<(const NodeIt i) const {return n<i.n;}
1.154 };
1.155
1.156 class EachNodeIt : public NodeIt {
1.157 friend class SmartGraph;
1.158 public:
1.159 - EachNodeIt(const SmartGraph& G) : NodeIt(0) { }
1.160 + EachNodeIt(const SmartGraph& G) : NodeIt(G.nodes.size()?0:-1) { }
1.161 EachNodeIt() : NodeIt() { }
1.162 };
1.163
1.164 @@ -210,17 +212,21 @@
1.165 protected:
1.166 int n;
1.167 friend int SmartGraph::id(EdgeIt e) const;
1.168 +
1.169 + EdgeIt(int nn) {n=nn;}
1.170 public:
1.171 EdgeIt() { }
1.172 - EdgeIt(int nn) {n=nn;}
1.173 + EdgeIt (_Invalid i) { n=-1; }
1.174 bool operator==(const EdgeIt i) const {return n==i.n;}
1.175 bool operator!=(const EdgeIt i) const {return n!=i.n;}
1.176 + bool operator<(const EdgeIt i) const {return n<i.n;}
1.177 };
1.178
1.179 class EachEdgeIt : public EdgeIt {
1.180 friend class SmartGraph;
1.181 public:
1.182 - EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { }
1.183 + EachEdgeIt(const SmartGraph& G) : EdgeIt(G.edges.size()-1) { }
1.184 + EachEdgeIt (_Invalid i) : EdgeIt(i) { }
1.185 EachEdgeIt() : EdgeIt() { }
1.186 };
1.187
1.188 @@ -228,6 +234,8 @@
1.189 friend class SmartGraph;
1.190 public:
1.191 OutEdgeIt() : EdgeIt() { }
1.192 + OutEdgeIt (_Invalid i) : EdgeIt(i) { }
1.193 +
1.194 OutEdgeIt(const SmartGraph& G,const NodeIt v)
1.195 : EdgeIt(G.nodes[v.n].first_out) {}
1.196 };
1.197 @@ -236,6 +244,7 @@
1.198 friend class SmartGraph;
1.199 public:
1.200 InEdgeIt() : EdgeIt() { }
1.201 + InEdgeIt (_Invalid i) : EdgeIt(i) { }
1.202 InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
1.203 };
1.204
1.205 @@ -285,7 +294,7 @@
1.206 typedef T ValueType;
1.207 typedef NodeIt KeyType;
1.208
1.209 - DynNodeMap(SmartGraph &_G) :
1.210 + DynNodeMap(const SmartGraph &_G) :
1.211 DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
1.212 {
1.213 //FIXME: What if there are empty Id's?
1.214 @@ -311,10 +320,14 @@
1.215 {
1.216 if(k.n>=container.size()) container.resize(k.n+1);
1.217 }
1.218 - void erase(const NodeIt k)
1.219 - {
1.220 - //FIXME: Please implement me.
1.221 - }
1.222 +// void erase(const NodeIt k)
1.223 +// {
1.224 +// //FIXME: Please implement me.
1.225 +// }
1.226 +// void erase(const EdgeIt k)
1.227 +// {
1.228 +// //FIXME: Please implement me.
1.229 +// }
1.230
1.231 void set(NodeIt n, T a) { container[n.n]=a; }
1.232 T get(NodeIt n) const { return container[n.n]; }
1.233 @@ -333,7 +346,7 @@
1.234 typedef T ValueType;
1.235 typedef EdgeIt KeyType;
1.236
1.237 - DynEdgeMap(SmartGraph &_G) :
1.238 + DynEdgeMap(const SmartGraph &_G) :
1.239 DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
1.240 {
1.241 //FIXME: What if there are empty Id's?
1.242 @@ -376,4 +389,7 @@
1.243 };
1.244 } //namespace hugo
1.245
1.246 +
1.247 +
1.248 +
1.249 #endif //SMART_GRAPH_H