alpar@906: /* -*- C++ -*- alpar@906: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@1956: * Copyright (C) 2003-2006 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@591: alpar@921: #ifndef LEMON_FULL_GRAPH_H alpar@921: #define LEMON_FULL_GRAPH_H alpar@591: deba@983: #include deba@983: deba@2116: #include deba@1791: #include deba@1566: deba@1993: #include deba@1993: #include klao@977: klao@977: alpar@591: ///\ingroup graphs alpar@591: ///\file deba@2116: ///\brief FullGraph and FullUGraph classes. alpar@591: alpar@591: alpar@921: namespace lemon { alpar@591: klao@946: class FullGraphBase { deba@1566: int _nodeNum; deba@1566: int _edgeNum; alpar@591: public: deba@782: klao@946: typedef FullGraphBase Graph; alpar@591: alpar@591: class Node; alpar@591: class Edge; deba@782: deba@2223: protected: alpar@591: klao@946: FullGraphBase() {} klao@946: deba@2223: void construct(int n) { _nodeNum = n; _edgeNum = n * n; } klao@946: deba@2223: public: alpar@591: klao@977: typedef True NodeNumTag; klao@977: typedef True EdgeNumTag; klao@977: deba@1986: Node operator()(int index) const { return Node(index); } deba@1986: int index(const Node& node) const { return node.id; } deba@1986: deba@2223: Edge edge(const Node& u, const Node& v) const { deba@2223: return Edge(*this, u.id, v.id); deba@2223: } deba@2223: deba@1566: int nodeNum() const { return _nodeNum; } deba@1566: int edgeNum() const { return _edgeNum; } alpar@591: deba@1791: int maxNodeId() const { return _nodeNum-1; } deba@1791: int maxEdgeId() const { return _edgeNum-1; } alpar@591: deba@1566: Node source(Edge e) const { return e.id % _nodeNum; } deba@1566: Node target(Edge e) const { return e.id / _nodeNum; } alpar@591: alpar@591: klao@946: static int id(Node v) { return v.id; } klao@946: static int id(Edge e) { return e.id; } alpar@591: deba@1791: static Node nodeFromId(int id) { return Node(id);} deba@1106: deba@1791: static Edge edgeFromId(int id) { return Edge(id);} deba@1106: deba@1566: typedef True FindEdgeTag; deba@1566: deba@1566: Edge findEdge(Node u,Node v, Edge prev = INVALID) const { klao@946: return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; alpar@774: } alpar@774: alpar@774: alpar@591: class Node { klao@946: friend class FullGraphBase; alpar@591: alpar@591: protected: klao@946: int id; alpar@1643: Node(int _id) : id(_id) {} alpar@591: public: alpar@591: Node() {} alpar@1643: Node (Invalid) : id(-1) {} klao@946: bool operator==(const Node node) const {return id == node.id;} klao@946: bool operator!=(const Node node) const {return id != node.id;} klao@946: bool operator<(const Node node) const {return id < node.id;} alpar@591: }; alpar@591: klao@946: klao@946: klao@946: class Edge { klao@946: friend class FullGraphBase; klao@946: klao@946: protected: deba@1566: int id; // _nodeNum * target + source; klao@946: klao@946: Edge(int _id) : id(_id) {} klao@946: alpar@986: Edge(const FullGraphBase& _graph, int source, int target) deba@1566: : id(_graph._nodeNum * target+source) {} alpar@591: public: klao@946: Edge() { } klao@946: Edge (Invalid) { id = -1; } klao@946: bool operator==(const Edge edge) const {return id == edge.id;} klao@946: bool operator!=(const Edge edge) const {return id != edge.id;} klao@946: bool operator<(const Edge edge) const {return id < edge.id;} alpar@591: }; alpar@591: klao@946: void first(Node& node) const { deba@1566: node.id = _nodeNum-1; klao@946: } alpar@591: klao@946: static void next(Node& node) { klao@946: --node.id; klao@946: } klao@946: klao@946: void first(Edge& edge) const { deba@1566: edge.id = _edgeNum-1; klao@946: } klao@946: klao@946: static void next(Edge& edge) { klao@946: --edge.id; klao@946: } klao@946: klao@946: void firstOut(Edge& edge, const Node& node) const { deba@1566: edge.id = _edgeNum + node.id - _nodeNum; klao@946: } klao@946: klao@946: void nextOut(Edge& edge) const { deba@1566: edge.id -= _nodeNum; klao@946: if (edge.id < 0) edge.id = -1; klao@946: } klao@946: klao@946: void firstIn(Edge& edge, const Node& node) const { deba@1566: edge.id = node.id * _nodeNum; klao@946: } alpar@591: klao@946: void nextIn(Edge& edge) const { klao@946: ++edge.id; deba@1566: if (edge.id % _nodeNum == 0) edge.id = -1; klao@946: } alpar@591: alpar@591: }; alpar@591: deba@1979: typedef GraphExtender ExtendedFullGraphBase; klao@946: deba@1566: /// \ingroup graphs alpar@951: /// deba@1566: /// \brief A full graph class. deba@1566: /// deba@1566: /// This is a simple and fast directed full graph implementation. deba@1566: /// It is completely static, so you can neither add nor delete either deba@1566: /// edges or nodes. deba@1566: /// Thus it conforms to deba@2111: /// the \ref concept::Graph "Graph" concept deba@2111: /// \sa concept::Graph. deba@1566: /// deba@1986: /// \sa FullUGraph deba@1986: /// deba@1566: /// \author Alpar Juttner deba@1669: class FullGraph : public ExtendedFullGraphBase { klao@946: public: klao@946: deba@1979: typedef ExtendedFullGraphBase Parent; deba@1979: deba@1979: /// \brief Constructor deba@1987: FullGraph() { construct(0); } deba@1987: deba@1987: /// \brief Constructor deba@1979: /// klao@946: FullGraph(int n) { construct(n); } deba@1979: deba@1979: /// \brief Resize the graph deba@1979: /// deba@1986: /// Resize the graph. The function will fully destroy and build the graph. deba@1986: /// This cause that the maps of the graph will reallocated deba@1986: /// automatically and the previous values will be lost. deba@1979: void resize(int n) { deba@1979: Parent::getNotifier(Edge()).clear(); deba@1979: Parent::getNotifier(Node()).clear(); deba@1979: construct(n); deba@1979: Parent::getNotifier(Node()).build(); deba@1979: Parent::getNotifier(Edge()).build(); deba@1979: } deba@2223: deba@2223: /// \brief Returns the node with the given index. deba@2223: /// deba@2223: /// Returns the node with the given index. Because it is a deba@2223: /// static size graph the node's of the graph can be indiced deba@2223: /// by the range from 0 to \e nodeNum()-1 and the index of deba@2223: /// the node can accessed by the \e index() member. deba@2223: Node operator()(int index) const { return Parent::operator()(index); } deba@2223: deba@2223: /// \brief Returns the index of the node. deba@2223: /// deba@2223: /// Returns the index of the node. Because it is a deba@2223: /// static size graph the node's of the graph can be indiced deba@2223: /// by the range from 0 to \e nodeNum()-1 and the index of deba@2223: /// the node can accessed by the \e index() member. deba@2223: int index(const Node& node) const { return Parent::index(node); } deba@2223: deba@2223: /// \brief Returns the edge connects the given nodes. deba@2223: /// deba@2223: /// Returns the edge connects the given nodes. deba@2223: Edge edge(const Node& u, const Node& v) const { deba@2223: return Parent::edge(u, v); deba@2223: } deba@2223: deba@2223: /// \brief Number of nodes. deba@2223: int nodeNum() const { return Parent::nodeNum(); } deba@2223: /// \brief Number of edges. deba@2223: int edgeNum() const { return Parent::edgeNum(); } klao@946: }; klao@946: deba@2116: deba@2116: class FullUGraphBase { deba@2116: int _nodeNum; deba@2116: int _edgeNum; deba@2116: public: deba@2116: deba@2116: typedef FullUGraphBase Graph; deba@2116: deba@2116: class Node; deba@2116: class Edge; deba@2116: deba@2223: protected: deba@2116: deba@2116: FullUGraphBase() {} deba@2116: deba@2116: void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; } deba@2116: deba@2223: public: deba@2223: deba@2223: deba@2116: Node operator()(int index) const { return Node(index); } deba@2223: int index(const Node& node) const { return node.id; } deba@2116: deba@2223: Edge edge(const Node& u, const Node& v) const { deba@2223: return Edge(u.id * (u.id - 1) / 2 + v.id); deba@2223: } deba@2116: deba@2116: typedef True NodeNumTag; deba@2116: typedef True EdgeNumTag; deba@2116: deba@2116: int nodeNum() const { return _nodeNum; } deba@2116: int edgeNum() const { return _edgeNum; } deba@2116: deba@2116: int maxNodeId() const { return _nodeNum-1; } deba@2116: int maxEdgeId() const { return _edgeNum-1; } deba@2116: deba@2116: static Node nodeFromId(int id) { return Node(id);} deba@2116: static Edge edgeFromId(int id) { return Edge(id);} deba@2116: deba@2116: Node source(Edge e) const { deba@2116: /// \todo we may do it faster deba@2116: return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2); deba@2116: } deba@2116: deba@2116: Node target(Edge e) const { deba@2116: int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; deba@2116: return Node(e.id - (source) * (source - 1) / 2); deba@2116: } deba@2116: deba@2116: static int id(Node v) { return v.id; } deba@2116: static int id(Edge e) { return e.id; } deba@2116: deba@2116: Edge findEdge(Node u, Node v, Edge prev = INVALID) const { deba@2116: if (prev.id != -1 || u.id <= v.id) return Edge(-1); deba@2116: return Edge(u.id * (u.id - 1) / 2 + v.id); deba@2116: } deba@2116: deba@2116: typedef True FindEdgeTag; deba@2116: deba@2116: deba@2116: class Node { deba@2116: friend class FullUGraphBase; deba@2116: deba@2116: protected: deba@2116: int id; deba@2116: Node(int _id) { id = _id;} deba@2116: public: deba@2116: Node() {} deba@2116: Node (Invalid) { id = -1; } deba@2116: bool operator==(const Node node) const {return id == node.id;} deba@2116: bool operator!=(const Node node) const {return id != node.id;} deba@2116: bool operator<(const Node node) const {return id < node.id;} deba@2116: }; deba@2116: deba@2116: deba@2116: deba@2116: class Edge { deba@2116: friend class FullUGraphBase; deba@2116: deba@2116: protected: deba@2116: int id; // _nodeNum * target + source; deba@2116: deba@2116: Edge(int _id) : id(_id) {} deba@2116: deba@2116: public: deba@2116: Edge() { } deba@2116: Edge (Invalid) { id = -1; } deba@2116: bool operator==(const Edge edge) const {return id == edge.id;} deba@2116: bool operator!=(const Edge edge) const {return id != edge.id;} deba@2116: bool operator<(const Edge edge) const {return id < edge.id;} deba@2116: }; deba@2116: deba@2116: void first(Node& node) const { deba@2116: node.id = _nodeNum - 1; deba@2116: } deba@2116: deba@2116: static void next(Node& node) { deba@2116: --node.id; deba@2116: } deba@2116: deba@2116: void first(Edge& edge) const { deba@2116: edge.id = _edgeNum - 1; deba@2116: } deba@2116: deba@2116: static void next(Edge& edge) { deba@2116: --edge.id; deba@2116: } deba@2116: deba@2116: void firstOut(Edge& edge, const Node& node) const { deba@2116: int src = node.id; deba@2116: int trg = 0; deba@2116: edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); deba@2116: } deba@2116: deba@2116: /// \todo with specialized iterators we can make faster iterating deba@2116: void nextOut(Edge& edge) const { deba@2116: int src = source(edge).id; deba@2116: int trg = target(edge).id; deba@2116: ++trg; deba@2116: edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); deba@2116: } deba@2116: deba@2116: void firstIn(Edge& edge, const Node& node) const { deba@2116: int src = node.id + 1; deba@2116: int trg = node.id; deba@2116: edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); deba@2116: } deba@2116: deba@2116: void nextIn(Edge& edge) const { deba@2116: int src = source(edge).id; deba@2116: int trg = target(edge).id; deba@2116: ++src; deba@2116: edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: typedef UGraphExtender > deba@2116: ExtendedFullUGraphBase; deba@2116: deba@2116: /// \ingroup graphs deba@2116: /// deba@2116: /// \brief An undirected full graph class. deba@2116: /// deba@2116: /// This is a simple and fast undirected full graph implementation. deba@2116: /// It is completely static, so you can neither add nor delete either deba@2116: /// edges or nodes. deba@2116: /// deba@2116: /// The main difference beetween the \e FullGraph and \e FullUGraph class deba@2116: /// is that this class conforms to the undirected graph concept and deba@2116: /// it does not contain the loop edges. deba@2116: /// deba@2116: /// \sa FullGraph deba@2116: /// deba@2116: /// \author Balazs Dezso deba@2116: class FullUGraph : public ExtendedFullUGraphBase { deba@2116: public: deba@2116: deba@2116: typedef ExtendedFullUGraphBase Parent; deba@2116: deba@2116: /// \brief Constructor deba@2116: FullUGraph() { construct(0); } deba@2116: deba@2116: /// \brief Constructor deba@2116: FullUGraph(int n) { construct(n); } deba@2116: deba@2116: /// \brief Resize the graph deba@2116: /// deba@2116: /// Resize the graph. The function will fully destroy and build the graph. deba@2116: /// This cause that the maps of the graph will reallocated deba@2116: /// automatically and the previous values will be lost. deba@2116: void resize(int n) { deba@2116: Parent::getNotifier(Edge()).clear(); deba@2116: Parent::getNotifier(UEdge()).clear(); deba@2116: Parent::getNotifier(Node()).clear(); deba@2116: construct(n); deba@2116: Parent::getNotifier(Node()).build(); deba@2116: Parent::getNotifier(UEdge()).build(); deba@2116: Parent::getNotifier(Edge()).build(); deba@2116: } deba@2223: deba@2223: /// \brief Returns the node with the given index. deba@2223: /// deba@2223: /// Returns the node with the given index. Because it is a deba@2223: /// static size graph the node's of the graph can be indiced deba@2223: /// by the range from 0 to \e nodeNum()-1 and the index of deba@2223: /// the node can accessed by the \e index() member. deba@2223: Node operator()(int index) const { return Parent::operator()(index); } deba@2223: deba@2223: /// \brief Returns the index of the node. deba@2223: /// deba@2223: /// Returns the index of the node. Because it is a deba@2223: /// static size graph the node's of the graph can be indiced deba@2223: /// by the range from 0 to \e nodeNum()-1 and the index of deba@2223: /// the node can accessed by the \e index() member. deba@2223: int index(const Node& node) const { return Parent::index(node); } deba@2223: deba@2223: /// \brief Number of nodes. deba@2223: int nodeNum() const { return Parent::nodeNum(); } deba@2223: /// \brief Number of edges. deba@2223: int edgeNum() const { return Parent::edgeNum(); } deba@2223: /// \brief Number of undirected edges. deba@2223: int uEdgeNum() const { return Parent::uEdgeNum(); } deba@2223: deba@2223: /// \brief Returns the edge connects the given nodes. deba@2223: /// deba@2223: /// Returns the edge connects the given nodes. deba@2223: Edge edge(const Node& u, const Node& v) const { deba@2223: if (Parent::index(u) > Parent::index(v)) { deba@2223: return Parent::direct(Parent::edge(u, v), true); deba@2223: } else if (Parent::index(u) == Parent::index(v)) { deba@2223: return INVALID; deba@2223: } else { deba@2223: return Parent::direct(Parent::edge(v, u), false); deba@2223: } deba@2223: } deba@2223: deba@2223: /// \brief Returns the undirected edge connects the given nodes. deba@2223: /// deba@2223: /// Returns the undirected edge connects the given nodes. deba@2223: UEdge uEdge(const Node& u, const Node& v) const { deba@2223: if (Parent::index(u) > Parent::index(v)) { deba@2223: return Parent::edge(u, v); deba@2223: } else if (Parent::index(u) == Parent::index(v)) { deba@2223: return INVALID; deba@2223: } else { deba@2223: return Parent::edge(v, u); deba@2223: } deba@2223: } deba@2116: }; deba@2116: deba@2116: deba@2116: class FullBpUGraphBase { deba@2116: protected: deba@2116: deba@2116: int _aNodeNum; deba@2116: int _bNodeNum; deba@2116: deba@2116: int _edgeNum; deba@2116: deba@2223: protected: deba@2223: deba@2223: FullBpUGraphBase() {} deba@2223: deba@2223: void construct(int aNodeNum, int bNodeNum) { deba@2223: _aNodeNum = aNodeNum; deba@2223: _bNodeNum = bNodeNum; deba@2223: _edgeNum = aNodeNum * bNodeNum; deba@2223: } deba@2223: deba@2116: public: deba@2116: deba@2116: class NodeSetError : public LogicError { deba@2162: public: alpar@2151: virtual const char* what() const throw() { deba@2116: return "lemon::FullBpUGraph::NodeSetError"; deba@2116: } deba@2116: }; deba@2116: deba@2116: class Node { deba@2116: friend class FullBpUGraphBase; deba@2116: protected: deba@2116: int id; deba@2116: deba@2116: Node(int _id) : id(_id) {} deba@2116: public: deba@2116: Node() {} deba@2116: Node(Invalid) { id = -1; } deba@2116: bool operator==(const Node i) const {return id==i.id;} deba@2116: bool operator!=(const Node i) const {return id!=i.id;} deba@2116: bool operator<(const Node i) const {return id> 1; } deba@2223: int bNodeIndex(const Node& node) const { return node.id >> 1; } deba@2223: deba@2223: UEdge uEdge(const Node& u, const Node& v) const { deba@2223: if (((u.id ^ v.id) & 1) != 1) { deba@2223: return UEdge(-1); deba@2223: } else if ((u.id & 1) == 0) { deba@2223: return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1)); deba@2223: } else { deba@2223: return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1)); deba@2223: } deba@2116: } deba@2116: deba@2116: void firstANode(Node& node) const { deba@2116: node.id = 2 * _aNodeNum - 2; deba@2116: if (node.id < 0) node.id = -1; deba@2116: } deba@2116: void nextANode(Node& node) const { deba@2116: node.id -= 2; deba@2116: if (node.id < 0) node.id = -1; deba@2116: } deba@2116: deba@2116: void firstBNode(Node& node) const { deba@2116: node.id = 2 * _bNodeNum - 1; deba@2116: } deba@2116: void nextBNode(Node& node) const { deba@2116: node.id -= 2; deba@2116: } deba@2116: deba@2116: void first(Node& node) const { deba@2116: if (_aNodeNum > 0) { deba@2116: node.id = 2 * _aNodeNum - 2; deba@2116: } else { deba@2116: node.id = 2 * _bNodeNum - 1; deba@2116: } deba@2116: } deba@2116: void next(Node& node) const { deba@2116: node.id -= 2; deba@2116: if (node.id == -2) { deba@2116: node.id = 2 * _bNodeNum - 1; deba@2116: } deba@2116: } deba@2116: deba@2116: void first(UEdge& edge) const { deba@2116: edge.id = _edgeNum - 1; deba@2116: } deba@2116: void next(UEdge& edge) const { deba@2116: --edge.id; deba@2116: } deba@2116: deba@2116: void firstFromANode(UEdge& edge, const Node& node) const { deba@2116: LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); deba@2116: edge.id = (node.id >> 1) * _bNodeNum; deba@2116: } deba@2116: void nextFromANode(UEdge& edge) const { deba@2116: ++(edge.id); deba@2116: if (edge.id % _bNodeNum == 0) edge.id = -1; deba@2116: } deba@2116: deba@2116: void firstFromBNode(UEdge& edge, const Node& node) const { deba@2116: LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); deba@2116: edge.id = (node.id >> 1); deba@2116: } deba@2116: void nextFromBNode(UEdge& edge) const { deba@2116: edge.id += _bNodeNum; deba@2116: if (edge.id >= _edgeNum) edge.id = -1; deba@2116: } deba@2116: deba@2116: static int id(const Node& node) { deba@2116: return node.id; deba@2116: } deba@2116: static Node nodeFromId(int id) { deba@2116: return Node(id); deba@2116: } deba@2116: int maxNodeId() const { deba@2116: return _aNodeNum > _bNodeNum ? deba@2116: _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1; deba@2116: } deba@2116: deba@2116: static int id(const UEdge& edge) { deba@2116: return edge.id; deba@2116: } deba@2116: static UEdge uEdgeFromId(int id) { deba@2116: return UEdge(id); deba@2116: } deba@2116: int maxUEdgeId() const { deba@2116: return _edgeNum - 1; deba@2116: } deba@2116: deba@2116: static int aNodeId(const Node& node) { deba@2116: return node.id >> 1; deba@2116: } deba@2231: static Node nodeFromANodeId(int id) { deba@2116: return Node(id << 1); deba@2116: } deba@2116: int maxANodeId() const { deba@2116: return _aNodeNum; deba@2116: } deba@2116: deba@2116: static int bNodeId(const Node& node) { deba@2116: return node.id >> 1; deba@2116: } deba@2231: static Node nodeFromBNodeId(int id) { deba@2116: return Node((id << 1) + 1); deba@2116: } deba@2116: int maxBNodeId() const { deba@2116: return _bNodeNum; deba@2116: } deba@2116: deba@2116: Node aNode(const UEdge& edge) const { deba@2116: return Node((edge.id / _bNodeNum) << 1); deba@2116: } deba@2116: Node bNode(const UEdge& edge) const { deba@2116: return Node(((edge.id % _bNodeNum) << 1) + 1); deba@2116: } deba@2116: deba@2116: static bool aNode(const Node& node) { deba@2116: return (node.id & 1) == 0; deba@2116: } deba@2116: deba@2116: static bool bNode(const Node& node) { deba@2116: return (node.id & 1) == 1; deba@2116: } deba@2116: deba@2116: deba@2116: typedef True NodeNumTag; deba@2116: int nodeNum() const { return _aNodeNum + _bNodeNum; } deba@2116: int aNodeNum() const { return _aNodeNum; } deba@2116: int bNodeNum() const { return _bNodeNum; } deba@2116: deba@2116: typedef True EdgeNumTag; deba@2116: int uEdgeNum() const { return _edgeNum; } deba@2116: deba@2223: deba@2223: typedef True FindEdgeTag; deba@2223: UEdge findUEdge(Node u, Node v, UEdge prev = INVALID) const { deba@2223: if (prev.id != -1 || ((u.id ^ v.id) & 1) != 1) { deba@2223: return UEdge(-1); deba@2223: } else if ((u.id & 1) == 0) { deba@2223: return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1)); deba@2223: } else { deba@2223: return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1)); deba@2223: } deba@2223: } deba@2223: deba@2116: }; deba@2116: deba@2116: deba@2231: typedef BpUGraphExtender > deba@2231: ExtendedFullBpUGraphBase; deba@2116: deba@2116: deba@2116: /// \ingroup graphs deba@2116: /// deba@2116: /// \brief An undirected full bipartite graph class. deba@2116: /// deba@2116: /// This is a simple and fast bipartite undirected full graph implementation. deba@2116: /// It is completely static, so you can neither add nor delete either deba@2116: /// edges or nodes. deba@2116: /// deba@2116: /// \author Balazs Dezso deba@2116: class FullBpUGraph : deba@2116: public ExtendedFullBpUGraphBase { deba@2116: public: deba@2116: deba@2116: typedef ExtendedFullBpUGraphBase Parent; deba@2116: deba@2116: FullBpUGraph() { deba@2116: Parent::construct(0, 0); deba@2116: } deba@2116: deba@2116: FullBpUGraph(int aNodeNum, int bNodeNum) { deba@2116: Parent::construct(aNodeNum, bNodeNum); deba@2116: } deba@2116: deba@2116: /// \brief Resize the graph deba@2116: /// deba@2223: /// Resize the graph deba@2116: void resize(int n, int m) { deba@2116: Parent::getNotifier(Edge()).clear(); deba@2116: Parent::getNotifier(UEdge()).clear(); deba@2116: Parent::getNotifier(Node()).clear(); deba@2116: Parent::getNotifier(ANode()).clear(); deba@2116: Parent::getNotifier(BNode()).clear(); deba@2116: construct(n, m); deba@2116: Parent::getNotifier(ANode()).build(); deba@2116: Parent::getNotifier(BNode()).build(); deba@2116: Parent::getNotifier(Node()).build(); deba@2116: Parent::getNotifier(UEdge()).build(); deba@2116: Parent::getNotifier(Edge()).build(); deba@2116: } deba@2223: deba@2223: /// \brief Number of nodes. deba@2223: int nodeNum() const { return Parent::nodeNum(); } deba@2223: /// \brief Number of A-nodes. deba@2223: int aNodeNum() const { return Parent::aNodeNum(); } deba@2223: /// \brief Number of B-nodes. deba@2223: int bNodeNum() const { return Parent::bNodeNum(); } deba@2223: /// \brief Number of edges. deba@2223: int edgeNum() const { return Parent::edgeNum(); } deba@2223: /// \brief Number of undirected edges. deba@2223: int uEdgeNum() const { return Parent::uEdgeNum(); } deba@2223: deba@2223: deba@2223: using Parent::aNode; deba@2223: using Parent::bNode; deba@2223: deba@2223: /// \brief Returns the A-node with the given index. deba@2223: /// deba@2223: /// Returns the A-node with the given index. Because it is a deba@2223: /// static size graph the node's of the graph can be indiced deba@2223: /// by the range from 0 to \e aNodeNum()-1 and the index of deba@2223: /// the node can accessed by the \e aNodeIndex() member. deba@2223: Node aNode(int index) const { return Parent::aNode(index); } deba@2223: deba@2223: /// \brief Returns the B-node with the given index. deba@2223: /// deba@2223: /// Returns the B-node with the given index. Because it is a deba@2223: /// static size graph the node's of the graph can be indiced deba@2223: /// by the range from 0 to \e bNodeNum()-1 and the index of deba@2223: /// the node can accessed by the \e bNodeIndex() member. deba@2223: Node bNode(int index) const { return Parent::bNode(index); } deba@2223: deba@2223: /// \brief Returns the index of the A-node. deba@2223: /// deba@2223: /// Returns the index of the A-node. Because it is a deba@2223: /// static size graph the node's of the graph can be indiced deba@2223: /// by the range from 0 to \e aNodeNum()-1 and the index of deba@2223: /// the node can accessed by the \e aNodeIndex() member. deba@2223: int aNodeIndex(const Node& node) const { return Parent::aNodeIndex(node); } deba@2223: deba@2223: /// \brief Returns the index of the B-node. deba@2223: /// deba@2223: /// Returns the index of the B-node. Because it is a deba@2223: /// static size graph the node's of the graph can be indiced deba@2223: /// by the range from 0 to \e bNodeNum()-1 and the index of deba@2223: /// the node can accessed by the \e bNodeIndex() member. deba@2223: int bNodeIndex(const Node& node) const { return Parent::bNodeIndex(node); } deba@2223: deba@2223: /// \brief Returns the edge connects the given nodes. deba@2223: /// deba@2223: /// Returns the edge connects the given nodes. deba@2223: Edge edge(const Node& u, const Node& v) const { deba@2223: UEdge uedge = Parent::uEdge(u, v); deba@2223: if (uedge != INVALID) { deba@2223: return Parent::direct(uedge, Parent::aNode(u)); deba@2223: } else { deba@2223: return INVALID; deba@2223: } deba@2223: } deba@2223: deba@2223: /// \brief Returns the undirected edge connects the given nodes. deba@2223: /// deba@2223: /// Returns the undirected edge connects the given nodes. deba@2223: UEdge uEdge(const Node& u, const Node& v) const { deba@2223: return Parent::uEdge(u, v); deba@2223: } deba@2116: }; deba@2116: alpar@921: } //namespace lemon alpar@591: alpar@591: alpar@921: #endif //LEMON_FULL_GRAPH_H