lemon-0.x: lemon/full_graph.h@01707a8a4ca6

     1 /* -*- C++ -*-

     2  * lemon/full_graph.h - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     6  *

     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.

    10  *

    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

    13  * purpose.

    14  *

    15  */

    17 #ifndef LEMON_FULL_GRAPH_H

    18 #define LEMON_FULL_GRAPH_H

    20 #include <cmath>

    23 #include <lemon/bits/iterable_graph_extender.h>

    24 #include <lemon/bits/alteration_notifier.h>

    25 #include <lemon/bits/default_map.h>

    27 #include <lemon/invalid.h>

    28 #include <lemon/utility.h>

    31 ///\ingroup graphs

    32 ///\file

    33 ///\brief FullGraph and SymFullGraph classes.

    36 namespace lemon {

    38   class FullGraphBase {

    39     int NodeNum;

    40     int EdgeNum;

    41   public:

    43     typedef FullGraphBase Graph;

    45     class Node;

    46     class Edge;

    48   public:

    50     FullGraphBase() {}

    53     ///Creates a full graph with \c n nodes.

    54     void construct(int n) { NodeNum = n; EdgeNum = n * n; }

    55     ///

    56     //    FullGraphBase(const FullGraphBase &_g)

    57     //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }

    59     typedef True NodeNumTag;

    60     typedef True EdgeNumTag;

    62     ///Number of nodes.

    63     int nodeNum() const { return NodeNum; }

    64     ///Number of edges.

    65     int edgeNum() const { return EdgeNum; }

    67     /// Maximum node ID.

    69     /// Maximum node ID.

    70     ///\sa id(Node)

    71     int maxId(Node = INVALID) const { return NodeNum-1; }

    72     /// Maximum edge ID.

    74     /// Maximum edge ID.

    75     ///\sa id(Edge)

    76     int maxId(Edge = INVALID) const { return EdgeNum-1; }

    78     Node source(Edge e) const { return e.id % NodeNum; }

    79     Node target(Edge e) const { return e.id / NodeNum; }

    82     /// Node ID.

    84     /// The ID of a valid Node is a nonnegative integer not greater than

    85     /// \ref maxNodeId(). The range of the ID's is not surely continuous

    86     /// and the greatest node ID can be actually less then \ref maxNodeId().

    87     ///

    88     /// The ID of the \ref INVALID node is -1.

    89     ///\return The ID of the node \c v.

    91     static int id(Node v) { return v.id; }

    92     /// Edge ID.

    94     /// The ID of a valid Edge is a nonnegative integer not greater than

    95     /// \ref maxEdgeId(). The range of the ID's is not surely continuous

    96     /// and the greatest edge ID can be actually less then \ref maxEdgeId().

    97     ///

    98     /// The ID of the \ref INVALID edge is -1.

    99     ///\return The ID of the edge \c e.

   100     static int id(Edge e) { return e.id; }

   102     static Node fromId(int id, Node) { return Node(id);}

   104     static Edge fromId(int id, Edge) { return Edge(id);}

   106     /// Finds an edge between two nodes.

   108     /// Finds an edge from node \c u to node \c v.

   109     ///

   110     /// If \c prev is \ref INVALID (this is the default value), then

   111     /// It finds the first edge from \c u to \c v. Otherwise it looks for

   112     /// the next edge from \c u to \c v after \c prev.

   113     /// \return The found edge or INVALID if there is no such an edge.

   114     Edge findEdge(Node u,Node v, Edge prev = INVALID)

   115     {

   116       return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;

   117     }

   120     class Node {

   121       friend class FullGraphBase;

   123     protected:

   124       int id;

   125       Node(int _id) { id = _id;}

   126     public:

   127       Node() {}

   128       Node (Invalid) { id = -1; }

   129       bool operator==(const Node node) const {return id == node.id;}

   130       bool operator!=(const Node node) const {return id != node.id;}

   131       bool operator<(const Node node) const {return id < node.id;}

   132     };

   136     class Edge {

   137       friend class FullGraphBase;

   139     protected:

   140       int id;  // NodeNum * target + source;

   142       Edge(int _id) : id(_id) {}

   144       Edge(const FullGraphBase& _graph, int source, int target)

   145 	: id(_graph.NodeNum * target+source) {}

   146     public:

   147       Edge() { }

   148       Edge (Invalid) { id = -1; }

   149       bool operator==(const Edge edge) const {return id == edge.id;}

   150       bool operator!=(const Edge edge) const {return id != edge.id;}

   151       bool operator<(const Edge edge) const {return id < edge.id;}

   152     };

   154     void first(Node& node) const {

   155       node.id = NodeNum-1;

   156     }

   158     static void next(Node& node) {

   159       --node.id;

   160     }

   162     void first(Edge& edge) const {

   163       edge.id = EdgeNum-1;

   164     }

   166     static void next(Edge& edge) {

   167       --edge.id;

   168     }

   170     void firstOut(Edge& edge, const Node& node) const {

   171       edge.id = EdgeNum + node.id - NodeNum;

   172     }

   174     void nextOut(Edge& edge) const {

   175       edge.id -= NodeNum;

   176       if (edge.id < 0) edge.id = -1;

   177     }

   179     void firstIn(Edge& edge, const Node& node) const {

   180       edge.id = node.id * NodeNum;

   181     }

   183     void nextIn(Edge& edge) const {

   184       ++edge.id;

   185       if (edge.id % NodeNum == 0) edge.id = -1;

   186     }

   188   };

   191   typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;

   192   typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;

   193   typedef DefaultMappableGraphExtender<IterableFullGraphBase> MappableFullGraphBase;

   195   /// \addtogroup graphs

   196   /// @{

   198   ///A full graph class.

   200   ///This is a simple and fast directed full graph implementation.

   201   ///It is completely static, so you can neither add nor delete either

   202   ///edges or nodes.

   203   ///Thus it conforms to

   204   ///the \ref concept::StaticGraph "StaticGraph" concept

   205   ///\sa concept::StaticGraph.

   206   ///

   207   ///\author Alpar Juttner

   208   class FullGraph : public MappableFullGraphBase {

   209   public:

   211     FullGraph(int n) { construct(n); }

   212   };

   214   ///@}

   216   // Base graph class for UndirFullGraph.

   217   class UndirFullGraphBase {

   218     int NodeNum;

   219     int EdgeNum;

   220   public:

   222     typedef UndirFullGraphBase Graph;

   224     class Node;

   225     class Edge;

   227   public:

   229     UndirFullGraphBase() {}

   232     ///Creates a full graph with \c n nodes.

   233     void construct(int n) { NodeNum = n; EdgeNum = n * (n - 1) / 2; }

   234     ///

   235     //    FullGraphBase(const FullGraphBase &_g)

   236     //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }

   238     typedef True NodeNumTag;

   239     typedef True EdgeNumTag;

   241     ///Number of nodes.

   242     int nodeNum() const { return NodeNum; }

   243     ///Number of edges.

   244     int edgeNum() const { return EdgeNum; }

   246     /// Maximum node ID.

   248     /// Maximum node ID.

   249     ///\sa id(Node)

   250     int maxId(Node = INVALID) const { return NodeNum-1; }

   251     /// Maximum edge ID.

   253     /// Maximum edge ID.

   254     ///\sa id(Edge)

   255     int maxId(Edge = INVALID) const { return EdgeNum-1; }

   257     Node source(Edge e) const {

   258       /// \todo we may do it faster

   259       return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;

   260     }

   262     Node target(Edge e) const {

   263       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;

   264       return e.id - (source) * (source - 1) / 2;

   265     }

   268     /// Node ID.

   270     /// The ID of a valid Node is a nonnegative integer not greater than

   271     /// \ref maxNodeId(). The range of the ID's is not surely continuous

   272     /// and the greatest node ID can be actually less then \ref maxNodeId().

   273     ///

   274     /// The ID of the \ref INVALID node is -1.

   275     ///\return The ID of the node \c v.

   277     static int id(Node v) { return v.id; }

   278     /// Edge ID.

   280     /// The ID of a valid Edge is a nonnegative integer not greater than

   281     /// \ref maxEdgeId(). The range of the ID's is not surely continuous

   282     /// and the greatest edge ID can be actually less then \ref maxEdgeId().

   283     ///

   284     /// The ID of the \ref INVALID edge is -1.

   285     ///\return The ID of the edge \c e.

   286     static int id(Edge e) { return e.id; }

   288     /// Finds an edge between two nodes.

   290     /// Finds an edge from node \c u to node \c v.

   291     ///

   292     /// If \c prev is \ref INVALID (this is the default value), then

   293     /// It finds the first edge from \c u to \c v. Otherwise it looks for

   294     /// the next edge from \c u to \c v after \c prev.

   295     /// \return The found edge or INVALID if there is no such an edge.

   296     Edge findEdge(Node u,Node v, Edge prev = INVALID)

   297     {

   298       return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;

   299     }

   302     class Node {

   303       friend class UndirFullGraphBase;

   305     protected:

   306       int id;

   307       Node(int _id) { id = _id;}

   308     public:

   309       Node() {}

   310       Node (Invalid) { id = -1; }

   311       bool operator==(const Node node) const {return id == node.id;}

   312       bool operator!=(const Node node) const {return id != node.id;}

   313       bool operator<(const Node node) const {return id < node.id;}

   314     };

   318     class Edge {

   319       friend class UndirFullGraphBase;

   321     protected:

   322       int id;  // NodeNum * target + source;

   324       Edge(int _id) : id(_id) {}

   326       Edge(const UndirFullGraphBase& _graph, int source, int target)

   327 	: id(_graph.NodeNum * target+source) {}

   328     public:

   329       Edge() { }

   330       Edge (Invalid) { id = -1; }

   331       bool operator==(const Edge edge) const {return id == edge.id;}

   332       bool operator!=(const Edge edge) const {return id != edge.id;}

   333       bool operator<(const Edge edge) const {return id < edge.id;}

   334     };

   336     void first(Node& node) const {

   337       node.id = NodeNum-1;

   338     }

   340     static void next(Node& node) {

   341       --node.id;

   342     }

   344     void first(Edge& edge) const {

   345       edge.id = EdgeNum-1;

   346     }

   348     static void next(Edge& edge) {

   349       --edge.id;

   350     }

   352     void firstOut(Edge& edge, const Node& node) const {

   353       edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1;

   354     }

   356     /// \todo with specialized iterators we can make faster iterating

   357     void nextOut(Edge& e) const {

   358       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;

   359       int target = e.id - (source) * (source - 1) / 2;

   360       ++target;

   361       e.id = target < source ? source * (source - 1) / 2 + target : -1;

   362     }

   364     void firstIn(Edge& edge, const Node& node) const {

   365       edge.id = node.id * (node.id + 1) / 2 - 1;

   366     }

   368     void nextIn(Edge& e) const {

   369       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;

   370       int target = e.id - (source) * (source - 1) / 2; ++target;

   371       ++source;

   372       e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1;

   373     }

   375   };

   377   /// \addtogroup graphs

   378   /// @{

   381   /// \todo UndirFullGraph from the UndirFullGraphBase

   384   /// @}

   386 } //namespace lemon

   389 #endif //LEMON_FULL_GRAPH_H

author	athos
	Fri, 15 Jul 2005 16:01:55 +0000
changeset 1560	01707a8a4ca6
parent 1435	8e85e6bbefdf
child 1566	12a3101cf3ab
permissions	-rw-r--r--