Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/full_graph.h
changeset 2230 67af33b34394
parent 2162 6831fa007688
child 2231 06faf3f06d67
equal deleted inserted replaced
28:9f6b1342f518 29:5b040c975e2c 
    33 ///\brief FullGraph and FullUGraph classes.
 
    33 ///\brief FullGraph and FullUGraph classes.
 
    34 
    34 
    35 
    35 
    36 namespace lemon {
 
    36 namespace lemon {
 
    37 
    37 
    38   /// \brief Base of the FullGrpah.
 
       
    39   ///
 
       
    40   /// Base of the FullGrpah.
 
       
    41   class FullGraphBase {
 
    38   class FullGraphBase {
 
    42     int _nodeNum;
 
    39     int _nodeNum;
 
    43     int _edgeNum;
 
    40     int _edgeNum;
 
    44   public:
 
    41   public:
 
    45 
    42 
    46     typedef FullGraphBase Graph;
 
    43     typedef FullGraphBase Graph;
 
    47 
    44 
    48     class Node;
 
    45     class Node;
 
    49     class Edge;
 
    46     class Edge;
 
    50 
    47 
       
    48   protected:
 
       
    49 
       
    50     FullGraphBase() {}
 
       
    51 
       
    52     void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
 
       
    53 
    51   public:
 
    54   public:
 
    52 
       
    53     FullGraphBase() {}
 
       
    54 
       
    55 
       
    56     ///Creates a full graph with \c n nodes.
 
       
    57     void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
 
       
    58     
    55     
    59     typedef True NodeNumTag;
 
    56     typedef True NodeNumTag;
 
    60     typedef True EdgeNumTag;
 
    57     typedef True EdgeNumTag;
 
    61 
    58 
    62     /// \brief Returns the node with the given index.
 
       
    63     ///
 
       
    64     /// Returns the node with the given index. Because it is a
 
       
    65     /// static size graph the node's of the graph can be indiced
 
       
    66     /// by the range from 0 to \e nodeNum()-1 and the index of
 
       
    67     /// the node can accessed by the \e index() member.
 
       
    68     Node operator()(int index) const { return Node(index); }
 
    59     Node operator()(int index) const { return Node(index); }
 
    69 
       
    70     /// \brief Returns the index of the node.
 
       
    71     ///
 
       
    72     /// Returns the index of the node. Because it is a
 
       
    73     /// static size graph the node's of the graph can be indiced
 
       
    74     /// by the range from 0 to \e nodeNum()-1 and the index of
 
       
    75     /// the node can accessed by the \e index() member.
 
       
    76     int index(const Node& node) const { return node.id; }
 
    60     int index(const Node& node) const { return node.id; }
 
    77 
    61 
    78     ///Number of nodes.
 
    62     Edge edge(const Node& u, const Node& v) const { 
       
    63       return Edge(*this, u.id, v.id); 
       
    64     }
 
       
    65 
    79     int nodeNum() const { return _nodeNum; }
 
    66     int nodeNum() const { return _nodeNum; }
 
    80     ///Number of edges.
 
       
    81     int edgeNum() const { return _edgeNum; }
 
    67     int edgeNum() const { return _edgeNum; }
 
    82 
    68 
    83     /// Maximum node ID.
 
       
    84     
       
    85     /// Maximum node ID.
 
       
    86     ///\sa id(Node)
 
       
    87     int maxNodeId() const { return _nodeNum-1; }
 
    69     int maxNodeId() const { return _nodeNum-1; }
 
    88     /// Maximum edge ID.
 
       
    89     
       
    90     /// Maximum edge ID.
 
       
    91     ///\sa id(Edge)
 
       
    92     int maxEdgeId() const { return _edgeNum-1; }
 
    70     int maxEdgeId() const { return _edgeNum-1; }
 
    93 
    71 
    94     Node source(Edge e) const { return e.id % _nodeNum; }
 
    72     Node source(Edge e) const { return e.id % _nodeNum; }
 
    95     Node target(Edge e) const { return e.id / _nodeNum; }
 
    73     Node target(Edge e) const { return e.id / _nodeNum; }
 
    96 
    74 
    97 
    75 
    98     /// Node ID.
 
       
    99     
       
   100     /// The ID of a valid Node is a nonnegative integer not greater than
 
       
   101     /// \ref maxNodeId(). The range of the ID's is not surely continuous
 
       
   102     /// and the greatest node ID can be actually less then \ref maxNodeId().
 
       
   103     ///
 
       
   104     /// The ID of the \ref INVALID node is -1.
 
       
   105     ///\return The ID of the node \c v. 
       
   106 
       
   107     static int id(Node v) { return v.id; }
 
    76     static int id(Node v) { return v.id; }
 
   108     /// Edge ID.
 
       
   109     
       
   110     /// The ID of a valid Edge is a nonnegative integer not greater than
 
       
   111     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
 
       
   112     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
 
       
   113     ///
 
       
   114     /// The ID of the \ref INVALID edge is -1.
 
       
   115     ///\return The ID of the edge \c e. 
       
   116     static int id(Edge e) { return e.id; }
 
    77     static int id(Edge e) { return e.id; }
 
   117 
    78 
   118     static Node nodeFromId(int id) { return Node(id);}
 
    79     static Node nodeFromId(int id) { return Node(id);}
 
   119     
    80     
   120     static Edge edgeFromId(int id) { return Edge(id);}
 
    81     static Edge edgeFromId(int id) { return Edge(id);}
 
   121 
    82 
   122     typedef True FindEdgeTag;
 
    83     typedef True FindEdgeTag;
 
   123 
    84 
   124     /// Finds an edge between two nodes.
 
       
   125     
       
   126     /// Finds an edge from node \c u to node \c v.
 
       
   127     ///
 
       
   128     /// If \c prev is \ref INVALID (this is the default value), then
 
       
   129     /// It finds the first edge from \c u to \c v. Otherwise it looks for
 
       
   130     /// the next edge from \c u to \c v after \c prev.
 
       
   131     /// \return The found edge or INVALID if there is no such an edge.
 
       
   132     Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
 
    85     Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
 
   133       return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
 
    86       return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
 
   134     }
 
    87     }
 
   135     
    88     
   136       
    89       
   215   /// edges or nodes.
 
   168   /// edges or nodes.
 
   216   /// Thus it conforms to
 
   169   /// Thus it conforms to
 
   217   /// the \ref concept::Graph "Graph" concept
 
   170   /// the \ref concept::Graph "Graph" concept
 
   218   /// \sa concept::Graph.
 
   171   /// \sa concept::Graph.
 
   219   ///
 
   172   ///
 
   220   /// \sa FullGraphBase
 
       
   221   /// \sa FullUGraph
 
   173   /// \sa FullUGraph
 
   222   ///
 
   174   ///
 
   223   /// \author Alpar Juttner
 
   175   /// \author Alpar Juttner
 
   224   class FullGraph : public ExtendedFullGraphBase {
 
   176   class FullGraph : public ExtendedFullGraphBase {
 
   225   public:
 
   177   public:
 
   243       Parent::getNotifier(Node()).clear();
 
   195       Parent::getNotifier(Node()).clear();
 
   244       construct(n);
 
   196       construct(n);
 
   245       Parent::getNotifier(Node()).build();
 
   197       Parent::getNotifier(Node()).build();
 
   246       Parent::getNotifier(Edge()).build();
 
   198       Parent::getNotifier(Edge()).build();
 
   247     }
 
   199     }
 
       
   200 
       
   201     /// \brief Returns the node with the given index.
 
       
   202     ///
 
       
   203     /// Returns the node with the given index. Because it is a
 
       
   204     /// static size graph the node's of the graph can be indiced
 
       
   205     /// by the range from 0 to \e nodeNum()-1 and the index of
 
       
   206     /// the node can accessed by the \e index() member.
 
       
   207     Node operator()(int index) const { return Parent::operator()(index); }
 
       
   208 
       
   209     /// \brief Returns the index of the node.
 
       
   210     ///
 
       
   211     /// Returns the index of the node. Because it is a
 
       
   212     /// static size graph the node's of the graph can be indiced
 
       
   213     /// by the range from 0 to \e nodeNum()-1 and the index of
 
       
   214     /// the node can accessed by the \e index() member.
 
       
   215     int index(const Node& node) const { return Parent::index(node); }
 
       
   216 
       
   217     /// \brief Returns the edge connects the given nodes.
 
       
   218     ///
 
       
   219     /// Returns the edge connects the given nodes.
 
       
   220     Edge edge(const Node& u, const Node& v) const { 
       
   221       return Parent::edge(u, v); 
       
   222     }
 
       
   223 
       
   224     /// \brief Number of nodes.
 
       
   225     int nodeNum() const { return Parent::nodeNum(); }
 
       
   226     /// \brief Number of edges.
 
       
   227     int edgeNum() const { return Parent::edgeNum(); }
 
   248   };
 
   228   };
 
   249 
   229 
   250 
   230 
   251   /// \brief Base of the FullUGrpah.
 
       
   252   ///
 
       
   253   /// Base of the FullUGrpah.
 
       
   254   class FullUGraphBase {
 
   231   class FullUGraphBase {
 
   255     int _nodeNum;
 
   232     int _nodeNum;
 
   256     int _edgeNum;
 
   233     int _edgeNum;
 
   257   public:
 
   234   public:
 
   258 
   235 
   259     typedef FullUGraphBase Graph;
 
   236     typedef FullUGraphBase Graph;
 
   260 
   237 
   261     class Node;
 
   238     class Node;
 
   262     class Edge;
 
   239     class Edge;
 
   263 
   240 
       
   241   protected:
 
       
   242 
       
   243     FullUGraphBase() {}
 
       
   244 
       
   245     void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
 
       
   246 
   264   public:
 
   247   public:
 
   265 
   248 
   266     FullUGraphBase() {}
 
   249 
   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); }
 
   250     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; }
 
   251     int index(const Node& node) const { return node.id; }
 
       
   252 
       
   253     Edge edge(const Node& u, const Node& v) const { 
       
   254       return Edge(u.id * (u.id - 1) / 2 + v.id);
 
       
   255     }
 
   287 
   256 
   288     typedef True NodeNumTag;
 
   257     typedef True NodeNumTag;
 
   289     typedef True EdgeNumTag;
 
   258     typedef True EdgeNumTag;
 
   290 
   259 
   291     ///Number of nodes.
 
       
   292     int nodeNum() const { return _nodeNum; }
 
   260     int nodeNum() const { return _nodeNum; }
 
   293     ///Number of edges.
 
       
   294     int edgeNum() const { return _edgeNum; }
 
   261     int edgeNum() const { return _edgeNum; }
 
   295 
   262 
   296     /// Maximum node ID.
 
       
   297     
       
   298     /// Maximum node ID.
 
       
   299     ///\sa id(Node)
 
       
   300     int maxNodeId() const { return _nodeNum-1; }
 
   263     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; }
 
   264     int maxEdgeId() const { return _edgeNum-1; }
 
   306 
   265 
   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);}
 
   266     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);}
 
   267     static Edge edgeFromId(int id) { return Edge(id);}
 
   318 
   268 
   319     Node source(Edge e) const { 
   269     Node source(Edge e) const { 
   320       /// \todo we may do it faster
 
   270       /// \todo we may do it faster
 
   321       return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
 
   271       return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
 
   324     Node target(Edge e) const { 
   274     Node target(Edge e) const { 
   325       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
 
   275       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
 
   326       return Node(e.id - (source) * (source - 1) / 2);
 
   276       return Node(e.id - (source) * (source - 1) / 2);
 
   327     }
 
   277     }
 
   328 
   278 
   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; }
 
   279     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; }
 
   280     static int id(Edge e) { return e.id; }
 
   350 
   281 
   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 {
 
   282     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
 
   360       if (prev.id != -1 || u.id <= v.id) return Edge(-1);
 
   283       if (prev.id != -1 || u.id <= v.id) return Edge(-1);
 
   361       return Edge(u.id * (u.id - 1) / 2 + v.id);
 
   284       return Edge(u.id * (u.id - 1) / 2 + v.id);
 
   362     }
 
   285     }
 
   363 
   286 
   454   ///
 
   377   ///
 
   455   /// The main difference beetween the \e FullGraph and \e FullUGraph class
 
   378   /// The main difference beetween the \e FullGraph and \e FullUGraph class
 
   456   /// is that this class conforms to the undirected graph concept and
 
   379   /// is that this class conforms to the undirected graph concept and
 
   457   /// it does not contain the loop edges.
 
   380   /// it does not contain the loop edges.
 
   458   ///
 
   381   ///
 
   459   /// \sa FullUGraphBase
 
       
   460   /// \sa FullGraph
 
   382   /// \sa FullGraph
 
   461   ///
 
   383   ///
 
   462   /// \author Balazs Dezso
 
   384   /// \author Balazs Dezso
 
   463   class FullUGraph : public ExtendedFullUGraphBase {
 
   385   class FullUGraph : public ExtendedFullUGraphBase {
 
   464   public:
 
   386   public:
 
   483       construct(n);
 
   405       construct(n);
 
   484       Parent::getNotifier(Node()).build();
 
   406       Parent::getNotifier(Node()).build();
 
   485       Parent::getNotifier(UEdge()).build();
 
   407       Parent::getNotifier(UEdge()).build();
 
   486       Parent::getNotifier(Edge()).build();
 
   408       Parent::getNotifier(Edge()).build();
 
   487     }
 
   409     }
 
       
   410 
       
   411     /// \brief Returns the node with the given index.
 
       
   412     ///
 
       
   413     /// Returns the node with the given index. Because it is a
 
       
   414     /// static size graph the node's of the graph can be indiced
 
       
   415     /// by the range from 0 to \e nodeNum()-1 and the index of
 
       
   416     /// the node can accessed by the \e index() member.
 
       
   417     Node operator()(int index) const { return Parent::operator()(index); }
 
       
   418 
       
   419     /// \brief Returns the index of the node.
 
       
   420     ///
 
       
   421     /// Returns the index of the node. Because it is a
 
       
   422     /// static size graph the node's of the graph can be indiced
 
       
   423     /// by the range from 0 to \e nodeNum()-1 and the index of
 
       
   424     /// the node can accessed by the \e index() member.
 
       
   425     int index(const Node& node) const { return Parent::index(node); }
 
       
   426 
       
   427     /// \brief Number of nodes.
 
       
   428     int nodeNum() const { return Parent::nodeNum(); }
 
       
   429     /// \brief Number of edges.
 
       
   430     int edgeNum() const { return Parent::edgeNum(); }
 
       
   431     /// \brief Number of undirected edges.
 
       
   432     int uEdgeNum() const { return Parent::uEdgeNum(); }
 
       
   433 
       
   434     /// \brief Returns the edge connects the given nodes.
 
       
   435     ///
 
       
   436     /// Returns the edge connects the given nodes.
 
       
   437     Edge edge(const Node& u, const Node& v) const { 
       
   438       if (Parent::index(u) > Parent::index(v)) {
 
       
   439         return Parent::direct(Parent::edge(u, v), true);
 
       
   440       } else if (Parent::index(u) == Parent::index(v)) {
 
       
   441         return INVALID;
 
       
   442       } else {
 
       
   443         return Parent::direct(Parent::edge(v, u), false); 
       
   444       }
 
       
   445     }
 
       
   446 
       
   447     /// \brief Returns the undirected edge connects the given nodes.
 
       
   448     ///
 
       
   449     /// Returns the undirected edge connects the given nodes.
 
       
   450     UEdge uEdge(const Node& u, const Node& v) const {
 
       
   451       if (Parent::index(u) > Parent::index(v)) {
 
       
   452         return Parent::edge(u, v);
 
       
   453       } else if (Parent::index(u) == Parent::index(v)) {
 
       
   454         return INVALID;
 
       
   455       } else {
 
       
   456         return Parent::edge(v, u);
 
       
   457       }
 
       
   458     }
 
   488   };
 
   459   };
 
   489 
   460 
   490 
   461 
   491   class FullBpUGraphBase {
 
   462   class FullBpUGraphBase {
 
   492   protected:
 
   463   protected:
 
   493 
   464 
   494     int _aNodeNum;
 
   465     int _aNodeNum;
 
   495     int _bNodeNum;
 
   466     int _bNodeNum;
 
   496 
   467 
   497     int _edgeNum;
 
   468     int _edgeNum;
 
       
   469 
       
   470   protected:
 
       
   471 
       
   472     FullBpUGraphBase() {}
 
       
   473 
       
   474     void construct(int aNodeNum, int bNodeNum) {
 
       
   475       _aNodeNum = aNodeNum;
 
       
   476       _bNodeNum = bNodeNum;
 
       
   477       _edgeNum = aNodeNum * bNodeNum;
 
       
   478     }
 
   498 
   479 
   499   public:
 
   480   public:
 
   500 
   481 
   501     class NodeSetError : public LogicError {
 
   482     class NodeSetError : public LogicError {
 
   502     public:
 
   483     public:
 
   531       bool operator==(const UEdge i) const {return id==i.id;}
 
   512       bool operator==(const UEdge i) const {return id==i.id;}
 
   532       bool operator!=(const UEdge i) const {return id!=i.id;}
 
   513       bool operator!=(const UEdge i) const {return id!=i.id;}
 
   533       bool operator<(const UEdge i) const {return id<i.id;}
 
   514       bool operator<(const UEdge i) const {return id<i.id;}
 
   534     };
 
   515     };
 
   535 
   516 
   536     void construct(int aNodeNum, int bNodeNum) {
 
   517     Node aNode(int index) const { return Node(index << 1); }
 
   537       _aNodeNum = aNodeNum;
 
   518     Node bNode(int index) const { return Node((index << 1) + 1); }
 
   538       _bNodeNum = bNodeNum;
 
   519 
   539       _edgeNum = aNodeNum * bNodeNum;
 
   520     int aNodeIndex(const Node& node) const { return node.id >> 1; }
 
       
   521     int bNodeIndex(const Node& node) const { return node.id >> 1; }
 
       
   522 
       
   523     UEdge uEdge(const Node& u, const Node& v) const { 
       
   524       if (((u.id ^ v.id) & 1) != 1) {
 
       
   525         return UEdge(-1);
 
       
   526       } else if ((u.id & 1) == 0) {
 
       
   527         return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1));
 
       
   528       } else {
 
       
   529         return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1));
 
       
   530       }
 
   540     }
 
   531     }
 
   541 
   532 
   542     void firstANode(Node& node) const {
 
   533     void firstANode(Node& node) const {
 
   543       node.id = 2 * _aNodeNum - 2;
 
   534       node.id = 2 * _aNodeNum - 2;
 
   544       if (node.id < 0) node.id = -1; 
   535       if (node.id < 0) node.id = -1; 
   648 
   639 
   649     static bool bNode(const Node& node) {
 
   640     static bool bNode(const Node& node) {
 
   650       return (node.id & 1) == 1;
 
   641       return (node.id & 1) == 1;
 
   651     }
 
   642     }
 
   652 
   643 
   653     static Node aNode(int index) {
 
       
   654       return Node(index << 1);
 
       
   655     }
 
       
   656 
       
   657     static Node bNode(int index) {
 
       
   658       return Node((index << 1) + 1);
 
       
   659     }
 
       
   660 
   644 
   661     typedef True NodeNumTag;
 
   645     typedef True NodeNumTag;
 
   662     int nodeNum() const { return _aNodeNum + _bNodeNum; }
 
   646     int nodeNum() const { return _aNodeNum + _bNodeNum; }
 
   663     int aNodeNum() const { return _aNodeNum; }
 
   647     int aNodeNum() const { return _aNodeNum; }
 
   664     int bNodeNum() const { return _bNodeNum; }
 
   648     int bNodeNum() const { return _bNodeNum; }
 
   665 
   649 
   666     typedef True EdgeNumTag;
 
   650     typedef True EdgeNumTag;
 
   667     int uEdgeNum() const { return _edgeNum; }
 
   651     int uEdgeNum() const { return _edgeNum; }
 
   668 
   652 
       
   653 
       
   654     typedef True FindEdgeTag;
 
       
   655     UEdge findUEdge(Node u, Node v, UEdge prev = INVALID) const {
 
       
   656       if (prev.id != -1 || ((u.id ^ v.id) & 1) != 1) {
 
       
   657         return UEdge(-1);
 
       
   658       } else if ((u.id & 1) == 0) {
 
       
   659         return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1));
 
       
   660       } else {
 
       
   661         return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1));
 
       
   662       }
 
       
   663     }
 
       
   664 
   669   };
 
   665   };
 
   670 
   666 
   671 
   667 
   672   typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
 
   668   typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
 
   673 
   669 
   677   /// \brief An undirected full bipartite graph class.
 
   673   /// \brief An undirected full bipartite graph class.
 
   678   ///
 
   674   ///
 
   679   /// This is a simple and fast bipartite undirected full graph implementation.
 
   675   /// This is a simple and fast bipartite undirected full graph implementation.
 
   680   /// It is completely static, so you can neither add nor delete either
 
   676   /// It is completely static, so you can neither add nor delete either
 
   681   /// edges or nodes.
 
   677   /// edges or nodes.
 
   682   ///
 
       
   683   /// \sa FullUGraphBase
 
       
   684   /// \sa FullGraph
 
       
   685   ///
 
   678   ///
 
   686   /// \author Balazs Dezso
 
   679   /// \author Balazs Dezso
 
   687   class FullBpUGraph : 
   680   class FullBpUGraph : 
   688     public ExtendedFullBpUGraphBase {
 
   681     public ExtendedFullBpUGraphBase {
 
   689   public:
 
   682   public:
 
   698       Parent::construct(aNodeNum, bNodeNum);
 
   691       Parent::construct(aNodeNum, bNodeNum);
 
   699     }
 
   692     }
 
   700 
   693 
   701     /// \brief Resize the graph
 
   694     /// \brief Resize the graph
 
   702     ///
 
   695     ///
 
       
   696     /// Resize the graph
 
   703     void resize(int n, int m) {
 
   697     void resize(int n, int m) {
 
   704       Parent::getNotifier(Edge()).clear();
 
   698       Parent::getNotifier(Edge()).clear();
 
   705       Parent::getNotifier(UEdge()).clear();
 
   699       Parent::getNotifier(UEdge()).clear();
 
   706       Parent::getNotifier(Node()).clear();
 
   700       Parent::getNotifier(Node()).clear();
 
   707       Parent::getNotifier(ANode()).clear();
 
   701       Parent::getNotifier(ANode()).clear();
 
   711       Parent::getNotifier(BNode()).build();
 
   705       Parent::getNotifier(BNode()).build();
 
   712       Parent::getNotifier(Node()).build();
 
   706       Parent::getNotifier(Node()).build();
 
   713       Parent::getNotifier(UEdge()).build();
 
   707       Parent::getNotifier(UEdge()).build();
 
   714       Parent::getNotifier(Edge()).build();
 
   708       Parent::getNotifier(Edge()).build();
 
   715     }
 
   709     }
 
       
   710 
       
   711     /// \brief Number of nodes.
 
       
   712     int nodeNum() const { return Parent::nodeNum(); }
 
       
   713     /// \brief Number of A-nodes.
 
       
   714     int aNodeNum() const { return Parent::aNodeNum(); }
 
       
   715     /// \brief Number of B-nodes.
 
       
   716     int bNodeNum() const { return Parent::bNodeNum(); }
 
       
   717     /// \brief Number of edges.
 
       
   718     int edgeNum() const { return Parent::edgeNum(); }
 
       
   719     /// \brief Number of undirected edges.
 
       
   720     int uEdgeNum() const { return Parent::uEdgeNum(); }
 
       
   721 
       
   722 
       
   723     using Parent::aNode;
 
       
   724     using Parent::bNode;
 
       
   725 
       
   726     /// \brief Returns the A-node with the given index.
 
       
   727     ///
 
       
   728     /// Returns the A-node with the given index. Because it is a
 
       
   729     /// static size graph the node's of the graph can be indiced
 
       
   730     /// by the range from 0 to \e aNodeNum()-1 and the index of
 
       
   731     /// the node can accessed by the \e aNodeIndex() member.
 
       
   732     Node aNode(int index) const { return Parent::aNode(index); }
 
       
   733 
       
   734     /// \brief Returns the B-node with the given index.
 
       
   735     ///
 
       
   736     /// Returns the B-node with the given index. Because it is a
 
       
   737     /// static size graph the node's of the graph can be indiced
 
       
   738     /// by the range from 0 to \e bNodeNum()-1 and the index of
 
       
   739     /// the node can accessed by the \e bNodeIndex() member.
 
       
   740     Node bNode(int index) const { return Parent::bNode(index); }
 
       
   741 
       
   742     /// \brief Returns the index of the A-node.
 
       
   743     ///
 
       
   744     /// Returns the index of the A-node. Because it is a
 
       
   745     /// static size graph the node's of the graph can be indiced
 
       
   746     /// by the range from 0 to \e aNodeNum()-1 and the index of
 
       
   747     /// the node can accessed by the \e aNodeIndex() member.
 
       
   748     int aNodeIndex(const Node& node) const { return Parent::aNodeIndex(node); }
 
       
   749 
       
   750     /// \brief Returns the index of the B-node.
 
       
   751     ///
 
       
   752     /// Returns the index of the B-node. Because it is a
 
       
   753     /// static size graph the node's of the graph can be indiced
 
       
   754     /// by the range from 0 to \e bNodeNum()-1 and the index of
 
       
   755     /// the node can accessed by the \e bNodeIndex() member.
 
       
   756     int bNodeIndex(const Node& node) const { return Parent::bNodeIndex(node); }
 
       
   757 
       
   758     /// \brief Returns the edge connects the given nodes.
 
       
   759     ///
 
       
   760     /// Returns the edge connects the given nodes.
 
       
   761     Edge edge(const Node& u, const Node& v) const {
 
       
   762       UEdge uedge = Parent::uEdge(u, v);
 
       
   763       if (uedge != INVALID) {
 
       
   764         return Parent::direct(uedge, Parent::aNode(u));
 
       
   765       } else {
 
       
   766         return INVALID;
 
       
   767       }
 
       
   768     }
 
       
   769 
       
   770     /// \brief Returns the undirected edge connects the given nodes.
 
       
   771     ///
 
       
   772     /// Returns the undirected edge connects the given nodes.
 
       
   773     UEdge uEdge(const Node& u, const Node& v) const {
 
       
   774       return Parent::uEdge(u, v);
 
       
   775     }
 
   716   };
 
   776   };
 
   717 
   777 
   718 } //namespace lemon
 
   778 } //namespace lemon
 
   719 
   779 
   720 
   780
lemon-0.x