Lemon Graph Format uses label instead of id named map.
2 * lemon/full_graph.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_FULL_GRAPH_H
18 #define LEMON_FULL_GRAPH_H
23 #include <lemon/bits/iterable_graph_extender.h>
24 #include <lemon/bits/alteration_notifier.h>
25 #include <lemon/bits/static_map.h>
26 #include <lemon/bits/graph_extender.h>
28 #include <lemon/invalid.h>
29 #include <lemon/utility.h>
34 ///\brief FullGraph and UndirFullGraph classes.
44 typedef FullGraphBase Graph;
54 ///Creates a full graph with \c n nodes.
55 void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
57 // FullGraphBase(const FullGraphBase &_g)
58 // : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { }
60 typedef True NodeNumTag;
61 typedef True EdgeNumTag;
64 int nodeNum() const { return _nodeNum; }
66 int edgeNum() const { return _edgeNum; }
72 int maxNodeId() const { return _nodeNum-1; }
77 int maxEdgeId() const { return _edgeNum-1; }
79 Node source(Edge e) const { return e.id % _nodeNum; }
80 Node target(Edge e) const { return e.id / _nodeNum; }
85 /// The ID of a valid Node is a nonnegative integer not greater than
86 /// \ref maxNodeId(). The range of the ID's is not surely continuous
87 /// and the greatest node ID can be actually less then \ref maxNodeId().
89 /// The ID of the \ref INVALID node is -1.
90 ///\return The ID of the node \c v.
92 static int id(Node v) { return v.id; }
95 /// The ID of a valid Edge is a nonnegative integer not greater than
96 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
97 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
99 /// The ID of the \ref INVALID edge is -1.
100 ///\return The ID of the edge \c e.
101 static int id(Edge e) { return e.id; }
103 static Node nodeFromId(int id) { return Node(id);}
105 static Edge edgeFromId(int id) { return Edge(id);}
107 typedef True FindEdgeTag;
109 /// Finds an edge between two nodes.
111 /// Finds an edge from node \c u to node \c v.
113 /// If \c prev is \ref INVALID (this is the default value), then
114 /// It finds the first edge from \c u to \c v. Otherwise it looks for
115 /// the next edge from \c u to \c v after \c prev.
116 /// \return The found edge or INVALID if there is no such an edge.
117 Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
118 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
123 friend class FullGraphBase;
127 Node(int _id) : id(_id) {}
130 Node (Invalid) : id(-1) {}
131 bool operator==(const Node node) const {return id == node.id;}
132 bool operator!=(const Node node) const {return id != node.id;}
133 bool operator<(const Node node) const {return id < node.id;}
139 friend class FullGraphBase;
142 int id; // _nodeNum * target + source;
144 Edge(int _id) : id(_id) {}
146 Edge(const FullGraphBase& _graph, int source, int target)
147 : id(_graph._nodeNum * target+source) {}
150 Edge (Invalid) { id = -1; }
151 bool operator==(const Edge edge) const {return id == edge.id;}
152 bool operator!=(const Edge edge) const {return id != edge.id;}
153 bool operator<(const Edge edge) const {return id < edge.id;}
156 void first(Node& node) const {
157 node.id = _nodeNum-1;
160 static void next(Node& node) {
164 void first(Edge& edge) const {
165 edge.id = _edgeNum-1;
168 static void next(Edge& edge) {
172 void firstOut(Edge& edge, const Node& node) const {
173 edge.id = _edgeNum + node.id - _nodeNum;
176 void nextOut(Edge& edge) const {
178 if (edge.id < 0) edge.id = -1;
181 void firstIn(Edge& edge, const Node& node) const {
182 edge.id = node.id * _nodeNum;
185 void nextIn(Edge& edge) const {
187 if (edge.id % _nodeNum == 0) edge.id = -1;
192 typedef StaticMappableGraphExtender<
193 IterableGraphExtender<
194 AlterableGraphExtender<
195 GraphExtender<FullGraphBase> > > > ExtendedFullGraphBase;
199 /// \brief A full graph class.
201 /// This is a simple and fast directed full graph implementation.
202 /// It is completely static, so you can neither add nor delete either
204 /// Thus it conforms to
205 /// the \ref concept::StaticGraph "StaticGraph" concept
206 /// \sa concept::StaticGraph.
208 /// \author Alpar Juttner
209 class FullGraph : public ExtendedFullGraphBase {
212 FullGraph(int n) { construct(n); }
216 class UndirFullGraphBase {
221 typedef UndirFullGraphBase Graph;
228 UndirFullGraphBase() {}
231 ///Creates a full graph with \c n nodes.
232 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
234 // FullGraphBase(const FullGraphBase &_g)
235 // : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { }
237 typedef True NodeNumTag;
238 typedef True EdgeNumTag;
241 int nodeNum() const { return _nodeNum; }
243 int edgeNum() const { return _edgeNum; }
249 int maxNodeId() const { return _nodeNum-1; }
254 int maxEdgeId() const { return _edgeNum-1; }
256 Node source(Edge e) const {
257 /// \todo we may do it faster
258 return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
261 Node target(Edge e) const {
262 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
263 return Node(e.id - (source) * (source - 1) / 2);
269 /// The ID of a valid Node is a nonnegative integer not greater than
270 /// \ref maxNodeId(). The range of the ID's is not surely continuous
271 /// and the greatest node ID can be actually less then \ref maxNodeId().
273 /// The ID of the \ref INVALID node is -1.
274 ///\return The ID of the node \c v.
276 static int id(Node v) { return v.id; }
279 /// The ID of a valid Edge is a nonnegative integer not greater than
280 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
281 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
283 /// The ID of the \ref INVALID edge is -1.
284 ///\return The ID of the edge \c e.
285 static int id(Edge e) { return e.id; }
287 /// Finds an edge between two nodes.
289 /// Finds an edge from node \c u to node \c v.
291 /// If \c prev is \ref INVALID (this is the default value), then
292 /// It finds the first edge from \c u to \c v. Otherwise it looks for
293 /// the next edge from \c u to \c v after \c prev.
294 /// \return The found edge or INVALID if there is no such an edge.
295 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
296 if (prev.id != -1 || u.id <= v.id) return -1;
297 return Edge(u.id * (u.id - 1) / 2 + v.id);
300 typedef True FindEdgeTag;
304 friend class UndirFullGraphBase;
308 Node(int _id) { id = _id;}
311 Node (Invalid) { id = -1; }
312 bool operator==(const Node node) const {return id == node.id;}
313 bool operator!=(const Node node) const {return id != node.id;}
314 bool operator<(const Node node) const {return id < node.id;}
320 friend class UndirFullGraphBase;
323 int id; // _nodeNum * target + source;
325 Edge(int _id) : id(_id) {}
329 Edge (Invalid) { id = -1; }
330 bool operator==(const Edge edge) const {return id == edge.id;}
331 bool operator!=(const Edge edge) const {return id != edge.id;}
332 bool operator<(const Edge edge) const {return id < edge.id;}
335 void first(Node& node) const {
336 node.id = _nodeNum - 1;
339 static void next(Node& node) {
343 void first(Edge& edge) const {
344 edge.id = _edgeNum - 1;
347 static void next(Edge& edge) {
351 void firstOut(Edge& edge, const Node& node) const {
354 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
357 /// \todo with specialized iterators we can make faster iterating
358 void nextOut(Edge& edge) const {
359 int src = source(edge).id;
360 int trg = target(edge).id;
362 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
365 void firstIn(Edge& edge, const Node& node) const {
366 int src = node.id + 1;
368 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
371 void nextIn(Edge& edge) const {
372 int src = source(edge).id;
373 int trg = target(edge).id;
375 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
380 typedef StaticMappableUndirGraphExtender<
381 IterableUndirGraphExtender<
382 AlterableUndirGraphExtender<
383 UndirGraphExtender<UndirFullGraphBase> > > > ExtendedUndirFullGraphBase;
387 /// \brief An undirected full graph class.
389 /// This is a simple and fast undirected full graph implementation.
390 /// It is completely static, so you can neither add nor delete either
393 /// The main difference beetween the \e FullGraph and \e UndirFullGraph class
394 /// is that this class conforms to the undirected graph concept and
395 /// it does not contain the loop edges.
399 /// \author Balazs Dezso
400 class UndirFullGraph : public ExtendedUndirFullGraphBase {
402 UndirFullGraph(int n) { construct(n); }
406 class FullUndirBipartiteGraphBase {
416 class NodeSetError : public LogicError {
417 virtual const char* exceptionName() const {
418 return "lemon::FullUndirBipartiteGraph::NodeSetError";
423 friend class FullUndirBipartiteGraphBase;
427 Node(int _id) : id(_id) {}
430 Node(Invalid) { id = -1; }
431 bool operator==(const Node i) const {return id==i.id;}
432 bool operator!=(const Node i) const {return id!=i.id;}
433 bool operator<(const Node i) const {return id<i.id;}
437 friend class FullUndirBipartiteGraphBase;
441 Edge(int _id) { id = _id;}
444 Edge (Invalid) { id = -1; }
445 bool operator==(const Edge i) const {return id==i.id;}
446 bool operator!=(const Edge i) const {return id!=i.id;}
447 bool operator<(const Edge i) const {return id<i.id;}
450 void construct(int upperNodeNum, int lowerNodeNum) {
451 _upperNodeNum = upperNodeNum;
452 _lowerNodeNum = lowerNodeNum;
453 _edgeNum = upperNodeNum * lowerNodeNum;
456 void firstUpper(Node& node) const {
457 node.id = 2 * _upperNodeNum - 2;
458 if (node.id < 0) node.id = -1;
460 void nextUpper(Node& node) const {
462 if (node.id < 0) node.id = -1;
465 void firstLower(Node& node) const {
466 node.id = 2 * _lowerNodeNum - 1;
468 void nextLower(Node& node) const {
472 void first(Node& node) const {
473 if (_upperNodeNum > 0) {
474 node.id = 2 * _upperNodeNum - 2;
476 node.id = 2 * _lowerNodeNum - 1;
479 void next(Node& node) const {
482 node.id = 2 * _lowerNodeNum - 1;
486 void first(Edge& edge) const {
487 edge.id = _edgeNum - 1;
489 void next(Edge& edge) const {
493 void firstDown(Edge& edge, const Node& node) const {
494 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
495 edge.id = (node.id >> 1) * _lowerNodeNum;
497 void nextDown(Edge& edge) const {
499 if (edge.id % _lowerNodeNum == 0) edge.id = -1;
502 void firstUp(Edge& edge, const Node& node) const {
503 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
504 edge.id = (node.id >> 1);
506 void nextUp(Edge& edge) const {
507 edge.id += _lowerNodeNum;
508 if (edge.id >= _edgeNum) edge.id = -1;
511 static int id(const Node& node) {
514 static Node nodeFromId(int id) {
517 int maxNodeId() const {
518 return _upperNodeNum > _lowerNodeNum ?
519 _upperNodeNum * 2 - 2 : _lowerNodeNum * 2 - 1;
522 static int id(const Edge& edge) {
525 static Edge edgeFromId(int id) {
528 int maxEdgeId() const {
532 static int upperId(const Node& node) {
535 static Node fromUpperId(int id, Node) {
536 return Node(id << 1);
538 int maxUpperId() const {
539 return _upperNodeNum;
542 static int lowerId(const Node& node) {
545 static Node fromLowerId(int id) {
546 return Node((id << 1) + 1);
548 int maxLowerId() const {
549 return _lowerNodeNum;
552 Node upperNode(const Edge& edge) const {
553 return Node((edge.id / _lowerNodeNum) << 1);
555 Node lowerNode(const Edge& edge) const {
556 return Node(((edge.id % _lowerNodeNum) << 1) + 1);
559 static bool upper(const Node& node) {
560 return (node.id & 1) == 0;
563 static bool lower(const Node& node) {
564 return (node.id & 1) == 1;
567 static Node upperNode(int index) {
568 return Node(index << 1);
571 static Node lowerNode(int index) {
572 return Node((index << 1) + 1);
578 typedef StaticMappableUndirBipartiteGraphExtender<
579 IterableUndirBipartiteGraphExtender<
580 AlterableUndirBipartiteGraphExtender<
581 UndirBipartiteGraphExtender <
582 FullUndirBipartiteGraphBase> > > >
583 ExtendedFullUndirBipartiteGraphBase;
586 class FullUndirBipartiteGraph :
587 public ExtendedFullUndirBipartiteGraphBase {
589 typedef ExtendedFullUndirBipartiteGraphBase Parent;
590 FullUndirBipartiteGraph(int upperNodeNum, int lowerNodeNum) {
591 Parent::construct(upperNodeNum, lowerNodeNum);
598 #endif //LEMON_FULL_GRAPH_H