COIN-OR::LEMON - Graph Library

Changeset 1188:5ef0ab7b61cd in lemon


Ignore:
Timestamp:
11/14/10 22:48:32 (9 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

FullBpGraph? implementation (#69)

Files:
5 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/graph_extender.h

    r1187 r1188  
    842842    }
    843843
     844    Node u(Edge e) const { return this->redNode(e); }
     845    Node v(Edge e) const { return this->blueNode(e); }
     846
    844847    Node oppositeNode(const Node &n, const Edge &e) const {
    845       if( n == Parent::u(e))
    846         return Parent::v(e);
    847       else if( n == Parent::v(e))
    848         return Parent::u(e);
     848      if( n == u(e))
     849        return v(e);
     850      else if( n == v(e))
     851        return u(e);
    849852      else
    850853        return INVALID;
     
    857860    using Parent::direct;
    858861    Arc direct(const Edge &edge, const Node &node) const {
    859       return Parent::direct(edge, Parent::u(edge) == node);
     862      return Parent::direct(edge, Parent::redNode(edge) == node);
    860863    }
    861864
  • lemon/core.h

    r1187 r1188  
    165165  typedef BpGraph::RedMap<bool> BoolRedMap;                             \
    166166  typedef BpGraph::RedMap<int> IntRedMap;                               \
    167   typedef BpGraph::RedMap<double> DoubleRedMap                          \
     167  typedef BpGraph::RedMap<double> DoubleRedMap;                         \
    168168  typedef BpGraph::BlueNode BlueNode;                                   \
    169169  typedef BpGraph::BlueIt BlueIt;                                       \
  • lemon/full_graph.h

    r956 r1188  
    622622  };
    623623
     624  class FullBpGraphBase {
     625
     626  protected:
     627
     628    int _red_num, _blue_num;
     629    int _node_num, _edge_num;
     630
     631  public:
     632
     633    typedef FullBpGraphBase Graph;
     634
     635    class Node;
     636    class Arc;
     637    class Edge;
     638
     639    class Node {
     640      friend class FullBpGraphBase;
     641    protected:
     642
     643      int _id;
     644      explicit Node(int id) { _id = id;}
     645
     646    public:
     647      Node() {}
     648      Node (Invalid) { _id = -1; }
     649      bool operator==(const Node& node) const {return _id == node._id;}
     650      bool operator!=(const Node& node) const {return _id != node._id;}
     651      bool operator<(const Node& node) const {return _id < node._id;}
     652    };
     653
     654    class Edge {
     655      friend class FullBpGraphBase;
     656    protected:
     657
     658      int _id;
     659      explicit Edge(int id) { _id = id;}
     660
     661    public:
     662      Edge() {}
     663      Edge (Invalid) { _id = -1; }
     664      bool operator==(const Edge& arc) const {return _id == arc._id;}
     665      bool operator!=(const Edge& arc) const {return _id != arc._id;}
     666      bool operator<(const Edge& arc) const {return _id < arc._id;}
     667    };
     668
     669    class Arc {
     670      friend class FullBpGraphBase;
     671    protected:
     672
     673      int _id;
     674      explicit Arc(int id) { _id = id;}
     675
     676    public:
     677      operator Edge() const {
     678        return _id != -1 ? edgeFromId(_id / 2) : INVALID;
     679      }
     680
     681      Arc() {}
     682      Arc (Invalid) { _id = -1; }
     683      bool operator==(const Arc& arc) const {return _id == arc._id;}
     684      bool operator!=(const Arc& arc) const {return _id != arc._id;}
     685      bool operator<(const Arc& arc) const {return _id < arc._id;}
     686    };
     687
     688
     689  protected:
     690
     691    FullBpGraphBase()
     692      : _red_num(0), _blue_num(0), _node_num(0), _edge_num(0) {}
     693
     694    void construct(int redNum, int blueNum) {
     695      _red_num = redNum; _blue_num = blueNum;
     696      _node_num = redNum + blueNum; _edge_num = redNum * blueNum;
     697    }
     698
     699  public:
     700
     701    typedef True NodeNumTag;
     702    typedef True EdgeNumTag;
     703    typedef True ArcNumTag;
     704
     705    int nodeNum() const { return _node_num; }
     706    int redNum() const { return _red_num; }
     707    int blueNum() const { return _blue_num; }
     708    int edgeNum() const { return _edge_num; }
     709    int arcNum() const { return 2 * _edge_num; }
     710
     711    int maxNodeId() const { return _node_num - 1; }
     712    int maxRedId() const { return _red_num - 1; }
     713    int maxBlueId() const { return _blue_num - 1; }
     714    int maxEdgeId() const { return _edge_num - 1; }
     715    int maxArcId() const { return 2 * _edge_num - 1; }
     716
     717    bool red(Node n) const { return n._id < _red_num; }
     718    bool blue(Node n) const { return n._id >= _red_num; }
     719
     720    Node source(Arc a) const {
     721      if (a._id & 1) {
     722        return Node((a._id >> 1) % _red_num);
     723      } else {
     724        return Node((a._id >> 1) / _red_num + _red_num);
     725      }
     726    }
     727    Node target(Arc a) const {
     728      if (a._id & 1) {
     729        return Node((a._id >> 1) / _red_num + _red_num);
     730      } else {
     731        return Node((a._id >> 1) % _red_num);
     732      }
     733    }
     734
     735    Node redNode(Edge e) const {
     736      return Node(e._id % _red_num);
     737    }
     738    Node blueNode(Edge e) const {
     739      return Node(e._id / _red_num + _red_num);
     740    }
     741
     742    static bool direction(Arc a) {
     743      return (a._id & 1) == 1;
     744    }
     745
     746    static Arc direct(Edge e, bool d) {
     747      return Arc(e._id * 2 + (d ? 1 : 0));
     748    }
     749
     750    void first(Node& node) const {
     751      node._id = _node_num - 1;
     752    }
     753
     754    static void next(Node& node) {
     755      --node._id;
     756    }
     757
     758    void firstRed(Node& node) const {
     759      node._id = _red_num - 1;
     760    }
     761
     762    static void nextRed(Node& node) {
     763      --node._id;
     764    }
     765
     766    void firstBlue(Node& node) const {
     767      if (_red_num == _node_num) node._id = -1;
     768      else node._id = _node_num - 1;
     769    }
     770
     771    void nextBlue(Node& node) const {
     772      if (node._id == _red_num) node._id = -1;
     773      else --node._id;
     774    }
     775
     776    void first(Arc& arc) const {
     777      arc._id = 2 * _edge_num - 1;
     778    }
     779
     780    static void next(Arc& arc) {
     781      --arc._id;
     782    }
     783
     784    void first(Edge& arc) const {
     785      arc._id = _edge_num - 1;
     786    }
     787
     788    static void next(Edge& arc) {
     789      --arc._id;
     790    }
     791
     792    void firstOut(Arc &a, const Node& v) const {
     793      if (v._id < _red_num) {
     794        a._id = 2 * (v._id + _red_num * (_blue_num - 1)) + 1;
     795      } else {
     796        a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num));
     797      }
     798    }
     799    void nextOut(Arc &a) const {
     800      if (a._id & 1) {
     801        a._id -= 2 * _red_num;
     802        if (a._id < 0) a._id = -1;
     803      } else {
     804        if (a._id % (2 * _red_num) == 0) a._id = -1;
     805        else a._id -= 2;
     806      }
     807    }
     808
     809    void firstIn(Arc &a, const Node& v) const {
     810      if (v._id < _red_num) {
     811        a._id = 2 * (v._id + _red_num * (_blue_num - 1));
     812      } else {
     813        a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num)) + 1;
     814      }
     815    }
     816    void nextIn(Arc &a) const {
     817      if (a._id & 1) {
     818        if (a._id % (2 * _red_num) == 1) a._id = -1;
     819        else a._id -= 2;
     820      } else {
     821        a._id -= 2 * _red_num;
     822        if (a._id < 0) a._id = -1;
     823      }
     824    }
     825
     826    void firstInc(Edge &e, bool& d, const Node& v) const {
     827      if (v._id < _red_num) {
     828        d = true;
     829        e._id = v._id + _red_num * (_blue_num - 1);
     830      } else {
     831        d = false;
     832        e._id = _red_num - 1 + _red_num * (v._id - _red_num);
     833      }
     834    }
     835    void nextInc(Edge &e, bool& d) const {
     836      if (d) {
     837        e._id -= _red_num;
     838        if (e._id < 0) e._id = -1;
     839      } else {
     840        if (e._id % _red_num == 0) e._id = -1;
     841        else --e._id;
     842      }
     843    }
     844
     845    static int id(Node v) { return v._id; }
     846    int redId(Node v) const {
     847      LEMON_DEBUG(v._id < _red_num, "Node has to be red");
     848      return v._id;
     849    }
     850    int blueId(Node v) const {
     851      LEMON_DEBUG(v._id >= _red_num, "Node has to be blue");
     852      return v._id - _red_num;
     853    }
     854    static int id(Arc e) { return e._id; }
     855    static int id(Edge e) { return e._id; }
     856   
     857    static Node nodeFromId(int id) { return Node(id);}
     858    static Arc arcFromId(int id) { return Arc(id);}
     859    static Edge edgeFromId(int id) { return Edge(id);}
     860
     861    bool valid(Node n) const {
     862      return n._id >= 0 && n._id < _node_num;
     863    }
     864    bool valid(Arc a) const {
     865      return a._id >= 0 && a._id < 2 * _edge_num;
     866    }
     867    bool valid(Edge e) const {
     868      return e._id >= 0 && e._id < _edge_num;
     869    }
     870
     871    Node redNode(int index) const {
     872      return Node(index);
     873    }
     874
     875    int redIndex(Node n) const {
     876      return n._id;
     877    }
     878
     879    Node blueNode(int index) const {
     880      return Node(index + _red_num);
     881    }
     882
     883    int blueIndex(Node n) const {
     884      return n._id - _red_num;
     885    }
     886       
     887    void clear() {
     888      _red_num = 0; _blue_num = 0;
     889      _node_num = 0; _edge_num = 0;
     890    }
     891
     892    Edge edge(const Node& u, const Node& v) const {
     893      if (u._id < _red_num) {
     894        if (v._id < _red_num) {
     895          return Edge(-1);
     896        } else {
     897          return Edge(u._id + _red_num * (v._id - _red_num));
     898        }
     899      } else {
     900        if (v._id < _red_num) {
     901          return Edge(v._id + _red_num * (u._id - _red_num));
     902        } else {
     903          return Edge(-1);
     904        }
     905      }
     906    }
     907
     908    Arc arc(const Node& u, const Node& v) const {
     909      if (u._id < _red_num) {
     910        if (v._id < _red_num) {
     911          return Arc(-1);
     912        } else {
     913          return Arc(2 * (u._id + _red_num * (v._id - _red_num)) + 1);
     914        }
     915      } else {
     916        if (v._id < _red_num) {
     917          return Arc(2 * (v._id + _red_num * (u._id - _red_num)));
     918        } else {
     919          return Arc(-1);
     920        }
     921      }
     922    }
     923
     924    typedef True FindEdgeTag;
     925    typedef True FindArcTag;
     926
     927    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
     928      return prev != INVALID ? INVALID : edge(u, v);
     929    }
     930
     931    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
     932      return prev != INVALID ? INVALID : arc(s, t);
     933    }
     934
     935  };
     936
     937  typedef BpGraphExtender<FullBpGraphBase> ExtendedFullBpGraphBase;
     938
     939  /// \ingroup graphs
     940  ///
     941  /// \brief An undirected full bipartite graph class.
     942  ///
     943  /// FullBpGraph is a simple and fast implmenetation of undirected
     944  /// full bipartite graphs. It contains an edge between every
     945  /// red-blue pairs of nodes, therefore the number of edges is
     946  /// <tt>nr*nb</tt>.  This class is completely static and it needs
     947  /// constant memory space.  Thus you can neither add nor delete
     948  /// nodes or edges, however the structure can be resized using
     949  /// resize().
     950  ///
     951  /// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept".
     952  /// Most of its member functions and nested classes are documented
     953  /// only in the concept class.
     954  ///
     955  /// This class provides constant time counting for nodes, edges and arcs.
     956  ///
     957  /// \sa FullGraph
     958  class FullBpGraph : public ExtendedFullBpGraphBase {
     959  public:
     960
     961    typedef ExtendedFullBpGraphBase Parent;
     962
     963    /// \brief Default constructor.
     964    ///
     965    /// Default constructor. The number of nodes and edges will be zero.
     966    FullBpGraph() { construct(0, 0); }
     967
     968    /// \brief Constructor
     969    ///
     970    /// Constructor.
     971    /// \param redNum The number of the red nodes.
     972    /// \param blueNum The number of the blue nodes.
     973    FullBpGraph(int redNum, int blueNum) { construct(redNum, blueNum); }
     974
     975    /// \brief Resizes the graph
     976    ///
     977    /// This function resizes the graph. It fully destroys and
     978    /// rebuilds the structure, therefore the maps of the graph will be
     979    /// reallocated automatically and the previous values will be lost.
     980    void resize(int redNum, int blueNum) {
     981      Parent::notifier(Arc()).clear();
     982      Parent::notifier(Edge()).clear();
     983      Parent::notifier(Node()).clear();
     984      Parent::notifier(BlueNode()).clear();
     985      Parent::notifier(RedNode()).clear();
     986      construct(redNum, blueNum);
     987      Parent::notifier(RedNode()).build();
     988      Parent::notifier(BlueNode()).build();
     989      Parent::notifier(Node()).build();
     990      Parent::notifier(Edge()).build();
     991      Parent::notifier(Arc()).build();
     992    }
     993
     994    /// \brief Returns the red node with the given index.
     995    ///
     996    /// Returns the red node with the given index. Since this
     997    /// structure is completely static, the red nodes can be indexed
     998    /// with integers from the range <tt>[0..redNum()-1]</tt>.
     999    /// \sa redIndex()
     1000    Node redNode(int index) const { return Parent::redNode(index); }
     1001
     1002    /// \brief Returns the index of the given red node.
     1003    ///
     1004    /// Returns the index of the given red node. Since this structure
     1005    /// is completely static, the red nodes can be indexed with
     1006    /// integers from the range <tt>[0..redNum()-1]</tt>.
     1007    ///
     1008    /// \sa operator()()
     1009    int redIndex(Node node) const { return Parent::redIndex(node); }
     1010
     1011    /// \brief Returns the blue node with the given index.
     1012    ///
     1013    /// Returns the blue node with the given index. Since this
     1014    /// structure is completely static, the blue nodes can be indexed
     1015    /// with integers from the range <tt>[0..blueNum()-1]</tt>.
     1016    /// \sa blueIndex()
     1017    Node blueNode(int index) const { return Parent::blueNode(index); }
     1018
     1019    /// \brief Returns the index of the given blue node.
     1020    ///
     1021    /// Returns the index of the given blue node. Since this structure
     1022    /// is completely static, the blue nodes can be indexed with
     1023    /// integers from the range <tt>[0..blueNum()-1]</tt>.
     1024    ///
     1025    /// \sa operator()()
     1026    int blueIndex(Node node) const { return Parent::blueIndex(node); }
     1027
     1028    /// \brief Returns the edge which connects the given nodes.
     1029    ///
     1030    /// Returns the edge which connects the given nodes.
     1031    Edge edge(const Node& u, const Node& v) const {
     1032      return Parent::edge(u, v);
     1033    }
     1034
     1035    /// \brief Returns the arc which connects the given nodes.
     1036    ///
     1037    /// Returns the arc which connects the given nodes.
     1038    Arc arc(const Node& u, const Node& v) const {
     1039      return Parent::arc(u, v);
     1040    }
     1041
     1042    /// \brief Number of nodes.
     1043    int nodeNum() const { return Parent::nodeNum(); }
     1044    /// \brief Number of red nodes.
     1045    int redNum() const { return Parent::redNum(); }
     1046    /// \brief Number of blue nodes.
     1047    int blueNum() const { return Parent::blueNum(); }
     1048    /// \brief Number of arcs.
     1049    int arcNum() const { return Parent::arcNum(); }
     1050    /// \brief Number of edges.
     1051    int edgeNum() const { return Parent::edgeNum(); }
     1052  };
     1053
    6241054
    6251055} //namespace lemon
  • lemon/smart_graph.h

    r1187 r1188  
    926926    Node blueNode(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
    927927
    928     Node u(Edge e) const { return redNode(e); }
    929     Node v(Edge e) const { return blueNode(e); }
    930 
    931928    static bool direction(Arc a) {
    932929      return (a._id & 1) == 1;
     
    11021099  /// \ingroup graphs
    11031100  ///
    1104   /// \brief A smart undirected graph class.
    1105   ///
    1106   /// \ref SmartBpGraph is a simple and fast graph implementation.
     1101  /// \brief A smart undirected bipartite graph class.
     1102  ///
     1103  /// \ref SmartBpGraph is a simple and fast bipartite graph implementation.
    11071104  /// It is also quite memory efficient but at the price
    11081105  /// that it does not support node and edge deletion
    11091106  /// (except for the Snapshot feature).
    11101107  ///
    1111   /// This type fully conforms to the \ref concepts::Graph "Graph concept"
     1108  /// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
    11121109  /// and it also provides some additional functionalities.
    11131110  /// Most of its member functions and nested classes are documented
     
    11161113  /// This class provides constant time counting for nodes, edges and arcs.
    11171114  ///
    1118   /// \sa concepts::Graph
    1119   /// \sa SmartDigraph
     1115  /// \sa concepts::BpGraph
     1116  /// \sa SmartGraph
    11201117  class SmartBpGraph : public ExtendedSmartBpGraphBase {
    11211118    typedef ExtendedSmartBpGraphBase Parent;
  • test/bpgraph_test.cc

    r1187 r1188  
    2020//#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 //#include <lemon/full_graph.h>
     22#include <lemon/full_graph.h>
    2323
    2424#include "test_tools.h"
     
    251251}
    252252
     253void checkFullBpGraph(int redNum, int blueNum) {
     254  typedef FullBpGraph BpGraph;
     255  BPGRAPH_TYPEDEFS(BpGraph);
     256
     257  BpGraph G(redNum, blueNum);
     258  checkGraphNodeList(G, redNum + blueNum);
     259  checkGraphRedNodeList(G, redNum);
     260  checkGraphBlueNodeList(G, blueNum);
     261  checkGraphEdgeList(G, redNum * blueNum);
     262  checkGraphArcList(G, 2 * redNum * blueNum);
     263
     264  G.resize(redNum, blueNum);
     265  checkGraphNodeList(G, redNum + blueNum);
     266  checkGraphRedNodeList(G, redNum);
     267  checkGraphBlueNodeList(G, blueNum);
     268  checkGraphEdgeList(G, redNum * blueNum);
     269  checkGraphArcList(G, 2 * redNum * blueNum);
     270
     271  for (RedIt n(G); n != INVALID; ++n) {
     272    checkGraphOutArcList(G, n, blueNum);
     273    checkGraphInArcList(G, n, blueNum);
     274    checkGraphIncEdgeList(G, n, blueNum);
     275  }
     276
     277  for (BlueIt n(G); n != INVALID; ++n) {
     278    checkGraphOutArcList(G, n, redNum);
     279    checkGraphInArcList(G, n, redNum);
     280    checkGraphIncEdgeList(G, n, redNum);
     281  }
     282
     283  checkGraphConArcList(G, 2 * redNum * blueNum);
     284  checkGraphConEdgeList(G, redNum * blueNum);
     285
     286  checkArcDirections(G);
     287
     288  checkNodeIds(G);
     289  checkRedNodeIds(G);
     290  checkBlueNodeIds(G);
     291  checkArcIds(G);
     292  checkEdgeIds(G);
     293
     294  checkGraphNodeMap(G);
     295  checkGraphRedMap(G);
     296  checkGraphBlueMap(G);
     297  checkGraphArcMap(G);
     298  checkGraphEdgeMap(G);
     299
     300  for (int i = 0; i < G.redNum(); ++i) {
     301    check(G.red(G.redNode(i)), "Wrong node");
     302    check(G.redIndex(G.redNode(i)) == i, "Wrong index");
     303  }
     304
     305  for (int i = 0; i < G.blueNum(); ++i) {
     306    check(G.blue(G.blueNode(i)), "Wrong node");
     307    check(G.blueIndex(G.blueNode(i)) == i, "Wrong index");
     308  }
     309
     310  for (NodeIt u(G); u != INVALID; ++u) {
     311    for (NodeIt v(G); v != INVALID; ++v) {
     312      Edge e = G.edge(u, v);
     313      Arc a = G.arc(u, v);
     314      if (G.red(u) == G.red(v)) {
     315        check(e == INVALID, "Wrong edge lookup");
     316        check(a == INVALID, "Wrong arc lookup");
     317      } else {
     318        check((G.u(e) == u && G.v(e) == v) ||
     319              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
     320        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
     321      }
     322    }
     323  }
     324
     325}
     326
    253327void checkGraphs() {
    254328  { // Checking SmartGraph
     
    257331    checkBpGraphValidity<SmartBpGraph>();
    258332  }
     333  { // Checking FullBpGraph
     334    checkFullBpGraph(6, 8);
     335    checkFullBpGraph(7, 4);
     336  }
    259337}
    260338
Note: See TracChangeset for help on using the changeset viewer.