COIN-OR::LEMON - Graph Library

Changeset 2116:b6a68c15a6a3 in lemon-0.x for lemon/full_graph.h


Ignore:
Timestamp:
06/30/06 14:15:45 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2822
Message:

Revert splitted files

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/full_graph.h

    r2115 r2116  
    2222#include <cmath>
    2323
     24#include <lemon/bits/base_extender.h>
    2425#include <lemon/bits/graph_extender.h>
    2526
     
    3031///\ingroup graphs
    3132///\file
    32 ///\brief FullGraph class.
     33///\brief FullGraph and FullUGraph classes.
    3334
    3435
     
    247248  };
    248249
     250
     251  /// \brief Base of the FullUGrpah.
     252  ///
     253  /// Base of the FullUGrpah.
     254  class FullUGraphBase {
     255    int _nodeNum;
     256    int _edgeNum;
     257  public:
     258
     259    typedef FullUGraphBase Graph;
     260
     261    class Node;
     262    class Edge;
     263
     264  public:
     265
     266    FullUGraphBase() {}
     267
     268
     269    ///Creates a full graph with \c n nodes.
     270    void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
     271
     272    /// \brief Returns the node with the given index.
     273    ///
     274    /// Returns the node with the given index. Because it is a
     275    /// static size graph the node's of the graph can be indiced
     276    /// by the range from 0 to \e nodeNum()-1 and the index of
     277    /// the node can accessed by the \e index() member.
     278    Node operator()(int index) const { return Node(index); }
     279
     280    /// \brief Returns the index of the node.
     281    ///
     282    /// Returns the index of the node. Because it is a
     283    /// static size graph the node's of the graph can be indiced
     284    /// by the range from 0 to \e nodeNum()-1 and the index of
     285    /// the node can accessed by the \e index() member.
     286    int index(const Node& node) const { return node.id; }
     287
     288    typedef True NodeNumTag;
     289    typedef True EdgeNumTag;
     290
     291    ///Number of nodes.
     292    int nodeNum() const { return _nodeNum; }
     293    ///Number of edges.
     294    int edgeNum() const { return _edgeNum; }
     295
     296    /// Maximum node ID.
     297   
     298    /// Maximum node ID.
     299    ///\sa id(Node)
     300    int maxNodeId() const { return _nodeNum-1; }
     301    /// Maximum edge ID.
     302   
     303    /// Maximum edge ID.
     304    ///\sa id(Edge)
     305    int maxEdgeId() const { return _edgeNum-1; }
     306
     307    /// \brief Returns the node from its \c id.
     308    ///
     309    /// Returns the node from its \c id. If there is not node
     310    /// with the given id the effect of the function is undefinied.
     311    static Node nodeFromId(int id) { return Node(id);}
     312
     313    /// \brief Returns the edge from its \c id.
     314    ///
     315    /// Returns the edge from its \c id. If there is not edge
     316    /// with the given id the effect of the function is undefinied.
     317    static Edge edgeFromId(int id) { return Edge(id);}
     318
     319    Node source(Edge e) const {
     320      /// \todo we may do it faster
     321      return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
     322    }
     323
     324    Node target(Edge e) const {
     325      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
     326      return Node(e.id - (source) * (source - 1) / 2);
     327    }
     328
     329
     330    /// \brief Node ID.
     331    ///
     332    /// The ID of a valid Node is a nonnegative integer not greater than
     333    /// \ref maxNodeId(). The range of the ID's is not surely continuous
     334    /// and the greatest node ID can be actually less then \ref maxNodeId().
     335    ///
     336    /// The ID of the \ref INVALID node is -1.
     337    /// \return The ID of the node \c v.
     338
     339    static int id(Node v) { return v.id; }
     340
     341    /// \brief Edge ID.
     342    ///
     343    /// The ID of a valid Edge is a nonnegative integer not greater than
     344    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
     345    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
     346    ///
     347    /// The ID of the \ref INVALID edge is -1.
     348    ///\return The ID of the edge \c e.
     349    static int id(Edge e) { return e.id; }
     350
     351    /// \brief Finds an edge between two nodes.
     352    ///
     353    /// Finds an edge from node \c u to node \c v.
     354    ///
     355    /// If \c prev is \ref INVALID (this is the default value), then
     356    /// It finds the first edge from \c u to \c v. Otherwise it looks for
     357    /// the next edge from \c u to \c v after \c prev.
     358    /// \return The found edge or INVALID if there is no such an edge.
     359    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
     360      if (prev.id != -1 || u.id <= v.id) return Edge(-1);
     361      return Edge(u.id * (u.id - 1) / 2 + v.id);
     362    }
     363
     364    typedef True FindEdgeTag;
     365   
     366     
     367    class Node {
     368      friend class FullUGraphBase;
     369
     370    protected:
     371      int id;
     372      Node(int _id) { id = _id;}
     373    public:
     374      Node() {}
     375      Node (Invalid) { id = -1; }
     376      bool operator==(const Node node) const {return id == node.id;}
     377      bool operator!=(const Node node) const {return id != node.id;}
     378      bool operator<(const Node node) const {return id < node.id;}
     379    };
     380   
     381
     382
     383    class Edge {
     384      friend class FullUGraphBase;
     385     
     386    protected:
     387      int id;  // _nodeNum * target + source;
     388
     389      Edge(int _id) : id(_id) {}
     390
     391    public:
     392      Edge() { }
     393      Edge (Invalid) { id = -1; }
     394      bool operator==(const Edge edge) const {return id == edge.id;}
     395      bool operator!=(const Edge edge) const {return id != edge.id;}
     396      bool operator<(const Edge edge) const {return id < edge.id;}
     397    };
     398
     399    void first(Node& node) const {
     400      node.id = _nodeNum - 1;
     401    }
     402
     403    static void next(Node& node) {
     404      --node.id;
     405    }
     406
     407    void first(Edge& edge) const {
     408      edge.id = _edgeNum - 1;
     409    }
     410
     411    static void next(Edge& edge) {
     412      --edge.id;
     413    }
     414
     415    void firstOut(Edge& edge, const Node& node) const {     
     416      int src = node.id;
     417      int trg = 0;
     418      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
     419    }
     420
     421    /// \todo with specialized iterators we can make faster iterating
     422    void nextOut(Edge& edge) const {
     423      int src = source(edge).id;
     424      int trg = target(edge).id;
     425      ++trg;
     426      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
     427    }
     428
     429    void firstIn(Edge& edge, const Node& node) const {
     430      int src = node.id + 1;
     431      int trg = node.id;
     432      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
     433    }
     434   
     435    void nextIn(Edge& edge) const {
     436      int src = source(edge).id;
     437      int trg = target(edge).id;
     438      ++src;
     439      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
     440    }
     441
     442  };
     443
     444  typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >
     445  ExtendedFullUGraphBase;
     446
     447  /// \ingroup graphs
     448  ///
     449  /// \brief An undirected full graph class.
     450  ///
     451  /// This is a simple and fast undirected full graph implementation.
     452  /// It is completely static, so you can neither add nor delete either
     453  /// edges or nodes.
     454  ///
     455  /// The main difference beetween the \e FullGraph and \e FullUGraph class
     456  /// is that this class conforms to the undirected graph concept and
     457  /// it does not contain the loop edges.
     458  ///
     459  /// \sa FullUGraphBase
     460  /// \sa FullGraph
     461  ///
     462  /// \author Balazs Dezso
     463  class FullUGraph : public ExtendedFullUGraphBase {
     464  public:
     465
     466    typedef ExtendedFullUGraphBase Parent;
     467
     468    /// \brief Constructor
     469    FullUGraph() { construct(0); }
     470
     471    /// \brief Constructor
     472    FullUGraph(int n) { construct(n); }
     473
     474    /// \brief Resize the graph
     475    ///
     476    /// Resize the graph. The function will fully destroy and build the graph.
     477    /// This cause that the maps of the graph will reallocated
     478    /// automatically and the previous values will be lost.
     479    void resize(int n) {
     480      Parent::getNotifier(Edge()).clear();
     481      Parent::getNotifier(UEdge()).clear();
     482      Parent::getNotifier(Node()).clear();
     483      construct(n);
     484      Parent::getNotifier(Node()).build();
     485      Parent::getNotifier(UEdge()).build();
     486      Parent::getNotifier(Edge()).build();
     487    }
     488  };
     489
     490
     491  class FullBpUGraphBase {
     492  protected:
     493
     494    int _aNodeNum;
     495    int _bNodeNum;
     496
     497    int _edgeNum;
     498
     499  public:
     500
     501    class NodeSetError : public LogicError {
     502      virtual const char* exceptionName() const {
     503        return "lemon::FullBpUGraph::NodeSetError";
     504      }
     505    };
     506 
     507    class Node {
     508      friend class FullBpUGraphBase;
     509    protected:
     510      int id;
     511
     512      Node(int _id) : id(_id) {}
     513    public:
     514      Node() {}
     515      Node(Invalid) { id = -1; }
     516      bool operator==(const Node i) const {return id==i.id;}
     517      bool operator!=(const Node i) const {return id!=i.id;}
     518      bool operator<(const Node i) const {return id<i.id;}
     519    };
     520
     521    class UEdge {
     522      friend class FullBpUGraphBase;
     523    protected:
     524      int id;
     525
     526      UEdge(int _id) { id = _id;}
     527    public:
     528      UEdge() {}
     529      UEdge (Invalid) { id = -1; }
     530      bool operator==(const UEdge i) const {return id==i.id;}
     531      bool operator!=(const UEdge i) const {return id!=i.id;}
     532      bool operator<(const UEdge i) const {return id<i.id;}
     533    };
     534
     535    void construct(int aNodeNum, int bNodeNum) {
     536      _aNodeNum = aNodeNum;
     537      _bNodeNum = bNodeNum;
     538      _edgeNum = aNodeNum * bNodeNum;
     539    }
     540
     541    void firstANode(Node& node) const {
     542      node.id = 2 * _aNodeNum - 2;
     543      if (node.id < 0) node.id = -1;
     544    }
     545    void nextANode(Node& node) const {
     546      node.id -= 2;
     547      if (node.id < 0) node.id = -1;
     548    }
     549
     550    void firstBNode(Node& node) const {
     551      node.id = 2 * _bNodeNum - 1;
     552    }
     553    void nextBNode(Node& node) const {
     554      node.id -= 2;
     555    }
     556
     557    void first(Node& node) const {
     558      if (_aNodeNum > 0) {
     559        node.id = 2 * _aNodeNum - 2;
     560      } else {
     561        node.id = 2 * _bNodeNum - 1;
     562      }
     563    }
     564    void next(Node& node) const {
     565      node.id -= 2;
     566      if (node.id == -2) {
     567        node.id = 2 * _bNodeNum - 1;
     568      }
     569    }
     570 
     571    void first(UEdge& edge) const {
     572      edge.id = _edgeNum - 1;
     573    }
     574    void next(UEdge& edge) const {
     575      --edge.id;
     576    }
     577
     578    void firstFromANode(UEdge& edge, const Node& node) const {
     579      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
     580      edge.id = (node.id >> 1) * _bNodeNum;
     581    }
     582    void nextFromANode(UEdge& edge) const {
     583      ++(edge.id);
     584      if (edge.id % _bNodeNum == 0) edge.id = -1;
     585    }
     586
     587    void firstFromBNode(UEdge& edge, const Node& node) const {
     588      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
     589      edge.id = (node.id >> 1);
     590    }
     591    void nextFromBNode(UEdge& edge) const {
     592      edge.id += _bNodeNum;
     593      if (edge.id >= _edgeNum) edge.id = -1;
     594    }
     595
     596    static int id(const Node& node) {
     597      return node.id;
     598    }
     599    static Node nodeFromId(int id) {
     600      return Node(id);
     601    }
     602    int maxNodeId() const {
     603      return _aNodeNum > _bNodeNum ?
     604        _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
     605    }
     606 
     607    static int id(const UEdge& edge) {
     608      return edge.id;
     609    }
     610    static UEdge uEdgeFromId(int id) {
     611      return UEdge(id);
     612    }
     613    int maxUEdgeId() const {
     614      return _edgeNum - 1;
     615    }
     616 
     617    static int aNodeId(const Node& node) {
     618      return node.id >> 1;
     619    }
     620    static Node fromANodeId(int id) {
     621      return Node(id << 1);
     622    }
     623    int maxANodeId() const {
     624      return _aNodeNum;
     625    }
     626
     627    static int bNodeId(const Node& node) {
     628      return node.id >> 1;
     629    }
     630    static Node fromBNodeId(int id) {
     631      return Node((id << 1) + 1);
     632    }
     633    int maxBNodeId() const {
     634      return _bNodeNum;
     635    }
     636
     637    Node aNode(const UEdge& edge) const {
     638      return Node((edge.id / _bNodeNum) << 1);
     639    }
     640    Node bNode(const UEdge& edge) const {
     641      return Node(((edge.id % _bNodeNum) << 1) + 1);
     642    }
     643
     644    static bool aNode(const Node& node) {
     645      return (node.id & 1) == 0;
     646    }
     647
     648    static bool bNode(const Node& node) {
     649      return (node.id & 1) == 1;
     650    }
     651
     652    static Node aNode(int index) {
     653      return Node(index << 1);
     654    }
     655
     656    static Node bNode(int index) {
     657      return Node((index << 1) + 1);
     658    }
     659
     660    typedef True NodeNumTag;
     661    int nodeNum() const { return _aNodeNum + _bNodeNum; }
     662    int aNodeNum() const { return _aNodeNum; }
     663    int bNodeNum() const { return _bNodeNum; }
     664
     665    typedef True EdgeNumTag;
     666    int uEdgeNum() const { return _edgeNum; }
     667
     668  };
     669
     670
     671  typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
     672
     673
     674  /// \ingroup graphs
     675  ///
     676  /// \brief An undirected full bipartite graph class.
     677  ///
     678  /// This is a simple and fast bipartite undirected full graph implementation.
     679  /// It is completely static, so you can neither add nor delete either
     680  /// edges or nodes.
     681  ///
     682  /// \sa FullUGraphBase
     683  /// \sa FullGraph
     684  ///
     685  /// \author Balazs Dezso
     686  class FullBpUGraph :
     687    public ExtendedFullBpUGraphBase {
     688  public:
     689
     690    typedef ExtendedFullBpUGraphBase Parent;
     691
     692    FullBpUGraph() {
     693      Parent::construct(0, 0);
     694    }
     695
     696    FullBpUGraph(int aNodeNum, int bNodeNum) {
     697      Parent::construct(aNodeNum, bNodeNum);
     698    }
     699
     700    /// \brief Resize the graph
     701    ///
     702    void resize(int n, int m) {
     703      Parent::getNotifier(Edge()).clear();
     704      Parent::getNotifier(UEdge()).clear();
     705      Parent::getNotifier(Node()).clear();
     706      Parent::getNotifier(ANode()).clear();
     707      Parent::getNotifier(BNode()).clear();
     708      construct(n, m);
     709      Parent::getNotifier(ANode()).build();
     710      Parent::getNotifier(BNode()).build();
     711      Parent::getNotifier(Node()).build();
     712      Parent::getNotifier(UEdge()).build();
     713      Parent::getNotifier(Edge()).build();
     714    }
     715  };
     716
    249717} //namespace lemon
    250718
Note: See TracChangeset for help on using the changeset viewer.