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