61 int maxEdgeId() const { return EdgeNum; } //FIXME: What is this? |
61 int maxEdgeId() const { return EdgeNum; } //FIXME: What is this? |
62 |
62 |
63 Node tail(Edge e) const { return e.n%NodeNum; } |
63 Node tail(Edge e) const { return e.n%NodeNum; } |
64 Node head(Edge e) const { return e.n/NodeNum; } |
64 Node head(Edge e) const { return e.n/NodeNum; } |
65 |
65 |
66 Node aNode(OutEdgeIt e) const { return tail(e); } |
|
67 Node aNode(InEdgeIt e) const { return head(e); } |
|
68 |
|
69 Node bNode(OutEdgeIt e) const { return head(e); } |
|
70 Node bNode(InEdgeIt e) const { return tail(e); } |
|
71 |
|
72 NodeIt& first(NodeIt& v) const { |
66 NodeIt& first(NodeIt& v) const { |
73 v=NodeIt(*this); return v; } |
67 v=NodeIt(*this); return v; } |
74 EdgeIt& first(EdgeIt& e) const { |
68 EdgeIt& first(EdgeIt& e) const { |
75 e=EdgeIt(*this); return e; } |
69 e=EdgeIt(*this); return e; } |
76 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
70 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
77 e=OutEdgeIt(*this,v); return e; } |
71 e=OutEdgeIt(*this,v); return e; } |
78 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
72 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
79 e=InEdgeIt(*this,v); return e; } |
73 e=InEdgeIt(*this,v); return e; } |
80 |
74 |
81 static bool valid(Edge e) { return e.n!=-1; } |
|
82 static bool valid(Node n) { return n.n!=-1; } |
|
83 |
|
84 template <typename It> It getNext(It it) const |
|
85 { It tmp(it); return next(tmp); } |
|
86 |
|
87 NodeIt& next(NodeIt& it) const { |
|
88 it.n=(it.n+2)%(NodeNum+1)-1; |
|
89 return it; |
|
90 } |
|
91 OutEdgeIt& next(OutEdgeIt& it) const |
|
92 { it.n+=NodeNum; if(it.n>=EdgeNum) it.n=-1; return it; } |
|
93 InEdgeIt& next(InEdgeIt& it) const |
|
94 { if(!((++it.n)%NodeNum)) it.n=-1; return it; } |
|
95 static EdgeIt& next(EdgeIt& it) { --it.n; return it; } |
|
96 |
|
97 static int id(Node v) { return v.n; } |
75 static int id(Node v) { return v.n; } |
98 static int id(Edge e) { return e.n; } |
76 static int id(Edge e) { return e.n; } |
99 |
77 |
|
78 /// Finds an edge between two nodes. |
|
79 |
|
80 /// Finds an edge from node \c u to node \c v. |
|
81 /// |
|
82 /// If \c prev is \ref INVALID (this is the default value), then |
|
83 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
84 /// the next edge from \c u to \c v after \c prev. |
|
85 /// \return The found edge or INVALID if there is no such an edge. |
|
86 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
|
87 { |
|
88 return prev.n==-1?Edge(*this,u.n,v.n):INVALID; |
|
89 } |
|
90 |
|
91 |
100 class Node { |
92 class Node { |
101 friend class FullGraph; |
93 friend class FullGraph; |
102 template <typename T> friend class NodeMap; |
94 template <typename T> friend class NodeMap; |
103 |
95 |
104 friend class Edge; |
96 friend class Edge; |
117 bool operator!=(const Node i) const {return n!=i.n;} |
109 bool operator!=(const Node i) const {return n!=i.n;} |
118 bool operator<(const Node i) const {return n<i.n;} |
110 bool operator<(const Node i) const {return n<i.n;} |
119 }; |
111 }; |
120 |
112 |
121 class NodeIt : public Node { |
113 class NodeIt : public Node { |
|
114 const FullGraph *G; |
122 friend class FullGraph; |
115 friend class FullGraph; |
123 public: |
116 public: |
124 NodeIt() : Node() { } |
117 NodeIt() : Node() { } |
|
118 NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { } |
125 NodeIt(Invalid i) : Node(i) { } |
119 NodeIt(Invalid i) : Node(i) { } |
126 NodeIt(const FullGraph& G) : Node(G.NodeNum?0:-1) { } |
120 NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { } |
127 ///\todo Undocumented conversion Node -\> NodeIt. |
121 ///\todo Undocumented conversion Node -\> NodeIt. |
128 NodeIt(const FullGraph& G, const Node &n) : Node(n) { } |
122 NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; } |
129 }; |
123 }; |
130 |
124 |
131 class Edge { |
125 class Edge { |
132 friend class FullGraph; |
126 friend class FullGraph; |
133 template <typename T> friend class EdgeMap; |
127 template <typename T> friend class EdgeMap; |
136 friend class NodeIt; |
130 friend class NodeIt; |
137 protected: |
131 protected: |
138 int n; //NodeNum*head+tail; |
132 int n; //NodeNum*head+tail; |
139 friend int FullGraph::id(Edge e); |
133 friend int FullGraph::id(Edge e); |
140 |
134 |
141 Edge(int nn) {n=nn;} |
135 Edge(int nn) : n(nn) {} |
|
136 Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {} |
142 public: |
137 public: |
143 Edge() { } |
138 Edge() { } |
144 Edge (Invalid) { n=-1; } |
139 Edge (Invalid) { n=-1; } |
145 bool operator==(const Edge i) const {return n==i.n;} |
140 bool operator==(const Edge i) const {return n==i.n;} |
146 bool operator!=(const Edge i) const {return n!=i.n;} |
141 bool operator!=(const Edge i) const {return n!=i.n;} |
152 }; |
147 }; |
153 |
148 |
154 class EdgeIt : public Edge { |
149 class EdgeIt : public Edge { |
155 friend class FullGraph; |
150 friend class FullGraph; |
156 public: |
151 public: |
157 EdgeIt(const FullGraph& G) : Edge(G.EdgeNum-1) { } |
152 EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { } |
|
153 EdgeIt(const FullGraph&, Edge e) : Edge(e) { } |
158 EdgeIt (Invalid i) : Edge(i) { } |
154 EdgeIt (Invalid i) : Edge(i) { } |
159 EdgeIt() : Edge() { } |
155 EdgeIt() : Edge() { } |
|
156 EdgeIt& operator++() { --n; return *this; } |
|
157 |
160 ///\bug This is a workaround until somebody tells me how to |
158 ///\bug This is a workaround until somebody tells me how to |
161 ///make class \c SymFullGraph::SymEdgeMap friend of Edge |
159 ///make class \c SymFullGraph::SymEdgeMap friend of Edge |
162 int &idref() {return n;} |
160 int &idref() {return n;} |
163 }; |
161 }; |
164 |
162 |
165 class OutEdgeIt : public Edge { |
163 class OutEdgeIt : public Edge { |
|
164 const FullGraph *G; |
166 friend class FullGraph; |
165 friend class FullGraph; |
167 public: |
166 public: |
168 OutEdgeIt() : Edge() { } |
167 OutEdgeIt() : Edge() { } |
|
168 OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { } |
169 OutEdgeIt (Invalid i) : Edge(i) { } |
169 OutEdgeIt (Invalid i) : Edge(i) { } |
170 |
170 |
171 OutEdgeIt(const FullGraph& G,const Node v) |
171 OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {} |
172 : Edge(v.n) {} |
172 |
|
173 OutEdgeIt& operator++() |
|
174 { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; } |
|
175 |
173 }; |
176 }; |
174 |
177 |
175 class InEdgeIt : public Edge { |
178 class InEdgeIt : public Edge { |
|
179 const FullGraph *G; |
176 friend class FullGraph; |
180 friend class FullGraph; |
177 public: |
181 public: |
178 InEdgeIt() : Edge() { } |
182 InEdgeIt() : Edge() { } |
|
183 InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { } |
179 InEdgeIt (Invalid i) : Edge(i) { } |
184 InEdgeIt (Invalid i) : Edge(i) { } |
180 InEdgeIt(const FullGraph& G,Node v) :Edge(v.n*G.NodeNum){} |
185 InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {} |
|
186 InEdgeIt& operator++() |
|
187 { if(!((++n)%G->NodeNum)) n=-1; return *this; } |
181 }; |
188 }; |
182 |
189 |
183 template <typename T> class NodeMap |
190 template <typename T> class NodeMap |
184 { |
191 { |
185 std::vector<T> container; |
192 std::vector<T> container; |