Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

full_graph.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/full_graph.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
00014  *
00015  */
00016 
00017 #ifndef LEMON_FULL_GRAPH_H
00018 #define LEMON_FULL_GRAPH_H
00019 
00020 #include <cmath>
00021 
00022 
00023 #include <lemon/iterable_graph_extender.h>
00024 #include <lemon/alteration_notifier.h>
00025 #include <lemon/default_map.h>
00026 
00027 #include <lemon/invalid.h>
00028 #include <lemon/utility.h>
00029 
00030 
00034 
00035 
00036 namespace lemon {
00037 
00040 
00041   class FullGraphBase {
00042     int NodeNum;
00043     int EdgeNum;
00044   public:
00045 
00046     typedef FullGraphBase Graph;
00047 
00048     class Node;
00049     class Edge;
00050 
00051   public:
00052 
00053     FullGraphBase() {}
00054 
00055 
00057     void construct(int n) { NodeNum = n; EdgeNum = n * n; }
00059     //    FullGraphBase(const FullGraphBase &_g)
00060     //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
00061     
00062     typedef True NodeNumTag;
00063     typedef True EdgeNumTag;
00064 
00066     int nodeNum() const { return NodeNum; }
00068     int edgeNum() const { return EdgeNum; }
00069 
00071     
00074     int maxId(Node = INVALID) const { return NodeNum-1; }
00076     
00079     int maxId(Edge = INVALID) const { return EdgeNum-1; }
00080 
00081     Node source(Edge e) const { return e.id % NodeNum; }
00082     Node target(Edge e) const { return e.id / NodeNum; }
00083 
00084 
00086     
00093 
00094     static int id(Node v) { return v.id; }
00096     
00103     static int id(Edge e) { return e.id; }
00104 
00105     static Node fromId(int id, Node) { return Node(id);}
00106     
00107     static Edge fromId(int id, Edge) { return Edge(id);}
00108 
00110     
00117     Edge findEdge(Node u,Node v, Edge prev = INVALID) 
00118     {
00119       return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
00120     }
00121     
00122       
00123     class Node {
00124       friend class FullGraphBase;
00125 
00126     protected:
00127       int id;
00128       Node(int _id) { id = _id;}
00129     public:
00130       Node() {}
00131       Node (Invalid) { id = -1; }
00132       bool operator==(const Node node) const {return id == node.id;}
00133       bool operator!=(const Node node) const {return id != node.id;}
00134       bool operator<(const Node node) const {return id < node.id;}
00135     };
00136     
00137 
00138 
00139     class Edge {
00140       friend class FullGraphBase;
00141       
00142     protected:
00143       int id;  // NodeNum * target + source;
00144 
00145       Edge(int _id) : id(_id) {}
00146 
00147       Edge(const FullGraphBase& _graph, int source, int target) 
00148         : id(_graph.NodeNum * target+source) {}
00149     public:
00150       Edge() { }
00151       Edge (Invalid) { id = -1; }
00152       bool operator==(const Edge edge) const {return id == edge.id;}
00153       bool operator!=(const Edge edge) const {return id != edge.id;}
00154       bool operator<(const Edge edge) const {return id < edge.id;}
00155     };
00156 
00157     void first(Node& node) const {
00158       node.id = NodeNum-1;
00159     }
00160 
00161     static void next(Node& node) {
00162       --node.id;
00163     }
00164 
00165     void first(Edge& edge) const {
00166       edge.id = EdgeNum-1;
00167     }
00168 
00169     static void next(Edge& edge) {
00170       --edge.id;
00171     }
00172 
00173     void firstOut(Edge& edge, const Node& node) const {
00174       edge.id = EdgeNum + node.id - NodeNum;
00175     }
00176 
00177     void nextOut(Edge& edge) const {
00178       edge.id -= NodeNum;
00179       if (edge.id < 0) edge.id = -1;
00180     }
00181 
00182     void firstIn(Edge& edge, const Node& node) const {
00183       edge.id = node.id * NodeNum;
00184     }
00185     
00186     void nextIn(Edge& edge) const {
00187       ++edge.id;
00188       if (edge.id % NodeNum == 0) edge.id = -1;
00189     }
00190 
00191   };
00192 
00193 
00194   typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
00195   typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
00196   typedef DefaultMappableGraphExtender<IterableFullGraphBase> MappableFullGraphBase;
00197 
00199 
00208   class FullGraph : public MappableFullGraphBase {
00209   public:
00210 
00211     FullGraph(int n) { construct(n); }
00212   };
00213 
00214 
00215   // Base graph class for UndirFullGraph.
00216   class UndirFullGraphBase {
00217     int NodeNum;
00218     int EdgeNum;
00219   public:
00220 
00221     typedef UndirFullGraphBase Graph;
00222 
00223     class Node;
00224     class Edge;
00225 
00226   public:
00227 
00228     UndirFullGraphBase() {}
00229 
00230 
00232     void construct(int n) { NodeNum = n; EdgeNum = n * (n - 1) / 2; }
00234     //    FullGraphBase(const FullGraphBase &_g)
00235     //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
00236     
00237     typedef True NodeNumTag;
00238     typedef True EdgeNumTag;
00239 
00241     int nodeNum() const { return NodeNum; }
00243     int edgeNum() const { return EdgeNum; }
00244 
00246     
00249     int maxId(Node = INVALID) const { return NodeNum-1; }
00251     
00254     int maxId(Edge = INVALID) const { return EdgeNum-1; }
00255 
00256     Node source(Edge e) const { 
00258       return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2; 
00259     }
00260 
00261     Node target(Edge e) const { 
00262       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
00263       return e.id - (source) * (source - 1) / 2; 
00264     }
00265 
00266 
00268     
00275 
00276     static int id(Node v) { return v.id; }
00278     
00285     static int id(Edge e) { return e.id; }
00286 
00288     
00295     Edge findEdge(Node u,Node v, Edge prev = INVALID) 
00296     {
00297       return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
00298     }
00299     
00300       
00301     class Node {
00302       friend class UndirFullGraphBase;
00303 
00304     protected:
00305       int id;
00306       Node(int _id) { id = _id;}
00307     public:
00308       Node() {}
00309       Node (Invalid) { id = -1; }
00310       bool operator==(const Node node) const {return id == node.id;}
00311       bool operator!=(const Node node) const {return id != node.id;}
00312       bool operator<(const Node node) const {return id < node.id;}
00313     };
00314     
00315 
00316 
00317     class Edge {
00318       friend class UndirFullGraphBase;
00319       
00320     protected:
00321       int id;  // NodeNum * target + source;
00322 
00323       Edge(int _id) : id(_id) {}
00324 
00325       Edge(const UndirFullGraphBase& _graph, int source, int target) 
00326         : id(_graph.NodeNum * target+source) {}
00327     public:
00328       Edge() { }
00329       Edge (Invalid) { id = -1; }
00330       bool operator==(const Edge edge) const {return id == edge.id;}
00331       bool operator!=(const Edge edge) const {return id != edge.id;}
00332       bool operator<(const Edge edge) const {return id < edge.id;}
00333     };
00334 
00335     void first(Node& node) const {
00336       node.id = NodeNum-1;
00337     }
00338 
00339     static void next(Node& node) {
00340       --node.id;
00341     }
00342 
00343     void first(Edge& edge) const {
00344       edge.id = EdgeNum-1;
00345     }
00346 
00347     static void next(Edge& edge) {
00348       --edge.id;
00349     }
00350 
00351     void firstOut(Edge& edge, const Node& node) const {      
00352       edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1;
00353     }
00354 
00356     void nextOut(Edge& e) const {
00357       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
00358       int target = e.id - (source) * (source - 1) / 2; 
00359       ++target;
00360       e.id = target < source ? source * (source - 1) / 2 + target : -1;
00361     }
00362 
00363     void firstIn(Edge& edge, const Node& node) const {
00364       edge.id = node.id * (node.id + 1) / 2 - 1;
00365     }
00366     
00367     void nextIn(Edge& e) const {
00368       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
00369       int target = e.id - (source) * (source - 1) / 2; ++target;
00370       ++source;
00371       e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1;
00372     }
00373 
00374   };
00375 
00377 
00378   
00379 
00381 
00382 } //namespace lemon
00383 
00384 
00385 #endif //LEMON_FULL_GRAPH_H

Generated on Sat Mar 19 10:58:39 2005 for LEMON by  doxygen 1.4.1