/* -*- C++ -*- * * This file is a part of LEMON, a generic C++ optimization library * * Copyright (C) 2003-2006 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #ifndef LEMON_FULL_GRAPH_H #define LEMON_FULL_GRAPH_H #include #include #include #include ///\ingroup graphs ///\file ///\brief FullGraph and FullUGraph classes. namespace lemon { /// \brief Base of the FullGrpah. /// /// Base of the FullGrpah. class FullGraphBase { int _nodeNum; int _edgeNum; public: typedef FullGraphBase Graph; class Node; class Edge; public: FullGraphBase() {} ///Creates a full graph with \c n nodes. void construct(int n) { _nodeNum = n; _edgeNum = n * n; } typedef True NodeNumTag; typedef True EdgeNumTag; /// \brief Returns the node with the given index. /// /// Returns the node with the given index. Because it is a /// static size graph the node's of the graph can be indiced /// by the range from 0 to \e nodeNum()-1 and the index of /// the node can accessed by the \e index() member. Node operator()(int index) const { return Node(index); } /// \brief Returns the index of the node. /// /// Returns the index of the node. Because it is a /// static size graph the node's of the graph can be indiced /// by the range from 0 to \e nodeNum()-1 and the index of /// the node can accessed by the \e index() member. int index(const Node& node) const { return node.id; } ///Number of nodes. int nodeNum() const { return _nodeNum; } ///Number of edges. int edgeNum() const { return _edgeNum; } /// Maximum node ID. /// Maximum node ID. ///\sa id(Node) int maxNodeId() const { return _nodeNum-1; } /// Maximum edge ID. /// Maximum edge ID. ///\sa id(Edge) int maxEdgeId() const { return _edgeNum-1; } Node source(Edge e) const { return e.id % _nodeNum; } Node target(Edge e) const { return e.id / _nodeNum; } /// Node ID. /// The ID of a valid Node is a nonnegative integer not greater than /// \ref maxNodeId(). The range of the ID's is not surely continuous /// and the greatest node ID can be actually less then \ref maxNodeId(). /// /// The ID of the \ref INVALID node is -1. ///\return The ID of the node \c v. static int id(Node v) { return v.id; } /// Edge ID. /// The ID of a valid Edge is a nonnegative integer not greater than /// \ref maxEdgeId(). The range of the ID's is not surely continuous /// and the greatest edge ID can be actually less then \ref maxEdgeId(). /// /// The ID of the \ref INVALID edge is -1. ///\return The ID of the edge \c e. static int id(Edge e) { return e.id; } static Node nodeFromId(int id) { return Node(id);} static Edge edgeFromId(int id) { return Edge(id);} typedef True FindEdgeTag; /// Finds an edge between two nodes. /// Finds an edge from node \c u to node \c v. /// /// If \c prev is \ref INVALID (this is the default value), then /// It finds the first edge from \c u to \c v. Otherwise it looks for /// the next edge from \c u to \c v after \c prev. /// \return The found edge or INVALID if there is no such an edge. Edge findEdge(Node u,Node v, Edge prev = INVALID) const { return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; } class Node { friend class FullGraphBase; protected: int id; Node(int _id) : id(_id) {} public: Node() {} Node (Invalid) : id(-1) {} bool operator==(const Node node) const {return id == node.id;} bool operator!=(const Node node) const {return id != node.id;} bool operator<(const Node node) const {return id < node.id;} }; class Edge { friend class FullGraphBase; protected: int id; // _nodeNum * target + source; Edge(int _id) : id(_id) {} Edge(const FullGraphBase& _graph, int source, int target) : id(_graph._nodeNum * target+source) {} public: Edge() { } Edge (Invalid) { id = -1; } bool operator==(const Edge edge) const {return id == edge.id;} bool operator!=(const Edge edge) const {return id != edge.id;} bool operator<(const Edge edge) const {return id < edge.id;} }; void first(Node& node) const { node.id = _nodeNum-1; } static void next(Node& node) { --node.id; } void first(Edge& edge) const { edge.id = _edgeNum-1; } static void next(Edge& edge) { --edge.id; } void firstOut(Edge& edge, const Node& node) const { edge.id = _edgeNum + node.id - _nodeNum; } void nextOut(Edge& edge) const { edge.id -= _nodeNum; if (edge.id < 0) edge.id = -1; } void firstIn(Edge& edge, const Node& node) const { edge.id = node.id * _nodeNum; } void nextIn(Edge& edge) const { ++edge.id; if (edge.id % _nodeNum == 0) edge.id = -1; } }; typedef GraphExtender ExtendedFullGraphBase; /// \ingroup graphs /// /// \brief A full graph class. /// /// This is a simple and fast directed full graph implementation. /// It is completely static, so you can neither add nor delete either /// edges or nodes. /// Thus it conforms to /// the \ref concept::StaticGraph "StaticGraph" concept /// \sa concept::StaticGraph. /// /// \sa FullGraphBase /// \sa FullUGraph /// /// \author Alpar Juttner class FullGraph : public ExtendedFullGraphBase { public: typedef ExtendedFullGraphBase Parent; /// \brief Constructor FullGraph() { construct(0); } /// \brief Constructor /// FullGraph(int n) { construct(n); } /// \brief Resize the graph /// /// Resize the graph. The function will fully destroy and build the graph. /// This cause that the maps of the graph will reallocated /// automatically and the previous values will be lost. void resize(int n) { Parent::getNotifier(Edge()).clear(); Parent::getNotifier(Node()).clear(); construct(n); Parent::getNotifier(Node()).build(); Parent::getNotifier(Edge()).build(); } }; /// \brief Base of the FullUGrpah. /// /// Base of the FullUGrpah. class FullUGraphBase { int _nodeNum; int _edgeNum; public: typedef FullUGraphBase Graph; class Node; class Edge; public: FullUGraphBase() {} ///Creates a full graph with \c n nodes. void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; } /// \brief Returns the node with the given index. /// /// Returns the node with the given index. Because it is a /// static size graph the node's of the graph can be indiced /// by the range from 0 to \e nodeNum()-1 and the index of /// the node can accessed by the \e index() member. Node operator()(int index) const { return Node(index); } /// \brief Returns the index of the node. /// /// Returns the index of the node. Because it is a /// static size graph the node's of the graph can be indiced /// by the range from 0 to \e nodeNum()-1 and the index of /// the node can accessed by the \e index() member. int index(const Node& node) const { return node.id; } typedef True NodeNumTag; typedef True EdgeNumTag; ///Number of nodes. int nodeNum() const { return _nodeNum; } ///Number of edges. int edgeNum() const { return _edgeNum; } /// Maximum node ID. /// Maximum node ID. ///\sa id(Node) int maxNodeId() const { return _nodeNum-1; } /// Maximum edge ID. /// Maximum edge ID. ///\sa id(Edge) int maxEdgeId() const { return _edgeNum-1; } Node source(Edge e) const { /// \todo we may do it faster return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2); } Node target(Edge e) const { int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; return Node(e.id - (source) * (source - 1) / 2); } /// \brief Node ID. /// /// The ID of a valid Node is a nonnegative integer not greater than /// \ref maxNodeId(). The range of the ID's is not surely continuous /// and the greatest node ID can be actually less then \ref maxNodeId(). /// /// The ID of the \ref INVALID node is -1. /// \return The ID of the node \c v. static int id(Node v) { return v.id; } /// \brief Edge ID. /// /// The ID of a valid Edge is a nonnegative integer not greater than /// \ref maxEdgeId(). The range of the ID's is not surely continuous /// and the greatest edge ID can be actually less then \ref maxEdgeId(). /// /// The ID of the \ref INVALID edge is -1. ///\return The ID of the edge \c e. static int id(Edge e) { return e.id; } /// \brief Finds an edge between two nodes. /// /// Finds an edge from node \c u to node \c v. /// /// If \c prev is \ref INVALID (this is the default value), then /// It finds the first edge from \c u to \c v. Otherwise it looks for /// the next edge from \c u to \c v after \c prev. /// \return The found edge or INVALID if there is no such an edge. Edge findEdge(Node u, Node v, Edge prev = INVALID) const { if (prev.id != -1 || u.id <= v.id) return Edge(-1); return Edge(u.id * (u.id - 1) / 2 + v.id); } typedef True FindEdgeTag; class Node { friend class FullUGraphBase; protected: int id; Node(int _id) { id = _id;} public: Node() {} Node (Invalid) { id = -1; } bool operator==(const Node node) const {return id == node.id;} bool operator!=(const Node node) const {return id != node.id;} bool operator<(const Node node) const {return id < node.id;} }; class Edge { friend class FullUGraphBase; protected: int id; // _nodeNum * target + source; Edge(int _id) : id(_id) {} public: Edge() { } Edge (Invalid) { id = -1; } bool operator==(const Edge edge) const {return id == edge.id;} bool operator!=(const Edge edge) const {return id != edge.id;} bool operator<(const Edge edge) const {return id < edge.id;} }; void first(Node& node) const { node.id = _nodeNum - 1; } static void next(Node& node) { --node.id; } void first(Edge& edge) const { edge.id = _edgeNum - 1; } static void next(Edge& edge) { --edge.id; } void firstOut(Edge& edge, const Node& node) const { int src = node.id; int trg = 0; edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); } /// \todo with specialized iterators we can make faster iterating void nextOut(Edge& edge) const { int src = source(edge).id; int trg = target(edge).id; ++trg; edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); } void firstIn(Edge& edge, const Node& node) const { int src = node.id + 1; int trg = node.id; edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); } void nextIn(Edge& edge) const { int src = source(edge).id; int trg = target(edge).id; ++src; edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); } }; typedef UGraphExtender > ExtendedFullUGraphBase; /// \ingroup graphs /// /// \brief An undirected full graph class. /// /// This is a simple and fast undirected full graph implementation. /// It is completely static, so you can neither add nor delete either /// edges or nodes. /// /// The main difference beetween the \e FullGraph and \e FullUGraph class /// is that this class conforms to the undirected graph concept and /// it does not contain the loop edges. /// /// \sa FullUGraphBase /// \sa FullGraph /// /// \author Balazs Dezso class FullUGraph : public ExtendedFullUGraphBase { public: typedef ExtendedFullUGraphBase Parent; /// \brief Constructor FullUGraph() { construct(0); } /// \brief Constructor FullUGraph(int n) { construct(n); } /// \brief Resize the graph /// /// Resize the graph. The function will fully destroy and build the graph. /// This cause that the maps of the graph will reallocated /// automatically and the previous values will be lost. void resize(int n) { Parent::getNotifier(Edge()).clear(); Parent::getNotifier(UEdge()).clear(); Parent::getNotifier(Node()).clear(); construct(n); Parent::getNotifier(Node()).build(); Parent::getNotifier(UEdge()).build(); Parent::getNotifier(Edge()).build(); } }; class FullBpUGraphBase { protected: int _aNodeNum; int _bNodeNum; int _edgeNum; public: class NodeSetError : public LogicError { virtual const char* exceptionName() const { return "lemon::FullBpUGraph::NodeSetError"; } }; class Node { friend class FullBpUGraphBase; protected: int id; Node(int _id) : id(_id) {} public: Node() {} Node(Invalid) { id = -1; } bool operator==(const Node i) const {return id==i.id;} bool operator!=(const Node i) const {return id!=i.id;} bool operator<(const Node i) const {return id 0) { node.id = 2 * _aNodeNum - 2; } else { node.id = 2 * _bNodeNum - 1; } } void next(Node& node) const { node.id -= 2; if (node.id == -2) { node.id = 2 * _bNodeNum - 1; } } void first(Edge& edge) const { edge.id = _edgeNum - 1; } void next(Edge& edge) const { --edge.id; } void firstOut(Edge& edge, const Node& node) const { LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); edge.id = (node.id >> 1) * _bNodeNum; } void nextOut(Edge& edge) const { ++(edge.id); if (edge.id % _bNodeNum == 0) edge.id = -1; } void firstIn(Edge& edge, const Node& node) const { LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); edge.id = (node.id >> 1); } void nextIn(Edge& edge) const { edge.id += _bNodeNum; if (edge.id >= _edgeNum) edge.id = -1; } static int id(const Node& node) { return node.id; } static Node nodeFromId(int id) { return Node(id); } int maxNodeId() const { return _aNodeNum > _bNodeNum ? _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1; } static int id(const Edge& edge) { return edge.id; } static Edge edgeFromId(int id) { return Edge(id); } int maxEdgeId() const { return _edgeNum - 1; } static int aNodeId(const Node& node) { return node.id >> 1; } static Node fromANodeId(int id, Node) { return Node(id << 1); } int maxANodeId() const { return _aNodeNum; } static int bNodeId(const Node& node) { return node.id >> 1; } static Node fromBNodeId(int id) { return Node((id << 1) + 1); } int maxBNodeId() const { return _bNodeNum; } Node aNode(const Edge& edge) const { return Node((edge.id / _bNodeNum) << 1); } Node bNode(const Edge& edge) const { return Node(((edge.id % _bNodeNum) << 1) + 1); } static bool aNode(const Node& node) { return (node.id & 1) == 0; } static bool bNode(const Node& node) { return (node.id & 1) == 1; } static Node aNode(int index) { return Node(index << 1); } static Node bNode(int index) { return Node((index << 1) + 1); } }; typedef BpUGraphExtender< BpUGraphBaseExtender< FullBpUGraphBase> > ExtendedFullBpUGraphBase; /// \ingroup graphs /// /// \brief An undirected full bipartite graph class. /// /// This is a simple and fast bipartite undirected full graph implementation. /// It is completely static, so you can neither add nor delete either /// edges or nodes. /// /// \sa FullUGraphBase /// \sa FullGraph /// /// \author Balazs Dezso class FullBpUGraph : public ExtendedFullBpUGraphBase { public: typedef ExtendedFullBpUGraphBase Parent; FullBpUGraph() { Parent::construct(0, 0); } FullBpUGraph(int aNodeNum, int bNodeNum) { Parent::construct(aNodeNum, bNodeNum); } /// \brief Resize the graph /// void resize(int n, int m) { Parent::getNotifier(Edge()).clear(); Parent::getNotifier(UEdge()).clear(); Parent::getNotifier(Node()).clear(); Parent::getNotifier(ANode()).clear(); Parent::getNotifier(BNode()).clear(); construct(n, m); Parent::getNotifier(ANode()).build(); Parent::getNotifier(BNode()).build(); Parent::getNotifier(Node()).build(); Parent::getNotifier(UEdge()).build(); Parent::getNotifier(Edge()).build(); } }; } //namespace lemon #endif //LEMON_FULL_GRAPH_H