COIN-OR::LEMON - Graph Library

Changeset 983:3095ff2b5c18 in lemon-0.x


Ignore:
Timestamp:
11/11/04 12:12:42 (15 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1371
Message:

UndirFullGraphBase? is added
It is a graph base which contains only one way directed edges in a full graph.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/full_graph.h

    r980 r983  
    1818#define LEMON_FULL_GRAPH_H
    1919
     20#include <cmath>
     21
    2022
    2123#include <lemon/iterable_graph_extender.h>
     
    198200  ///the \ref concept::StaticGraph "StaticGraph" concept
    199201  ///\sa concept::StaticGraph.
    200   ///\todo What about loops?
    201   ///\todo Don't we need SymEdgeMap?
    202202  ///
    203203  ///\author Alpar Juttner
     
    208208  };
    209209
     210
     211  /// Base graph class for UndirFullGraph.
     212
     213  class UndirFullGraphBase {
     214    int NodeNum;
     215    int EdgeNum;
     216  public:
     217
     218    typedef FullGraphBase Graph;
     219
     220    class Node;
     221    class Edge;
     222
     223  public:
     224
     225    FullGraphBase() {}
     226
     227
     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) { }
     233   
     234    typedef True NodeNumTag;
     235    typedef True EdgeNumTag;
     236
     237    ///Number of nodes.
     238    int nodeNum() const { return NodeNum; }
     239    ///Number of edges.
     240    int edgeNum() const { return EdgeNum; }
     241
     242    /// Maximum node ID.
     243   
     244    /// Maximum node ID.
     245    ///\sa id(Node)
     246    int maxId(Node = INVALID) const { return NodeNum-1; }
     247    /// Maximum edge ID.
     248   
     249    /// Maximum edge ID.
     250    ///\sa id(Edge)
     251    int maxId(Edge = INVALID) const { return EdgeNum-1; }
     252
     253    Node tail(Edge e) const {
     254      /// \todo we may do it faster
     255      return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;
     256    }
     257
     258    Node head(Edge e) const {
     259      int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
     260      return e.id - (tail) * (tail - 1) / 2;
     261    }
     262
     263
     264    /// Node ID.
     265   
     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.
     272
     273    static int id(Node v) { return v.id; }
     274    /// Edge ID.
     275   
     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; }
     283
     284    /// Finds an edge between two nodes.
     285   
     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    }
     296   
     297     
     298    class Node {
     299      friend class FullGraphBase;
     300
     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    };
     311   
     312
     313
     314    class Edge {
     315      friend class FullGraphBase;
     316     
     317    protected:
     318      int id;  // NodeNum * head + tail;
     319
     320      Edge(int _id) : id(_id) {}
     321
     322      Edge(const FullGraphBase& _graph, int tail, int head)
     323        : id(_graph.NodeNum * head+tail) {}
     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    };
     331
     332    void first(Node& node) const {
     333      node.id = NodeNum-1;
     334    }
     335
     336    static void next(Node& node) {
     337      --node.id;
     338    }
     339
     340    void first(Edge& edge) const {
     341      edge.id = EdgeNum-1;
     342    }
     343
     344    static void next(Edge& edge) {
     345      --edge.id;
     346    }
     347
     348    void firstOut(Edge& edge, const Node& node) const {     
     349      edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1;
     350    }
     351
     352    /// \todo with specialized iterators we can make faster iterating
     353    void nextOut(Edge& edge) const {
     354      int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
     355      int head = e.id - (tail) * (tail - 1) / 2;
     356      ++head;
     357      return head < tail ? tail * (tail - 1) / 2 + head : -1;
     358    }
     359
     360    void firstIn(Edge& edge, const Node& node) const {
     361      edge.id = node.id * (node.id + 1) / 2 - 1;
     362    }
     363   
     364    void nextIn(Edge& edge) const {
     365      int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
     366      int head = e.id - (tail) * (tail - 1) / 2; ++head;
     367      ++tail;
     368      return tail < nodeNum ? tail * (tail - 1) / 2 + head : -1;
     369    }
     370
     371  };
     372
     373  /// \todo UndirFullGraph from the UndirFullGraphBase
     374
     375 
     376
    210377  /// @} 
    211378
Note: See TracChangeset for help on using the changeset viewer.