1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/alpar/smart_graph.h Fri Feb 20 00:29:19 2004 +0000
1.3 @@ -0,0 +1,234 @@
1.4 +#ifndef SMART_GRAPH_H
1.5 +#define SMART_GRAPH_H
1.6 +
1.7 +#include <iostream>
1.8 +#include <vector>
1.9 +
1.10 +namespace marci {
1.11 +
1.12 + class SmartGraph {
1.13 +
1.14 + static const int INVALID=-1;
1.15 +
1.16 + struct NodeT
1.17 + {
1.18 + int first_in,first_out;
1.19 + NodeT() : first_in(INVALID), first_out(INVALID) {}
1.20 + };
1.21 + struct EdgeT
1.22 + {
1.23 + int head, tail, next_in, next_out;
1.24 + //FIXME: is this necessary?
1.25 + EdgeT() : next_in(INVALID), next_out(INVALID) {}
1.26 + };
1.27 +
1.28 + std::vector<NodeT> nodes;
1.29 + std::vector<EdgeT> edges;
1.30 +
1.31 +
1.32 + public:
1.33 +
1.34 + class NodeIt;
1.35 + class EachNodeIt;
1.36 + class EdgeIt;
1.37 + class EachEdgeIt;
1.38 + class OutEdgeIt;
1.39 + class InEdgeIt;
1.40 +
1.41 +// class NodeIt { int n; };
1.42 +// class EachNodeIt : public NodeIt { };
1.43 +// class EdgeIt { int n; };
1.44 +// class EachEdgeIt : public EdgeIt {};
1.45 +// class OutEdgeIt : public EdgeIt {};
1.46 +// class InEdgeIt : public EdgeIt {};
1.47 + // class SymEdgeIt;
1.48 +
1.49 + template <typename T> class NodeMap;
1.50 + template <typename T> class EdgeMap;
1.51 +
1.52 + private:
1.53 +
1.54 + template <typename T> friend class NodeMap;
1.55 + template <typename T> friend class EdgeMap;
1.56 +
1.57 + template <typename T>
1.58 + class NodeMap {
1.59 + const SmartGraph& G;
1.60 + std::vector<T> container;
1.61 + public:
1.62 + typedef T ValueType;
1.63 + typedef NodeIt KeyType;
1.64 + NodeMap(const SmartGraph& _G) : G(_G), container(G.nodeNum()) { }
1.65 + NodeMap(const SmartGraph& _G, T a) :
1.66 + G(_G), container(G.nodeNum(), a) { }
1.67 + void set(NodeIt n, T a) { container[n.n]=a; }
1.68 + T get(NodeIt n) const { return container[n.n]; }
1.69 + T& operator[](NodeIt n) { return container[n.n]; }
1.70 + const T& operator[](NodeIt n) const { return container[n.n]; }
1.71 + void resize() { container.resize(G.nodeNum()); }
1.72 + void resize(T a) { container.resize(G.nodeNum(), a); }
1.73 + };
1.74 +
1.75 + template <typename T>
1.76 + class EdgeMap {
1.77 + const SmartGraph& G;
1.78 + std::vector<T> container;
1.79 + public:
1.80 + typedef T ValueType;
1.81 + typedef EdgeIt KeyType;
1.82 + EdgeMap(const SmartGraph& _G) : G(_G), container(G.edgeNum()) { }
1.83 + EdgeMap(const SmartGraph& _G, T a) :
1.84 + G(_G), container(G.edgeNum(), a) { }
1.85 + void set(EdgeIt e, T a) { container[e.n]=a; }
1.86 + T get(EdgeIt e) const { return container[e.n]; }
1.87 + T& operator[](EdgeIt e) { return container[e.n]; }
1.88 + const T& operator[](EdgeIt e) const { return container[e.n]; }
1.89 + void resize() { container.resize(G.edgeNum()); }
1.90 + void resize(T a) { container.resize(G.edgeNum(), a); }
1.91 + };
1.92 +
1.93 + public:
1.94 +
1.95 + /* default constructor */
1.96 +
1.97 + SmartGraph() : nodes(), edges() { }
1.98 +
1.99 + ~SmartGraph() {}
1.100 +
1.101 + int nodeNum() const { return nodes.size(); } //FIXME: What is this?
1.102 + int edgeNum() const { return edges.size(); } //FIXME: What is this?
1.103 +
1.104 + NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
1.105 + NodeIt head(EdgeIt e) const { return edges[e.n].head; }
1.106 +
1.107 + NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
1.108 + NodeIt aNode(const InEdgeIt& e) const { return head(e); }
1.109 + //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
1.110 +
1.111 + NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
1.112 + NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
1.113 + //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
1.114 +
1.115 + EachNodeIt& getFirst(EachNodeIt& v) const {
1.116 + v=EachNodeIt(*this); return v; }
1.117 + EachEdgeIt& getFirst(EachEdgeIt& e) const {
1.118 + e=EachEdgeIt(*this); return e; }
1.119 + OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const {
1.120 + e=OutEdgeIt(*this,v); return e; }
1.121 + InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const {
1.122 + e=InEdgeIt(*this,v); return e; }
1.123 +
1.124 + template< typename It >
1.125 + It first() const {
1.126 + It e;
1.127 + getFirst(e);
1.128 + return e;
1.129 + }
1.130 +
1.131 + template< typename It >
1.132 + It first(NodeIt v) const {
1.133 + It e;
1.134 + getFirst(e, v);
1.135 + return e;
1.136 + }
1.137 +
1.138 + bool valid(EdgeIt e) const { return e.n!=INVALID; }
1.139 + bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
1.140 + bool valid(NodeIt n) const { return n.n<int(nodes.size()); }
1.141 +
1.142 + template <typename It> It next(It it) const {
1.143 + It tmp(it); return goNext(it); }
1.144 +
1.145 + NodeIt& goNext(NodeIt& it) const { ++it.n; return it; }
1.146 + OutEdgeIt& goNext(OutEdgeIt& it) const
1.147 + { it.n=edges[it.n].next_out; return it; }
1.148 + InEdgeIt& goNext(InEdgeIt& it) const
1.149 + { it.n=edges[it.n].next_in; return it; }
1.150 + EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; }
1.151 +
1.152 + int id(NodeIt v) const { return v.n; }
1.153 + int id(EdgeIt e) const { return e.n; }
1.154 +
1.155 + NodeIt addNode() {
1.156 + NodeIt n; n.n=nodes.size();
1.157 + nodes.push_back(NodeT()); //FIXME: Hmmm...
1.158 + return n;
1.159 + }
1.160 + EdgeIt addEdge(NodeIt u, NodeIt v) {
1.161 + EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
1.162 + edges[e.n].tail=u.n; edges[e.n].head=v.n;
1.163 + edges[e.n].next_out=nodes[u.n].first_out;
1.164 + edges[e.n].next_in=nodes[v.n].first_in;
1.165 + nodes[u.n].first_out=nodes[v.n].first_in=e.n;
1.166 + return e;
1.167 + }
1.168 +
1.169 + void clear() {nodes.clear();edges.clear();}
1.170 +
1.171 + class NodeIt {
1.172 + friend class SmartGraph;
1.173 + template <typename T> friend class NodeMap;
1.174 +
1.175 + friend class EdgeIt;
1.176 + friend class OutEdgeIt;
1.177 + friend class InEdgeIt;
1.178 + friend class SymEdgeIt;
1.179 +
1.180 + protected:
1.181 + int n;
1.182 + friend int SmartGraph::id(NodeIt v) const;
1.183 + public:
1.184 + NodeIt() {}
1.185 + NodeIt(int nn) {n=nn;}
1.186 + bool operator==(const NodeIt i) const {return n==i.n;}
1.187 + bool operator!=(const NodeIt i) const {return n!=i.n;}
1.188 + };
1.189 +
1.190 + class EachNodeIt : public NodeIt {
1.191 + friend class SmartGraph;
1.192 + public:
1.193 + EachNodeIt(const SmartGraph& G) : NodeIt(0) { }
1.194 + EachNodeIt() : NodeIt() { }
1.195 + };
1.196 +
1.197 + class EdgeIt {
1.198 + friend class SmartGraph;
1.199 + template <typename T> friend class EdgeMap;
1.200 +
1.201 + friend class NodeIt;
1.202 + friend class EachNodeIt;
1.203 + protected:
1.204 + int n;
1.205 + friend int SmartGraph::id(EdgeIt e) const;
1.206 + public:
1.207 + EdgeIt() { }
1.208 + EdgeIt(int nn) {n=nn;}
1.209 + bool operator==(const EdgeIt i) const {return n==i.n;}
1.210 + bool operator!=(const EdgeIt i) const {return n!=i.n;}
1.211 + };
1.212 +
1.213 + class EachEdgeIt : public EdgeIt {
1.214 + friend class SmartGraph;
1.215 + public:
1.216 + EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { }
1.217 + EachEdgeIt() : EdgeIt() { }
1.218 + };
1.219 +
1.220 + class OutEdgeIt : public EdgeIt {
1.221 + friend class SmartGraph;
1.222 + public:
1.223 + OutEdgeIt() : EdgeIt() { }
1.224 + OutEdgeIt(const SmartGraph& G,const NodeIt v)
1.225 + : EdgeIt(G.nodes[v.n].first_out) {}
1.226 + };
1.227 +
1.228 + class InEdgeIt : public EdgeIt {
1.229 + friend class SmartGraph;
1.230 + public:
1.231 + InEdgeIt() : EdgeIt() { }
1.232 + InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
1.233 + };
1.234 + };
1.235 +} //namespace marci
1.236 +
1.237 +#endif //SMART_GRAPH_H