lemon-0.x: src/lemon/full_graph.h@68beae6758a7

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

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

     3  *

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

     5  * (Egervary Combinatorial Optimization Research Group, 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/iterable_graph_extender.h>

    24 #include <lemon/alteration_observer_registry.h>

    25 #include <lemon/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 /// \addtogroup graphs

    39 /// @{

    41   class FullGraphBase {

    42     int NodeNum;

    43     int EdgeNum;

    44   public:

    46     typedef FullGraphBase Graph;

    48     class Node;

    49     class Edge;

    51   public:

    53     FullGraphBase() {}

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

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

    58     ///

    59     //    FullGraphBase(const FullGraphBase &_g)

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

    62     typedef True NodeNumTag;

    63     typedef True EdgeNumTag;

    65     ///Number of nodes.

    66     int nodeNum() const { return NodeNum; }

    67     ///Number of edges.

    68     int edgeNum() const { return EdgeNum; }

    70     /// Maximum node ID.

    72     /// Maximum node ID.

    73     ///\sa id(Node)

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

    75     /// Maximum edge ID.

    77     /// Maximum edge ID.

    78     ///\sa id(Edge)

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

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

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

    85     /// Node ID.

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

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

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

    90     ///

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

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

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

    95     /// Edge ID.

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

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

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

   100     ///

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

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

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

   105     /// Finds an edge between two nodes.

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

   108     ///

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

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

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

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

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

   114     {

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

   116     }

   119     class Node {

   120       friend class FullGraphBase;

   122     protected:

   123       int id;

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

   125     public:

   126       Node() {}

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

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

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

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

   131     };

   135     class Edge {

   136       friend class FullGraphBase;

   138     protected:

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

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

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

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

   145     public:

   146       Edge() { }

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

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

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

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

   151     };

   153     void first(Node& node) const {

   154       node.id = NodeNum-1;

   155     }

   157     static void next(Node& node) {

   158       --node.id;

   159     }

   161     void first(Edge& edge) const {

   162       edge.id = EdgeNum-1;

   163     }

   165     static void next(Edge& edge) {

   166       --edge.id;

   167     }

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

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

   171     }

   173     void nextOut(Edge& edge) const {

   174       edge.id -= NodeNum;

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

   176     }

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

   179       edge.id = node.id * NodeNum;

   180     }

   182     void nextIn(Edge& edge) const {

   183       ++edge.id;

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

   185     }

   187   };

   190   typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;

   191   typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;

   192   typedef DefaultMappableGraphExtender<IterableFullGraphBase> MappableFullGraphBase;

   194   ///A full graph class.

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

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

   198   ///edges or nodes.

   199   ///Thus it conforms to

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

   201   ///\sa concept::StaticGraph.

   202   ///

   203   ///\author Alpar Juttner

   204   class FullGraph : public MappableFullGraphBase {

   205   public:

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

   208   };

   211   /// Base graph class for UndirFullGraph.

   213   class UndirFullGraphBase {

   214     int NodeNum;

   215     int EdgeNum;

   216   public:

   218     typedef UndirFullGraphBase Graph;

   220     class Node;

   221     class Edge;

   223   public:

   225     UndirFullGraphBase() {}

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

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

   230     ///

   231     //    FullGraphBase(const FullGraphBase &_g)

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

   234     typedef True NodeNumTag;

   235     typedef True EdgeNumTag;

   237     ///Number of nodes.

   238     int nodeNum() const { return NodeNum; }

   239     ///Number of edges.

   240     int edgeNum() const { return EdgeNum; }

   242     /// Maximum node ID.

   244     /// Maximum node ID.

   245     ///\sa id(Node)

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

   247     /// Maximum edge ID.

   249     /// Maximum edge ID.

   250     ///\sa id(Edge)

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

   253     Node source(Edge e) const {

   254       /// \todo we may do it faster

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

   256     }

   258     Node target(Edge e) const {

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

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

   261     }

   264     /// Node ID.

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

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

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

   269     ///

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

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

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

   274     /// Edge ID.

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

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

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

   279     ///

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

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

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

   284     /// Finds an edge between two nodes.

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

   287     ///

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

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

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

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

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

   293     {

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

   295     }

   298     class Node {

   299       friend class UndirFullGraphBase;

   301     protected:

   302       int id;

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

   304     public:

   305       Node() {}

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

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

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

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

   310     };

   314     class Edge {

   315       friend class UndirFullGraphBase;

   317     protected:

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

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

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

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

   324     public:

   325       Edge() { }

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

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

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

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

   330     };

   332     void first(Node& node) const {

   333       node.id = NodeNum-1;

   334     }

   336     static void next(Node& node) {

   337       --node.id;

   338     }

   340     void first(Edge& edge) const {

   341       edge.id = EdgeNum-1;

   342     }

   344     static void next(Edge& edge) {

   345       --edge.id;

   346     }

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

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

   350     }

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

   353     void nextOut(Edge& e) const {

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

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

   356       ++target;

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

   358     }

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

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

   362     }

   364     void nextIn(Edge& e) const {

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

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

   367       ++source;

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

   369     }

   371   };

   373   /// \todo UndirFullGraph from the UndirFullGraphBase

   377   /// @}

   379 } //namespace lemon

   382 #endif //LEMON_FULL_GRAPH_H

author	ladanyi
	Mon, 22 Nov 2004 14:39:40 +0000
changeset 1018	68beae6758a7
parent 985	741f3108a90f
child 1039	bd01c5a3f989
permissions	-rw-r--r--