54 public: |
54 public: |
55 |
55 |
56 typedef True NodeNumTag; |
56 typedef True NodeNumTag; |
57 typedef True EdgeNumTag; |
57 typedef True EdgeNumTag; |
58 |
58 |
59 Node operator()(int index) const { return Node(index); } |
59 Node operator()(int ix) const { return Node(ix); } |
60 int index(const Node& node) const { return node.id; } |
60 int index(const Node& node) const { return node.id; } |
61 |
61 |
62 Edge edge(const Node& u, const Node& v) const { |
62 Edge edge(const Node& u, const Node& v) const { |
63 return Edge(*this, u.id, v.id); |
63 return Edge(*this, u.id, v.id); |
64 } |
64 } |
127 |
127 |
128 static void next(Node& node) { |
128 static void next(Node& node) { |
129 --node.id; |
129 --node.id; |
130 } |
130 } |
131 |
131 |
132 void first(Edge& edge) const { |
132 void first(Edge& e) const { |
133 edge.id = _edgeNum-1; |
133 e.id = _edgeNum-1; |
134 } |
134 } |
135 |
135 |
136 static void next(Edge& edge) { |
136 static void next(Edge& e) { |
137 --edge.id; |
137 --e.id; |
138 } |
138 } |
139 |
139 |
140 void firstOut(Edge& edge, const Node& node) const { |
140 void firstOut(Edge& e, const Node& n) const { |
141 edge.id = _edgeNum + node.id - _nodeNum; |
141 e.id = _edgeNum + n.id - _nodeNum; |
142 } |
142 } |
143 |
143 |
144 void nextOut(Edge& edge) const { |
144 void nextOut(Edge& e) const { |
145 edge.id -= _nodeNum; |
145 e.id -= _nodeNum; |
146 if (edge.id < 0) edge.id = -1; |
146 if (e.id < 0) e.id = -1; |
147 } |
147 } |
148 |
148 |
149 void firstIn(Edge& edge, const Node& node) const { |
149 void firstIn(Edge& e, const Node& n) const { |
150 edge.id = node.id * _nodeNum; |
150 e.id = n.id * _nodeNum; |
151 } |
151 } |
152 |
152 |
153 void nextIn(Edge& edge) const { |
153 void nextIn(Edge& e) const { |
154 ++edge.id; |
154 ++e.id; |
155 if (edge.id % _nodeNum == 0) edge.id = -1; |
155 if (e.id % _nodeNum == 0) e.id = -1; |
156 } |
156 } |
157 |
157 |
158 }; |
158 }; |
159 |
159 |
160 typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase; |
160 typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase; |
205 /// |
205 /// |
206 /// Returns the node with the given index. Because it is a |
206 /// Returns the node with the given index. Because it is a |
207 /// static size graph the node's of the graph can be indiced |
207 /// static size graph the node's of the graph can be indiced |
208 /// by the range from 0 to \e nodeNum()-1 and the index of |
208 /// by the range from 0 to \e nodeNum()-1 and the index of |
209 /// the node can accessed by the \e index() member. |
209 /// the node can accessed by the \e index() member. |
210 Node operator()(int index) const { return Parent::operator()(index); } |
210 Node operator()(int ix) const { return Parent::operator()(ix); } |
211 |
211 |
212 /// \brief Returns the index of the node. |
212 /// \brief Returns the index of the node. |
213 /// |
213 /// |
214 /// Returns the index of the node. Because it is a |
214 /// Returns the index of the node. Because it is a |
215 /// static size graph the node's of the graph can be indiced |
215 /// static size graph the node's of the graph can be indiced |
248 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; } |
248 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; } |
249 |
249 |
250 public: |
250 public: |
251 |
251 |
252 |
252 |
253 Node operator()(int index) const { return Node(index); } |
253 Node operator()(int ix) const { return Node(ix); } |
254 int index(const Node& node) const { return node.id; } |
254 int index(const Node& node) const { return node.id; } |
255 |
255 |
256 Edge edge(const Node& u, const Node& v) const { |
256 Edge edge(const Node& u, const Node& v) const { |
257 return Edge(u.id * (u.id - 1) / 2 + v.id); |
257 return Edge(u.id * (u.id - 1) / 2 + v.id); |
258 } |
258 } |
269 static Node nodeFromId(int id) { return Node(id);} |
269 static Node nodeFromId(int id) { return Node(id);} |
270 static Edge edgeFromId(int id) { return Edge(id);} |
270 static Edge edgeFromId(int id) { return Edge(id);} |
271 |
271 |
272 Node source(Edge e) const { |
272 Node source(Edge e) const { |
273 /// \todo we may do it faster |
273 /// \todo we may do it faster |
274 return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2); |
274 return Node((int(sqrt(double(1 + 8 * e.id)) + 1)) / 2); |
275 } |
275 } |
276 |
276 |
277 Node target(Edge e) const { |
277 Node target(Edge e) const { |
278 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
278 int s = (int(sqrt(double(1 + 8 * e.id)) + 1)) / 2; |
279 return Node(e.id - (source) * (source - 1) / 2); |
279 return Node(e.id - s * (s - 1) / 2); |
280 } |
280 } |
281 |
281 |
282 static int id(Node v) { return v.id; } |
282 static int id(Node v) { return v.id; } |
283 static int id(Edge e) { return e.id; } |
283 static int id(Edge e) { return e.id; } |
284 |
284 |
320 bool operator==(const Edge edge) const {return id == edge.id;} |
320 bool operator==(const Edge edge) const {return id == edge.id;} |
321 bool operator!=(const Edge edge) const {return id != edge.id;} |
321 bool operator!=(const Edge edge) const {return id != edge.id;} |
322 bool operator<(const Edge edge) const {return id < edge.id;} |
322 bool operator<(const Edge edge) const {return id < edge.id;} |
323 }; |
323 }; |
324 |
324 |
325 void first(Node& node) const { |
325 void first(Node& n) const { |
326 node.id = _nodeNum - 1; |
326 n.id = _nodeNum - 1; |
327 } |
327 } |
328 |
328 |
329 static void next(Node& node) { |
329 static void next(Node& n) { |
330 --node.id; |
330 --n.id; |
331 } |
331 } |
332 |
332 |
333 void first(Edge& edge) const { |
333 void first(Edge& e) const { |
334 edge.id = _edgeNum - 1; |
334 e.id = _edgeNum - 1; |
335 } |
335 } |
336 |
336 |
337 static void next(Edge& edge) { |
337 static void next(Edge& e) { |
338 --edge.id; |
338 --e.id; |
339 } |
339 } |
340 |
340 |
341 void firstOut(Edge& edge, const Node& node) const { |
341 void firstOut(Edge& e, const Node& n) const { |
342 int src = node.id; |
342 int src = n.id; |
343 int trg = 0; |
343 int trg = 0; |
344 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); |
344 e.id = (trg < src ? src * (src - 1) / 2 + trg : -1); |
345 } |
345 } |
346 |
346 |
347 /// \todo with specialized iterators we can make faster iterating |
347 /// \todo with specialized iterators we can make faster iterating |
348 void nextOut(Edge& edge) const { |
348 void nextOut(Edge& e) const { |
349 int src = source(edge).id; |
349 int src = source(e).id; |
350 int trg = target(edge).id; |
350 int trg = target(e).id; |
351 ++trg; |
351 ++trg; |
352 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); |
352 e.id = (trg < src ? src * (src - 1) / 2 + trg : -1); |
353 } |
353 } |
354 |
354 |
355 void firstIn(Edge& edge, const Node& node) const { |
355 void firstIn(Edge& e, const Node& n) const { |
356 int src = node.id + 1; |
356 int src = n.id + 1; |
357 int trg = node.id; |
357 int trg = n.id; |
358 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); |
358 e.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); |
359 } |
359 } |
360 |
360 |
361 void nextIn(Edge& edge) const { |
361 void nextIn(Edge& e) const { |
362 int src = source(edge).id; |
362 int src = source(e).id; |
363 int trg = target(edge).id; |
363 int trg = target(e).id; |
364 ++src; |
364 ++src; |
365 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); |
365 e.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); |
366 } |
366 } |
367 |
367 |
368 }; |
368 }; |
369 |
369 |
370 typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> > |
370 typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> > |
419 /// |
419 /// |
420 /// Returns the node with the given index. Because it is a |
420 /// Returns the node with the given index. Because it is a |
421 /// static size graph the node's of the graph can be indiced |
421 /// static size graph the node's of the graph can be indiced |
422 /// by the range from 0 to \e nodeNum()-1 and the index of |
422 /// by the range from 0 to \e nodeNum()-1 and the index of |
423 /// the node can accessed by the \e index() member. |
423 /// the node can accessed by the \e index() member. |
424 Node operator()(int index) const { return Parent::operator()(index); } |
424 Node operator()(int ix) const { return Parent::operator()(ix); } |
425 |
425 |
426 /// \brief Returns the index of the node. |
426 /// \brief Returns the index of the node. |
427 /// |
427 /// |
428 /// Returns the index of the node. Because it is a |
428 /// Returns the index of the node. Because it is a |
429 /// static size graph the node's of the graph can be indiced |
429 /// static size graph the node's of the graph can be indiced |
476 |
476 |
477 protected: |
477 protected: |
478 |
478 |
479 FullBpUGraphBase() {} |
479 FullBpUGraphBase() {} |
480 |
480 |
481 void construct(int aNodeNum, int bNodeNum) { |
481 void construct(int ann, int bnn) { |
482 _aNodeNum = aNodeNum; |
482 _aNodeNum = ann; |
483 _bNodeNum = bNodeNum; |
483 _bNodeNum = bnn; |
484 _edgeNum = aNodeNum * bNodeNum; |
484 _edgeNum = ann * bnn; |
485 } |
485 } |
486 |
486 |
487 public: |
487 public: |
488 |
488 |
489 class NodeSetError : public LogicError { |
489 class NodeSetError : public LogicError { |
519 bool operator==(const UEdge i) const {return id==i.id;} |
519 bool operator==(const UEdge i) const {return id==i.id;} |
520 bool operator!=(const UEdge i) const {return id!=i.id;} |
520 bool operator!=(const UEdge i) const {return id!=i.id;} |
521 bool operator<(const UEdge i) const {return id<i.id;} |
521 bool operator<(const UEdge i) const {return id<i.id;} |
522 }; |
522 }; |
523 |
523 |
524 Node aNode(int index) const { return Node(index << 1); } |
524 Node aNode(int ix) const { return Node(ix << 1); } |
525 Node bNode(int index) const { return Node((index << 1) + 1); } |
525 Node bNode(int ix) const { return Node((ix << 1) + 1); } |
526 |
526 |
527 int aNodeIndex(const Node& node) const { return node.id >> 1; } |
527 int aNodeIndex(const Node& node) const { return node.id >> 1; } |
528 int bNodeIndex(const Node& node) const { return node.id >> 1; } |
528 int bNodeIndex(const Node& node) const { return node.id >> 1; } |
529 |
529 |
530 UEdge uEdge(const Node& u, const Node& v) const { |
530 UEdge uEdge(const Node& u, const Node& v) const { |
693 |
693 |
694 FullBpUGraph() { |
694 FullBpUGraph() { |
695 Parent::construct(0, 0); |
695 Parent::construct(0, 0); |
696 } |
696 } |
697 |
697 |
698 FullBpUGraph(int aNodeNum, int bNodeNum) { |
698 FullBpUGraph(int ann, int bnn) { |
699 Parent::construct(aNodeNum, bNodeNum); |
699 Parent::construct(ann, bnn); |
700 } |
700 } |
701 |
701 |
702 /// \brief Resize the graph |
702 /// \brief Resize the graph |
703 /// |
703 /// |
704 /// Resize the graph |
704 /// Resize the graph |
735 /// |
735 /// |
736 /// Returns the A-node with the given index. Because it is a |
736 /// Returns the A-node with the given index. Because it is a |
737 /// static size graph the node's of the graph can be indiced |
737 /// static size graph the node's of the graph can be indiced |
738 /// by the range from 0 to \e aNodeNum()-1 and the index of |
738 /// by the range from 0 to \e aNodeNum()-1 and the index of |
739 /// the node can accessed by the \e aNodeIndex() member. |
739 /// the node can accessed by the \e aNodeIndex() member. |
740 Node aNode(int index) const { return Parent::aNode(index); } |
740 Node aNode(int ix) const { return Parent::aNode(ix); } |
741 |
741 |
742 /// \brief Returns the B-node with the given index. |
742 /// \brief Returns the B-node with the given index. |
743 /// |
743 /// |
744 /// Returns the B-node with the given index. Because it is a |
744 /// Returns the B-node with the given index. Because it is a |
745 /// static size graph the node's of the graph can be indiced |
745 /// static size graph the node's of the graph can be indiced |
746 /// by the range from 0 to \e bNodeNum()-1 and the index of |
746 /// by the range from 0 to \e bNodeNum()-1 and the index of |
747 /// the node can accessed by the \e bNodeIndex() member. |
747 /// the node can accessed by the \e bNodeIndex() member. |
748 Node bNode(int index) const { return Parent::bNode(index); } |
748 Node bNode(int ix) const { return Parent::bNode(ix); } |
749 |
749 |
750 /// \brief Returns the index of the A-node. |
750 /// \brief Returns the index of the A-node. |
751 /// |
751 /// |
752 /// Returns the index of the A-node. Because it is a |
752 /// Returns the index of the A-node. Because it is a |
753 /// static size graph the node's of the graph can be indiced |
753 /// static size graph the node's of the graph can be indiced |