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