1.1 --- a/src/work/alpar/emptygraph.h Thu Mar 04 19:45:06 2004 +0000
1.2 +++ b/src/work/alpar/emptygraph.h Sun Mar 07 19:33:34 2004 +0000
1.3 @@ -38,7 +38,7 @@
1.4 // class SymEdgeIt : public EdgeIt {};
1.5 class EachEdgeIt : public EdgeIt {
1.6 EachEdgeIt() {}
1.7 - EachEdgeIt(const EmptyGraph &, NodeIt) {}
1.8 + EachEdgeIt(const EmptyGraph &) {}
1.9 };
1.10
1.11 EachNodeIt &getFirst(EachNodeIt &) const {}
2.1 --- a/src/work/alpar/smart_graph.h Thu Mar 04 19:45:06 2004 +0000
2.2 +++ b/src/work/alpar/smart_graph.h Sun Mar 07 19:33:34 2004 +0000
2.3 @@ -3,27 +3,28 @@
2.4 #ifndef SMART_GRAPH_H
2.5 #define SMART_GRAPH_H
2.6
2.7 -#include <iostream>
2.8 #include <vector>
2.9 #include <limits.h>
2.10
2.11 +struct _Invalid {} Invalid;
2.12 +
2.13 namespace hugo {
2.14
2.15 class SmartGraph {
2.16
2.17 - static const int INVALID_EDGE=-1;
2.18 - static const int INVALID_NODE=INT_MAX;
2.19 +// static const int INVALID=-1;
2.20 +// static const int INVALID_NODE=INT_MAX;
2.21
2.22 struct NodeT
2.23 {
2.24 int first_in,first_out;
2.25 - NodeT() : first_in(INVALID_EDGE), first_out(INVALID_EDGE) {}
2.26 + NodeT() : first_in(-1), first_out(-1) {}
2.27 };
2.28 struct EdgeT
2.29 {
2.30 int head, tail, next_in, next_out;
2.31 //FIXME: is this necessary?
2.32 - EdgeT() : next_in(INVALID_EDGE), next_out(INVALID_EDGE) {}
2.33 + EdgeT() : next_in(-1), next_out(-1) {}
2.34 };
2.35
2.36 std::vector<NodeT> nodes;
2.37 @@ -37,11 +38,10 @@
2.38 public:
2.39 virtual void add(const Key k) = NULL;
2.40 virtual void erase(const Key k) = NULL;
2.41 - DynMapBase(SmartGraph &_G) : G(&_G) {}
2.42 + DynMapBase(const SmartGraph &_G) : G(&_G) {}
2.43 virtual ~DynMapBase() {}
2.44 friend class SmartGraph;
2.45 };
2.46 -
2.47 public:
2.48 template <typename T> class DynEdgeMap;
2.49 template <typename T> class DynEdgeMap;
2.50 @@ -50,8 +50,8 @@
2.51 class EdgeIt;
2.52
2.53 protected:
2.54 - std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
2.55 - std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
2.56 + mutable std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
2.57 + mutable std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
2.58
2.59 public:
2.60
2.61 @@ -60,13 +60,13 @@
2.62 class OutEdgeIt;
2.63 class InEdgeIt;
2.64
2.65 - // class NodeIt { int n; };
2.66 + // class NodeIt { int n; };
2.67 // class EachNodeIt : public NodeIt { };
2.68 // class EdgeIt { int n; };
2.69 // class EachEdgeIt : public EdgeIt {};
2.70 // class OutEdgeIt : public EdgeIt {};
2.71 // class InEdgeIt : public EdgeIt {};
2.72 - // class SymEdgeIt;
2.73 + // class SymEdgeIt;
2.74
2.75 template <typename T> class NodeMap;
2.76 template <typename T> class EdgeMap;
2.77 @@ -96,13 +96,13 @@
2.78 NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
2.79 NodeIt head(EdgeIt e) const { return edges[e.n].head; }
2.80
2.81 - NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
2.82 - NodeIt aNode(const InEdgeIt& e) const { return head(e); }
2.83 - //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
2.84 +// NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
2.85 +// NodeIt aNode(const InEdgeIt& e) const { return head(e); }
2.86 +// //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
2.87
2.88 - NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
2.89 - NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
2.90 - //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
2.91 +// NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
2.92 +// NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
2.93 +// //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
2.94
2.95 EachNodeIt& getFirst(EachNodeIt& v) const {
2.96 v=EachNodeIt(*this); return v; }
2.97 @@ -127,23 +127,23 @@
2.98 return e;
2.99 }
2.100
2.101 - bool valid(EdgeIt e) const { return e.n!=INVALID_EDGE; }
2.102 - bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
2.103 - bool valid(NodeIt n) const { return n.n<int(nodes.size()); }
2.104 + bool valid(EdgeIt e) const { return e.n!=-1; }
2.105 + // bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
2.106 + bool valid(NodeIt n) const { return n.n!=-1; }
2.107
2.108 - void setInvalid(EdgeIt &e) { e.n=INVALID_EDGE; }
2.109 - void setInvalid(NodeIt &n) { n.n=INVALID_NODE; }
2.110 + void setInvalid(EdgeIt &e) { e.n=-1; }
2.111 + void setInvalid(NodeIt &n) { n.n=-1; }
2.112
2.113 - template <typename It> It next(It it) const
2.114 - // { It tmp(it); return goNext(tmp); }
2.115 - { It tmp; tmp.n=it.n+1; return tmp; }
2.116 + template <typename It> It getNext(It it) const
2.117 + { It tmp(it); return next(tmp); }
2.118 + //{ It tmp; tmp.n=it.n+1; return tmp; }
2.119
2.120 - NodeIt& goNext(NodeIt& it) const { ++it.n; return it; }
2.121 - OutEdgeIt& goNext(OutEdgeIt& it) const
2.122 + NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
2.123 + OutEdgeIt& next(OutEdgeIt& it) const
2.124 { it.n=edges[it.n].next_out; return it; }
2.125 - InEdgeIt& goNext(InEdgeIt& it) const
2.126 + InEdgeIt& next(InEdgeIt& it) const
2.127 { it.n=edges[it.n].next_in; return it; }
2.128 - EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; }
2.129 + EachEdgeIt& next(EachEdgeIt& it) const { --it.n; return it; }
2.130
2.131 int id(NodeIt v) const { return v.n; }
2.132 int id(EdgeIt e) const { return e.n; }
2.133 @@ -166,7 +166,7 @@
2.134 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
2.135
2.136 for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
2.137 - i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);
2.138 + i!=dyn_edge_maps.end(); ++i) (**i).add(e);
2.139
2.140 return e;
2.141 }
2.142 @@ -186,17 +186,19 @@
2.143 protected:
2.144 int n;
2.145 friend int SmartGraph::id(NodeIt v) const;
2.146 + NodeIt(int nn) {n=nn;}
2.147 public:
2.148 NodeIt() {}
2.149 - NodeIt(int nn) {n=nn;}
2.150 + NodeIt (_Invalid i) { n=-1; }
2.151 bool operator==(const NodeIt i) const {return n==i.n;}
2.152 bool operator!=(const NodeIt i) const {return n!=i.n;}
2.153 + bool operator<(const NodeIt i) const {return n<i.n;}
2.154 };
2.155
2.156 class EachNodeIt : public NodeIt {
2.157 friend class SmartGraph;
2.158 public:
2.159 - EachNodeIt(const SmartGraph& G) : NodeIt(0) { }
2.160 + EachNodeIt(const SmartGraph& G) : NodeIt(G.nodes.size()?0:-1) { }
2.161 EachNodeIt() : NodeIt() { }
2.162 };
2.163
2.164 @@ -210,17 +212,21 @@
2.165 protected:
2.166 int n;
2.167 friend int SmartGraph::id(EdgeIt e) const;
2.168 +
2.169 + EdgeIt(int nn) {n=nn;}
2.170 public:
2.171 EdgeIt() { }
2.172 - EdgeIt(int nn) {n=nn;}
2.173 + EdgeIt (_Invalid i) { n=-1; }
2.174 bool operator==(const EdgeIt i) const {return n==i.n;}
2.175 bool operator!=(const EdgeIt i) const {return n!=i.n;}
2.176 + bool operator<(const EdgeIt i) const {return n<i.n;}
2.177 };
2.178
2.179 class EachEdgeIt : public EdgeIt {
2.180 friend class SmartGraph;
2.181 public:
2.182 - EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { }
2.183 + EachEdgeIt(const SmartGraph& G) : EdgeIt(G.edges.size()-1) { }
2.184 + EachEdgeIt (_Invalid i) : EdgeIt(i) { }
2.185 EachEdgeIt() : EdgeIt() { }
2.186 };
2.187
2.188 @@ -228,6 +234,8 @@
2.189 friend class SmartGraph;
2.190 public:
2.191 OutEdgeIt() : EdgeIt() { }
2.192 + OutEdgeIt (_Invalid i) : EdgeIt(i) { }
2.193 +
2.194 OutEdgeIt(const SmartGraph& G,const NodeIt v)
2.195 : EdgeIt(G.nodes[v.n].first_out) {}
2.196 };
2.197 @@ -236,6 +244,7 @@
2.198 friend class SmartGraph;
2.199 public:
2.200 InEdgeIt() : EdgeIt() { }
2.201 + InEdgeIt (_Invalid i) : EdgeIt(i) { }
2.202 InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
2.203 };
2.204
2.205 @@ -285,7 +294,7 @@
2.206 typedef T ValueType;
2.207 typedef NodeIt KeyType;
2.208
2.209 - DynNodeMap(SmartGraph &_G) :
2.210 + DynNodeMap(const SmartGraph &_G) :
2.211 DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
2.212 {
2.213 //FIXME: What if there are empty Id's?
2.214 @@ -311,10 +320,14 @@
2.215 {
2.216 if(k.n>=container.size()) container.resize(k.n+1);
2.217 }
2.218 - void erase(const NodeIt k)
2.219 - {
2.220 - //FIXME: Please implement me.
2.221 - }
2.222 +// void erase(const NodeIt k)
2.223 +// {
2.224 +// //FIXME: Please implement me.
2.225 +// }
2.226 +// void erase(const EdgeIt k)
2.227 +// {
2.228 +// //FIXME: Please implement me.
2.229 +// }
2.230
2.231 void set(NodeIt n, T a) { container[n.n]=a; }
2.232 T get(NodeIt n) const { return container[n.n]; }
2.233 @@ -333,7 +346,7 @@
2.234 typedef T ValueType;
2.235 typedef EdgeIt KeyType;
2.236
2.237 - DynEdgeMap(SmartGraph &_G) :
2.238 + DynEdgeMap(const SmartGraph &_G) :
2.239 DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
2.240 {
2.241 //FIXME: What if there are empty Id's?
2.242 @@ -376,4 +389,7 @@
2.243 };
2.244 } //namespace hugo
2.245
2.246 +
2.247 +
2.248 +
2.249 #endif //SMART_GRAPH_H
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/alpar/smart_graph_demo.cc Sun Mar 07 19:33:34 2004 +0000
3.3 @@ -0,0 +1,36 @@
3.4 +#include<smart_graph.h>
3.5 +
3.6 +#include <iostream>
3.7 +
3.8 +using namespace hugo;
3.9 +
3.10 +SmartGraph::OutEdgeIt safeFirstOut(const SmartGraph &G, SmartGraph::NodeIt n)
3.11 +{
3.12 + return G.valid(n) ? SmartGraph::OutEdgeIt(G,n):Invalid;
3.13 +}
3.14 +
3.15 +int main()
3.16 +{
3.17 +
3.18 + typedef SmartGraph::EdgeIt EdgeIt;
3.19 + typedef SmartGraph::InEdgeIt InEdgeIt;
3.20 + typedef SmartGraph::OutEdgeIt OutEdgeIt;
3.21 + typedef SmartGraph::EachEdgeIt EachEdgeIt;
3.22 + typedef SmartGraph::NodeIt NodeIt;
3.23 + typedef SmartGraph::EachNodeIt EachNodeIt;
3.24 +
3.25 + SmartGraph G;
3.26 + EachNodeIt n;
3.27 +
3.28 +
3.29 + // std::cout.form("%s: %d\n","Sztring",15);
3.30 +
3.31 + for(int i=0;i<10;i++) G.addNode();
3.32 + for(G.getFirst(n);G.valid(n);G.next(n))
3.33 + for(EachNodeIt m(G);m!=Invalid;G.next(m))
3.34 + if(n!=m) G.addEdge(n,m);
3.35 +
3.36 + OutEdgeIt e = safeFirstOut(G,n);
3.37 + OutEdgeIt f = safeFirstOut(G,EachNodeIt(G));
3.38 +
3.39 +}