alpar@956: /* -*- mode: C++; indent-tabs-mode: nil; -*- kpeter@820: * alpar@956: * This file is a part of LEMON, a generic C++ optimization library. kpeter@820: * alpar@956: * Copyright (C) 2003-2010 kpeter@820: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport kpeter@820: * (Egervary Research Group on Combinatorial Optimization, EGRES). kpeter@820: * kpeter@820: * Permission to use, modify and distribute this software is granted kpeter@820: * provided that this copyright notice appears in all copies. For kpeter@820: * precise terms see the accompanying LICENSE file. kpeter@820: * kpeter@820: * This software is provided "AS IS" with no warranty of any kind, kpeter@820: * express or implied, and with no claim as to its suitability for any kpeter@820: * purpose. kpeter@820: * kpeter@820: */ kpeter@820: kpeter@820: #ifndef LEMON_STATIC_GRAPH_H kpeter@820: #define LEMON_STATIC_GRAPH_H kpeter@820: kpeter@820: ///\ingroup graphs kpeter@820: ///\file kpeter@820: ///\brief StaticDigraph class. kpeter@820: kpeter@820: #include kpeter@820: #include kpeter@820: kpeter@820: namespace lemon { kpeter@820: kpeter@820: class StaticDigraphBase { kpeter@820: public: kpeter@820: alpar@956: StaticDigraphBase() alpar@956: : built(false), node_num(0), arc_num(0), kpeter@820: node_first_out(NULL), node_first_in(NULL), alpar@956: arc_source(NULL), arc_target(NULL), kpeter@820: arc_next_in(NULL), arc_next_out(NULL) {} alpar@956: kpeter@820: ~StaticDigraphBase() { kpeter@821: if (built) { kpeter@820: delete[] node_first_out; kpeter@820: delete[] node_first_in; kpeter@820: delete[] arc_source; kpeter@820: delete[] arc_target; kpeter@820: delete[] arc_next_out; kpeter@820: delete[] arc_next_in; kpeter@820: } kpeter@820: } kpeter@820: kpeter@820: class Node { kpeter@820: friend class StaticDigraphBase; kpeter@820: protected: kpeter@820: int id; kpeter@820: Node(int _id) : id(_id) {} kpeter@820: public: kpeter@820: Node() {} kpeter@820: Node (Invalid) : id(-1) {} kpeter@820: bool operator==(const Node& node) const { return id == node.id; } kpeter@820: bool operator!=(const Node& node) const { return id != node.id; } kpeter@820: bool operator<(const Node& node) const { return id < node.id; } kpeter@820: }; kpeter@820: kpeter@820: class Arc { alpar@956: friend class StaticDigraphBase; kpeter@820: protected: kpeter@820: int id; kpeter@820: Arc(int _id) : id(_id) {} kpeter@820: public: kpeter@820: Arc() { } kpeter@820: Arc (Invalid) : id(-1) {} kpeter@820: bool operator==(const Arc& arc) const { return id == arc.id; } kpeter@820: bool operator!=(const Arc& arc) const { return id != arc.id; } kpeter@820: bool operator<(const Arc& arc) const { return id < arc.id; } kpeter@820: }; kpeter@820: kpeter@820: Node source(const Arc& e) const { return Node(arc_source[e.id]); } kpeter@820: Node target(const Arc& e) const { return Node(arc_target[e.id]); } kpeter@820: kpeter@820: void first(Node& n) const { n.id = node_num - 1; } kpeter@820: static void next(Node& n) { --n.id; } kpeter@820: kpeter@820: void first(Arc& e) const { e.id = arc_num - 1; } kpeter@820: static void next(Arc& e) { --e.id; } kpeter@820: alpar@956: void firstOut(Arc& e, const Node& n) const { alpar@956: e.id = node_first_out[n.id] != node_first_out[n.id + 1] ? kpeter@820: node_first_out[n.id] : -1; kpeter@820: } kpeter@820: void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; } kpeter@820: kpeter@820: void firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; } kpeter@820: void nextIn(Arc& e) const { e.id = arc_next_in[e.id]; } kpeter@820: kpeter@825: static int id(const Node& n) { return n.id; } kpeter@825: static Node nodeFromId(int id) { return Node(id); } kpeter@820: int maxNodeId() const { return node_num - 1; } kpeter@820: kpeter@825: static int id(const Arc& e) { return e.id; } kpeter@825: static Arc arcFromId(int id) { return Arc(id); } kpeter@820: int maxArcId() const { return arc_num - 1; } kpeter@820: kpeter@820: typedef True NodeNumTag; kpeter@820: typedef True ArcNumTag; kpeter@820: kpeter@820: int nodeNum() const { return node_num; } kpeter@820: int arcNum() const { return arc_num; } kpeter@820: kpeter@820: private: kpeter@820: kpeter@820: template kpeter@820: class ArcLess { kpeter@820: public: kpeter@820: typedef typename Digraph::Arc Arc; kpeter@820: alpar@956: ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef) kpeter@820: : digraph(_graph), nodeRef(_nodeRef) {} alpar@956: kpeter@820: bool operator()(const Arc& left, const Arc& right) const { alpar@956: return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)]; kpeter@820: } kpeter@820: private: kpeter@820: const Digraph& digraph; kpeter@820: const NodeRefMap& nodeRef; kpeter@820: }; alpar@956: kpeter@820: public: kpeter@820: kpeter@820: typedef True BuildTag; alpar@956: kpeter@821: void clear() { kpeter@821: if (built) { kpeter@820: delete[] node_first_out; kpeter@820: delete[] node_first_in; kpeter@820: delete[] arc_source; kpeter@820: delete[] arc_target; kpeter@820: delete[] arc_next_out; kpeter@820: delete[] arc_next_in; kpeter@820: } kpeter@821: built = false; kpeter@821: node_num = 0; kpeter@821: arc_num = 0; kpeter@821: } alpar@956: kpeter@821: template kpeter@821: void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) { kpeter@820: typedef typename Digraph::Node GNode; kpeter@820: typedef typename Digraph::Arc GArc; kpeter@820: kpeter@821: built = true; kpeter@821: kpeter@820: node_num = countNodes(digraph); kpeter@820: arc_num = countArcs(digraph); kpeter@820: kpeter@820: node_first_out = new int[node_num + 1]; kpeter@820: node_first_in = new int[node_num]; kpeter@820: kpeter@820: arc_source = new int[arc_num]; kpeter@820: arc_target = new int[arc_num]; kpeter@820: arc_next_out = new int[arc_num]; kpeter@820: arc_next_in = new int[arc_num]; kpeter@820: kpeter@820: int node_index = 0; kpeter@820: for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { kpeter@820: nodeRef[n] = Node(node_index); kpeter@820: node_first_in[node_index] = -1; kpeter@820: ++node_index; kpeter@820: } kpeter@820: kpeter@820: ArcLess arcLess(digraph, nodeRef); kpeter@820: kpeter@820: int arc_index = 0; kpeter@820: for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { kpeter@820: int source = nodeRef[n].id; kpeter@820: std::vector arcs; kpeter@820: for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) { kpeter@820: arcs.push_back(e); kpeter@820: } kpeter@820: if (!arcs.empty()) { kpeter@820: node_first_out[source] = arc_index; kpeter@820: std::sort(arcs.begin(), arcs.end(), arcLess); kpeter@820: for (typename std::vector::iterator it = arcs.begin(); kpeter@820: it != arcs.end(); ++it) { kpeter@820: int target = nodeRef[digraph.target(*it)].id; kpeter@820: arcRef[*it] = Arc(arc_index); alpar@956: arc_source[arc_index] = source; kpeter@820: arc_target[arc_index] = target; kpeter@820: arc_next_in[arc_index] = node_first_in[target]; kpeter@820: node_first_in[target] = arc_index; kpeter@820: arc_next_out[arc_index] = arc_index + 1; kpeter@820: ++arc_index; kpeter@820: } kpeter@820: arc_next_out[arc_index - 1] = -1; kpeter@820: } else { kpeter@820: node_first_out[source] = arc_index; kpeter@820: } kpeter@820: } kpeter@820: node_first_out[node_num] = arc_num; kpeter@820: } alpar@956: kpeter@824: template kpeter@824: void build(int n, ArcListIterator first, ArcListIterator last) { kpeter@824: built = true; kpeter@824: kpeter@824: node_num = n; alpar@1328: arc_num = static_cast(std::distance(first, last)); kpeter@824: kpeter@824: node_first_out = new int[node_num + 1]; kpeter@824: node_first_in = new int[node_num]; kpeter@824: kpeter@824: arc_source = new int[arc_num]; kpeter@824: arc_target = new int[arc_num]; kpeter@824: arc_next_out = new int[arc_num]; kpeter@824: arc_next_in = new int[arc_num]; alpar@956: kpeter@824: for (int i = 0; i != node_num; ++i) { kpeter@824: node_first_in[i] = -1; alpar@956: } alpar@956: kpeter@824: int arc_index = 0; kpeter@824: for (int i = 0; i != node_num; ++i) { kpeter@824: node_first_out[i] = arc_index; kpeter@824: for ( ; first != last && (*first).first == i; ++first) { kpeter@824: int j = (*first).second; kpeter@824: LEMON_ASSERT(j >= 0 && j < node_num, kpeter@824: "Wrong arc list for StaticDigraph::build()"); kpeter@824: arc_source[arc_index] = i; kpeter@824: arc_target[arc_index] = j; kpeter@824: arc_next_in[arc_index] = node_first_in[j]; kpeter@824: node_first_in[j] = arc_index; kpeter@824: arc_next_out[arc_index] = arc_index + 1; kpeter@824: ++arc_index; kpeter@824: } kpeter@824: if (arc_index > node_first_out[i]) kpeter@824: arc_next_out[arc_index - 1] = -1; kpeter@824: } kpeter@824: LEMON_ASSERT(first == last, kpeter@824: "Wrong arc list for StaticDigraph::build()"); kpeter@824: node_first_out[node_num] = arc_num; kpeter@824: } kpeter@820: kpeter@820: protected: kpeter@820: kpeter@820: void fastFirstOut(Arc& e, const Node& n) const { kpeter@820: e.id = node_first_out[n.id]; kpeter@820: } kpeter@820: kpeter@820: static void fastNextOut(Arc& e) { kpeter@820: ++e.id; kpeter@820: } kpeter@820: void fastLastOut(Arc& e, const Node& n) const { kpeter@820: e.id = node_first_out[n.id + 1]; kpeter@820: } kpeter@820: kpeter@821: protected: kpeter@821: bool built; kpeter@820: int node_num; kpeter@820: int arc_num; kpeter@820: int *node_first_out; kpeter@820: int *node_first_in; kpeter@820: int *arc_source; kpeter@820: int *arc_target; kpeter@820: int *arc_next_in; kpeter@820: int *arc_next_out; kpeter@820: }; kpeter@820: kpeter@820: typedef DigraphExtender ExtendedStaticDigraphBase; kpeter@820: kpeter@820: kpeter@822: /// \ingroup graphs kpeter@822: /// kpeter@822: /// \brief A static directed graph class. kpeter@822: /// kpeter@822: /// \ref StaticDigraph is a highly efficient digraph implementation, kpeter@822: /// but it is fully static. kpeter@822: /// It stores only two \c int values for each node and only four \c int kpeter@822: /// values for each arc. Moreover it provides faster item iteration than kpeter@822: /// \ref ListDigraph and \ref SmartDigraph, especially using \c OutArcIt kpeter@822: /// iterators, since its arcs are stored in an appropriate order. kpeter@822: /// However it only provides build() and clear() functions and does not kpeter@822: /// support any other modification of the digraph. kpeter@822: /// kpeter@823: /// Since this digraph structure is completely static, its nodes and arcs kpeter@823: /// can be indexed with integers from the ranges [0..nodeNum()-1] alpar@956: /// and [0..arcNum()-1], respectively. kpeter@823: /// The index of an item is the same as its ID, it can be obtained kpeter@823: /// using the corresponding \ref index() or \ref concepts::Digraph::id() kpeter@823: /// "id()" function. A node or arc with a certain index can be obtained kpeter@823: /// using node() or arc(). kpeter@823: /// kpeter@822: /// This type fully conforms to the \ref concepts::Digraph "Digraph concept". kpeter@822: /// Most of its member functions and nested classes are documented kpeter@822: /// only in the concept class. kpeter@822: /// kpeter@834: /// This class provides constant time counting for nodes and arcs. kpeter@834: /// kpeter@822: /// \sa concepts::Digraph kpeter@820: class StaticDigraph : public ExtendedStaticDigraphBase { kpeter@820: public: kpeter@820: kpeter@820: typedef ExtendedStaticDigraphBase Parent; alpar@956: kpeter@821: public: alpar@956: kpeter@823: /// \brief Constructor kpeter@822: /// kpeter@823: /// Default constructor. kpeter@823: StaticDigraph() : Parent() {} kpeter@823: kpeter@823: /// \brief The node with the given index. kpeter@823: /// kpeter@823: /// This function returns the node with the given index. kpeter@823: /// \sa index() kpeter@825: static Node node(int ix) { return Parent::nodeFromId(ix); } kpeter@823: kpeter@823: /// \brief The arc with the given index. kpeter@823: /// kpeter@823: /// This function returns the arc with the given index. kpeter@823: /// \sa index() kpeter@825: static Arc arc(int ix) { return Parent::arcFromId(ix); } kpeter@823: kpeter@823: /// \brief The index of the given node. kpeter@823: /// kpeter@823: /// This function returns the index of the the given node. kpeter@823: /// \sa node() kpeter@825: static int index(Node node) { return Parent::id(node); } kpeter@823: kpeter@823: /// \brief The index of the given arc. kpeter@823: /// kpeter@823: /// This function returns the index of the the given arc. kpeter@823: /// \sa arc() kpeter@825: static int index(Arc arc) { return Parent::id(arc); } kpeter@823: kpeter@823: /// \brief Number of nodes. kpeter@823: /// kpeter@823: /// This function returns the number of nodes. kpeter@823: int nodeNum() const { return node_num; } kpeter@823: kpeter@823: /// \brief Number of arcs. kpeter@823: /// kpeter@823: /// This function returns the number of arcs. kpeter@823: int arcNum() const { return arc_num; } kpeter@823: kpeter@822: /// \brief Build the digraph copying another digraph. kpeter@822: /// kpeter@822: /// This function builds the digraph copying another digraph of any kpeter@822: /// kind. It can be called more than once, but in such case, the whole kpeter@822: /// structure and all maps will be cleared and rebuilt. kpeter@822: /// kpeter@822: /// This method also makes possible to copy a digraph to a StaticDigraph kpeter@822: /// structure using \ref DigraphCopy. alpar@956: /// kpeter@822: /// \param digraph An existing digraph to be copied. kpeter@822: /// \param nodeRef The node references will be copied into this map. kpeter@822: /// Its key type must be \c Digraph::Node and its value type must be kpeter@822: /// \c StaticDigraph::Node. kpeter@822: /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" kpeter@822: /// concept. kpeter@822: /// \param arcRef The arc references will be copied into this map. kpeter@822: /// Its key type must be \c Digraph::Arc and its value type must be kpeter@822: /// \c StaticDigraph::Arc. kpeter@822: /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. kpeter@822: /// kpeter@822: /// \note If you do not need the arc references, then you could use kpeter@822: /// \ref NullMap for the last parameter. However the node references kpeter@822: /// are required by the function itself, thus they must be readable kpeter@822: /// from the map. kpeter@821: template kpeter@821: void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) { kpeter@821: if (built) Parent::clear(); kpeter@821: Parent::build(digraph, nodeRef, arcRef); kpeter@821: } alpar@956: kpeter@824: /// \brief Build the digraph from an arc list. kpeter@824: /// kpeter@824: /// This function builds the digraph from the given arc list. kpeter@824: /// It can be called more than once, but in such case, the whole kpeter@824: /// structure and all maps will be cleared and rebuilt. kpeter@824: /// kpeter@824: /// The list of the arcs must be given in the range [begin, end) kpeter@824: /// specified by STL compatible itartors whose \c value_type must be kpeter@824: /// std::pair. kpeter@824: /// Each arc must be specified by a pair of integer indices kpeter@824: /// from the range [0..n-1]. The pairs must be in a kpeter@824: /// non-decreasing order with respect to their first values. kpeter@824: /// If the k-th pair in the list is (i,j), then kpeter@824: /// arc(k-1) will connect node(i) to node(j). kpeter@824: /// kpeter@824: /// \param n The number of nodes. kpeter@824: /// \param begin An iterator pointing to the beginning of the arc list. kpeter@824: /// \param end An iterator pointing to the end of the arc list. kpeter@824: /// kpeter@824: /// For example, a simple digraph can be constructed like this. kpeter@824: /// \code kpeter@824: /// std::vector > arcs; kpeter@824: /// arcs.push_back(std::make_pair(0,1)); kpeter@824: /// arcs.push_back(std::make_pair(0,2)); kpeter@824: /// arcs.push_back(std::make_pair(1,3)); kpeter@824: /// arcs.push_back(std::make_pair(1,2)); kpeter@824: /// arcs.push_back(std::make_pair(3,0)); kpeter@824: /// StaticDigraph gr; kpeter@824: /// gr.build(4, arcs.begin(), arcs.end()); kpeter@824: /// \endcode kpeter@824: template kpeter@824: void build(int n, ArcListIterator begin, ArcListIterator end) { kpeter@824: if (built) Parent::clear(); kpeter@824: StaticDigraphBase::build(n, begin, end); kpeter@824: notifier(Node()).build(); kpeter@824: notifier(Arc()).build(); kpeter@824: } kpeter@824: kpeter@823: /// \brief Clear the digraph. kpeter@823: /// kpeter@823: /// This function erases all nodes and arcs from the digraph. kpeter@823: void clear() { kpeter@823: Parent::clear(); kpeter@823: } kpeter@820: kpeter@820: protected: kpeter@820: kpeter@820: using Parent::fastFirstOut; kpeter@820: using Parent::fastNextOut; kpeter@820: using Parent::fastLastOut; alpar@956: kpeter@820: public: kpeter@820: kpeter@820: class OutArcIt : public Arc { kpeter@820: public: kpeter@820: kpeter@820: OutArcIt() { } kpeter@820: kpeter@820: OutArcIt(Invalid i) : Arc(i) { } kpeter@820: kpeter@820: OutArcIt(const StaticDigraph& digraph, const Node& node) { alpar@956: digraph.fastFirstOut(*this, node); alpar@956: digraph.fastLastOut(last, node); kpeter@820: if (last == *this) *this = INVALID; kpeter@820: } kpeter@820: kpeter@820: OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) { kpeter@820: if (arc != INVALID) { kpeter@820: digraph.fastLastOut(last, digraph.source(arc)); kpeter@820: } kpeter@820: } kpeter@820: alpar@956: OutArcIt& operator++() { kpeter@820: StaticDigraph::fastNextOut(*this); kpeter@820: if (last == *this) *this = INVALID; alpar@956: return *this; kpeter@820: } kpeter@820: kpeter@820: private: kpeter@820: Arc last; kpeter@820: }; kpeter@820: kpeter@821: Node baseNode(const OutArcIt &arc) const { kpeter@821: return Parent::source(static_cast(arc)); kpeter@821: } kpeter@821: kpeter@821: Node runningNode(const OutArcIt &arc) const { kpeter@821: return Parent::target(static_cast(arc)); kpeter@821: } kpeter@821: kpeter@821: Node baseNode(const InArcIt &arc) const { kpeter@821: return Parent::target(static_cast(arc)); kpeter@821: } kpeter@821: kpeter@821: Node runningNode(const InArcIt &arc) const { kpeter@821: return Parent::source(static_cast(arc)); kpeter@821: } kpeter@821: kpeter@820: }; kpeter@820: kpeter@820: } kpeter@820: kpeter@820: #endif