Differential D5594 Diff 18104 extern/quadriflow/3rd/lemon-1.3.1/lemon/static_graph.h

Changeset View

Standalone View

extern/quadriflow/3rd/lemon-1.3.1/lemon/static_graph.h

This file was added.

				/* -- mode: C++; indent-tabs-mode: nil; --
				*
				* This file is a part of LEMON, a generic C++ optimization library.
				*
				* Copyright (C) 2003-2010
				* 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_STATIC_GRAPH_H
				#define LEMON_STATIC_GRAPH_H

				///\ingroup graphs
				///\file
				///\brief StaticDigraph class.

				#include <lemon/core.h>
				#include <lemon/bits/graph_extender.h>

				namespace lemon {

				class StaticDigraphBase {
				public:

				StaticDigraphBase()
				: built(false), node_num(0), arc_num(0),
				node_first_out(NULL), node_first_in(NULL),
				arc_source(NULL), arc_target(NULL),
				arc_next_in(NULL), arc_next_out(NULL) {}

				~StaticDigraphBase() {
				if (built) {
				delete[] node_first_out;
				delete[] node_first_in;
				delete[] arc_source;
				delete[] arc_target;
				delete[] arc_next_out;
				delete[] arc_next_in;
				}
				}

				class Node {
				friend class StaticDigraphBase;
				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 Arc {
				friend class StaticDigraphBase;
				protected:
				int id;
				Arc(int _id) : id(_id) {}
				public:
				Arc() { }
				Arc (Invalid) : id(-1) {}
				bool operator==(const Arc& arc) const { return id == arc.id; }
				bool operator!=(const Arc& arc) const { return id != arc.id; }
				bool operator<(const Arc& arc) const { return id < arc.id; }
				};

				Node source(const Arc& e) const { return Node(arc_source[e.id]); }
				Node target(const Arc& e) const { return Node(arc_target[e.id]); }

				void first(Node& n) const { n.id = node_num - 1; }
				static void next(Node& n) { --n.id; }

				void first(Arc& e) const { e.id = arc_num - 1; }
				static void next(Arc& e) { --e.id; }

				void firstOut(Arc& e, const Node& n) const {
				e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
				node_first_out[n.id] : -1;
				}
				void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }

				void firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; }
				void nextIn(Arc& e) const { e.id = arc_next_in[e.id]; }

				static int id(const Node& n) { return n.id; }
				static Node nodeFromId(int id) { return Node(id); }
				int maxNodeId() const { return node_num - 1; }

				static int id(const Arc& e) { return e.id; }
				static Arc arcFromId(int id) { return Arc(id); }
				int maxArcId() const { return arc_num - 1; }

				typedef True NodeNumTag;
				typedef True ArcNumTag;

				int nodeNum() const { return node_num; }
				int arcNum() const { return arc_num; }

				private:

				template <typename Digraph, typename NodeRefMap>
				class ArcLess {
				public:
				typedef typename Digraph::Arc Arc;

				ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
				: digraph(_graph), nodeRef(_nodeRef) {}

				bool operator()(const Arc& left, const Arc& right) const {
				return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
				}
				private:
				const Digraph& digraph;
				const NodeRefMap& nodeRef;
				};

				public:

				typedef True BuildTag;

				void clear() {
				if (built) {
				delete[] node_first_out;
				delete[] node_first_in;
				delete[] arc_source;
				delete[] arc_target;
				delete[] arc_next_out;
				delete[] arc_next_in;
				}
				built = false;
				node_num = 0;
				arc_num = 0;
				}

				template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
				void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
				typedef typename Digraph::Node GNode;
				typedef typename Digraph::Arc GArc;

				built = true;

				node_num = countNodes(digraph);
				arc_num = countArcs(digraph);

				node_first_out = new int[node_num + 1];
				node_first_in = new int[node_num];

				arc_source = new int[arc_num];
				arc_target = new int[arc_num];
				arc_next_out = new int[arc_num];
				arc_next_in = new int[arc_num];

				int node_index = 0;
				for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
				nodeRef[n] = Node(node_index);
				node_first_in[node_index] = -1;
				++node_index;
				}

				ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);

				int arc_index = 0;
				for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
				int source = nodeRef[n].id;
				std::vector<GArc> arcs;
				for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {
				arcs.push_back(e);
				}
				if (!arcs.empty()) {
				node_first_out[source] = arc_index;
				std::sort(arcs.begin(), arcs.end(), arcLess);
				for (typename std::vector<GArc>::iterator it = arcs.begin();
				it != arcs.end(); ++it) {
				int target = nodeRef[digraph.target(*it)].id;
				arcRef[*it] = Arc(arc_index);
				arc_source[arc_index] = source;
				arc_target[arc_index] = target;
				arc_next_in[arc_index] = node_first_in[target];
				node_first_in[target] = arc_index;
				arc_next_out[arc_index] = arc_index + 1;
				++arc_index;
				}
				arc_next_out[arc_index - 1] = -1;
				} else {
				node_first_out[source] = arc_index;
				}
				}
				node_first_out[node_num] = arc_num;
				}

				template <typename ArcListIterator>
				void build(int n, ArcListIterator first, ArcListIterator last) {
				built = true;

				node_num = n;
				arc_num = std::distance(first, last);

				node_first_out = new int[node_num + 1];
				node_first_in = new int[node_num];

				arc_source = new int[arc_num];
				arc_target = new int[arc_num];
				arc_next_out = new int[arc_num];
				arc_next_in = new int[arc_num];

				for (int i = 0; i != node_num; ++i) {
				node_first_in[i] = -1;
				}

				int arc_index = 0;
				for (int i = 0; i != node_num; ++i) {
				node_first_out[i] = arc_index;
				for ( ; first != last && (*first).first == i; ++first) {
				int j = (*first).second;
				LEMON_ASSERT(j >= 0 && j < node_num,
				"Wrong arc list for StaticDigraph::build()");
				arc_source[arc_index] = i;
				arc_target[arc_index] = j;
				arc_next_in[arc_index] = node_first_in[j];
				node_first_in[j] = arc_index;
				arc_next_out[arc_index] = arc_index + 1;
				++arc_index;
				}
				if (arc_index > node_first_out[i])
				arc_next_out[arc_index - 1] = -1;
				}
				LEMON_ASSERT(first == last,
				"Wrong arc list for StaticDigraph::build()");
				node_first_out[node_num] = arc_num;
				}

				protected:

				void fastFirstOut(Arc& e, const Node& n) const {
				e.id = node_first_out[n.id];
				}

				static void fastNextOut(Arc& e) {
				++e.id;
				}
				void fastLastOut(Arc& e, const Node& n) const {
				e.id = node_first_out[n.id + 1];
				}

				protected:
				bool built;
				int node_num;
				int arc_num;
				int *node_first_out;
				int *node_first_in;
				int *arc_source;
				int *arc_target;
				int *arc_next_in;
				int *arc_next_out;
				};

				typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase;


				/// \ingroup graphs
				///
				/// \brief A static directed graph class.
				///
				/// \ref StaticDigraph is a highly efficient digraph implementation,
				/// but it is fully static.
				/// It stores only two \c int values for each node and only four \c int
				/// values for each arc. Moreover it provides faster item iteration than
				/// \ref ListDigraph and \ref SmartDigraph, especially using \c OutArcIt
				/// iterators, since its arcs are stored in an appropriate order.
				/// However it only provides build() and clear() functions and does not
				/// support any other modification of the digraph.
				///
				/// Since this digraph structure is completely static, its nodes and arcs
				/// can be indexed with integers from the ranges <tt>[0..nodeNum()-1]</tt>
				/// and <tt>[0..arcNum()-1]</tt>, respectively.
				/// The index of an item is the same as its ID, it can be obtained
				/// using the corresponding \ref index() or \ref concepts::Digraph::id()
				/// "id()" function. A node or arc with a certain index can be obtained
				/// using node() or arc().
				///
				/// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
				/// Most of its member functions and nested classes are documented
				/// only in the concept class.
				///
				/// This class provides constant time counting for nodes and arcs.
				///
				/// \sa concepts::Digraph
				class StaticDigraph : public ExtendedStaticDigraphBase {
				public:

				typedef ExtendedStaticDigraphBase Parent;

				public:

				/// \brief Constructor
				///
				/// Default constructor.
				StaticDigraph() : Parent() {}

				/// \brief The node with the given index.
				///
				/// This function returns the node with the given index.
				/// \sa index()
				static Node node(int ix) { return Parent::nodeFromId(ix); }

				/// \brief The arc with the given index.
				///
				/// This function returns the arc with the given index.
				/// \sa index()
				static Arc arc(int ix) { return Parent::arcFromId(ix); }

				/// \brief The index of the given node.
				///
				/// This function returns the index of the the given node.
				/// \sa node()
				static int index(Node node) { return Parent::id(node); }

				/// \brief The index of the given arc.
				///
				/// This function returns the index of the the given arc.
				/// \sa arc()
				static int index(Arc arc) { return Parent::id(arc); }

				/// \brief Number of nodes.
				///
				/// This function returns the number of nodes.
				int nodeNum() const { return node_num; }

				/// \brief Number of arcs.
				///
				/// This function returns the number of arcs.
				int arcNum() const { return arc_num; }

				/// \brief Build the digraph copying another digraph.
				///
				/// This function builds the digraph copying another digraph of any
				/// kind. It can be called more than once, but in such case, the whole
				/// structure and all maps will be cleared and rebuilt.
				///
				/// This method also makes possible to copy a digraph to a StaticDigraph
				/// structure using \ref DigraphCopy.
				///
				/// \param digraph An existing digraph to be copied.
				/// \param nodeRef The node references will be copied into this map.
				/// Its key type must be \c Digraph::Node and its value type must be
				/// \c StaticDigraph::Node.
				/// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
				/// concept.
				/// \param arcRef The arc references will be copied into this map.
				/// Its key type must be \c Digraph::Arc and its value type must be
				/// \c StaticDigraph::Arc.
				/// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
				///
				/// \note If you do not need the arc references, then you could use
				/// \ref NullMap for the last parameter. However the node references
				/// are required by the function itself, thus they must be readable
				/// from the map.
				template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
				void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
				if (built) Parent::clear();
				Parent::build(digraph, nodeRef, arcRef);
				}

				/// \brief Build the digraph from an arc list.
				///
				/// This function builds the digraph from the given arc list.
				/// It can be called more than once, but in such case, the whole
				/// structure and all maps will be cleared and rebuilt.
				///
				/// The list of the arcs must be given in the range <tt>[begin, end)</tt>
				/// specified by STL compatible itartors whose \c value_type must be
				/// <tt>std::pair<int,int></tt>.
				/// Each arc must be specified by a pair of integer indices
				/// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a
				/// non-decreasing order with respect to their first values.</i>
				/// If the k-th pair in the list is <tt>(i,j)</tt>, then
				/// <tt>arc(k-1)</tt> will connect <tt>node(i)</tt> to <tt>node(j)</tt>.
				///
				/// \param n The number of nodes.
				/// \param begin An iterator pointing to the beginning of the arc list.
				/// \param end An iterator pointing to the end of the arc list.
				///
				/// For example, a simple digraph can be constructed like this.
				/// \code
				/// std::vector<std::pair<int,int> > arcs;
				/// arcs.push_back(std::make_pair(0,1));
				/// arcs.push_back(std::make_pair(0,2));
				/// arcs.push_back(std::make_pair(1,3));
				/// arcs.push_back(std::make_pair(1,2));
				/// arcs.push_back(std::make_pair(3,0));
				/// StaticDigraph gr;
				/// gr.build(4, arcs.begin(), arcs.end());
				/// \endcode
				template <typename ArcListIterator>
				void build(int n, ArcListIterator begin, ArcListIterator end) {
				if (built) Parent::clear();
				StaticDigraphBase::build(n, begin, end);
				notifier(Node()).build();
				notifier(Arc()).build();
				}

				/// \brief Clear the digraph.
				///
				/// This function erases all nodes and arcs from the digraph.
				void clear() {
				Parent::clear();
				}

				protected:

				using Parent::fastFirstOut;
				using Parent::fastNextOut;
				using Parent::fastLastOut;

				public:

				class OutArcIt : public Arc {
				public:

				OutArcIt() { }

				OutArcIt(Invalid i) : Arc(i) { }

				OutArcIt(const StaticDigraph& digraph, const Node& node) {
				digraph.fastFirstOut(*this, node);
				digraph.fastLastOut(last, node);
				if (last == this) this = INVALID;
				}

				OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
				if (arc != INVALID) {
				digraph.fastLastOut(last, digraph.source(arc));
				}
				}

				OutArcIt& operator++() {
				StaticDigraph::fastNextOut(*this);
				if (last == this) this = INVALID;
				return *this;
				}

				private:
				Arc last;
				};

				Node baseNode(const OutArcIt &arc) const {
				return Parent::source(static_cast<const Arc&>(arc));
				}

				Node runningNode(const OutArcIt &arc) const {
				return Parent::target(static_cast<const Arc&>(arc));
				}

				Node baseNode(const InArcIt &arc) const {
				return Parent::target(static_cast<const Arc&>(arc));
				}

				Node runningNode(const InArcIt &arc) const {
				return Parent::source(static_cast<const Arc&>(arc));
				}

				};

				}

				#endif