lemon-0.x: comparison lemon/min_cost

equal deleted inserted replaced

--1:000000000000
+:88bf8b76d70e
+/* -*- 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_MIN_COST_ARBORESCENCE_H
+#define LEMON_MIN_COST_ARBORESCENCE_H
+///\ingroup spantree
+///\file
+///\brief Minimum Cost Arborescence algorithm.
+#include <vector>
+#include <lemon/list_graph.h>
+namespace lemon {
+/// \brief Default traits class of MinCostArborescence class.
+///
+/// Default traits class of MinCostArborescence class.
+/// \param _Graph Graph type.
+/// \param _CostMap Type of cost map.
+template <class _Graph, class _CostMap>
+struct MinCostArborescenceDefaultTraits{
+/// \brief The graph type the algorithm runs on.
+typedef _Graph Graph;
+/// \brief The type of the map that stores the edge costs.
+///
+/// The type of the map that stores the edge costs.
+/// It must meet the \ref concept::ReadMap "ReadMap" concept.
+typedef _CostMap CostMap;
+/// \brief The value type of the costs.
+///
+/// The value type of the costs.
+typedef typename CostMap::Value Value;
+/// \brief The type of the map that stores which edges are
+/// in the arborescence.
+///
+/// The type of the map that stores which edges are in the arborescence.
+/// It must meet the \ref concept::ReadWriteMap "ReadWriteMap" concept.
+/// Initially it will be setted to false on each edge. The algorithm
+/// may set each value one time to true and maybe after it to false again.
+/// Therefore you cannot use maps like BackInserteBoolMap with this
+/// algorithm.
+typedef typename Graph::template EdgeMap<bool> ArborescenceMap;
+/// \brief Instantiates a ArborescenceMap.
+///
+/// This function instantiates a \ref ArborescenceMap.
+/// \param _graph is the graph, to which we would like to define the
+/// ArborescenceMap.
+static ArborescenceMap *createArborescenceMap(const Graph &_graph){
+return new ArborescenceMap(_graph);
+}
+};
+/// \ingroup spantree
+///
+/// \brief %MinCostArborescence algorithm class.
+///
+/// This class provides an efficient implementation of
+/// %MinCostArborescence algorithm. The arborescence is a tree
+/// which is directed from a given source node of the graph. One or
+/// more sources should be given for the algorithm and it will calculate
+/// the minimum cost subgraph which are union of arborescences with the
+/// given sources and spans all the nodes which are reachable from the
+/// sources. The time complexity of the algorithm is O(n^2 + e).
+///
+/// \param _Graph The graph type the algorithm runs on. The default value
+/// is \ref ListGraph. The value of _Graph is not used directly by
+/// MinCostArborescence, it is only passed to
+/// \ref MinCostArborescenceDefaultTraits.
+/// \param _CostMap This read-only EdgeMap determines the costs of the
+/// edges. It is read once for each edge, so the map may involve in
+/// relatively time consuming process to compute the edge cost if
+/// it is necessary. The default map type is \ref
+/// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
+/// of _CostMap is not used directly by MinCostArborescence,
+/// it is only passed to \ref MinCostArborescenceDefaultTraits.
+/// \param _Traits Traits class to set various data types used
+/// by the algorithm.  The default traits class is
+/// \ref MinCostArborescenceDefaultTraits
+/// "MinCostArborescenceDefaultTraits<_Graph,_CostMap>".  See \ref
+/// MinCostArborescenceDefaultTraits for the documentation of a
+/// MinCostArborescence traits class.
+///
+/// \author Balazs Dezso
+#ifndef DOXYGEN
+template <typename _Graph = ListGraph,
+typename _CostMap = typename _Graph::template EdgeMap<int>,
+typename _Traits =
+MinCostArborescenceDefaultTraits<_Graph, _CostMap> >
+#else
+template <typename _Graph, typename _CostMap, typedef _Traits>
+#endif
+class MinCostArborescence {
+public:
+/// \brief \ref Exception for uninitialized parameters.
+///
+/// This error represents problems in the initialization
+/// of the parameters of the algorithms.
+class UninitializedParameter : public lemon::UninitializedParameter {
+public:
+virtual const char* exceptionName() const {
+	return "lemon::MinCostArborescence::UninitializedParameter";
+}
+};
+/// The traits.
+typedef _Traits Traits;
+/// The type of the underlying graph.
+typedef typename Traits::Graph Graph;
+/// The type of the map that stores the edge costs.
+typedef typename Traits::CostMap CostMap;
+///The type of the costs of the edges.
+typedef typename Traits::Value Value;
+///The type of the map that stores which edges are in the arborescence.
+typedef typename Traits::ArborescenceMap ArborescenceMap;
+protected:
+typedef typename Graph::Node Node;
+typedef typename Graph::Edge Edge;
+typedef typename Graph::NodeIt NodeIt;
+typedef typename Graph::EdgeIt EdgeIt;
+typedef typename Graph::InEdgeIt InEdgeIt;
+typedef typename Graph::OutEdgeIt OutEdgeIt;
+struct CostEdge {
+Edge edge;
+Value value;
+CostEdge() {}
+CostEdge(Edge _edge, Value _value) : edge(_edge), value(_value) {}
+};
+const Graph* graph;
+const CostMap* cost;
+ArborescenceMap* _arborescence_map;
+bool local_arborescence_map;
+typedef typename Graph::template NodeMap<int> LevelMap;
+LevelMap *_level;
+typedef typename Graph::template NodeMap<CostEdge> CostEdgeMap;
+CostEdgeMap *_cost_edges;
+struct StackLevel {
+std::vector<CostEdge> edges;
+int node_level;
+};
+std::vector<StackLevel> level_stack;
+std::vector<Node> queue;
+int node_counter;
+public:
+/// \name Named template parameters
+/// @{
+template <class T>
+struct DefArborescenceMapTraits : public Traits {
+typedef T ArborescenceMap;
+static ArborescenceMap *createArborescenceMap(const Graph &)
+{
+	throw UninitializedParameter();
+}
+};
+/// \brief \ref named-templ-param "Named parameter" for
+/// setting ArborescenceMap type
+///
+/// \ref named-templ-param "Named parameter" for setting
+/// ArborescenceMap type
+template <class T>
+struct DefArborescenceMap
+: public MinCostArborescence<Graph, CostMap,
+DefArborescenceMapTraits<T> > {
+typedef MinCostArborescence<Graph, CostMap,
+DefArborescenceMapTraits<T> > Create;
+};
+/// @}
+/// \brief Constructor.
+///
+/// \param _graph The graph the algorithm will run on.
+/// \param _cost The cost map used by the algorithm.
+MinCostArborescence(const Graph& _graph, const CostMap& _cost)
+: graph(&_graph), cost(&_cost),
+_arborescence_map(0), local_arborescence_map(false),
+_level(0), _cost_edges(0) {}
+/// \brief Destructor.
+~MinCostArborescence() {
+destroyStructures();
+}
+/// \brief Sets the arborescence map.
+///
+/// Sets the arborescence map.
+/// \return \c (*this)
+MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
+_arborescence_map = &m;
+return *this;
+}
+/// \name Query Functions
+/// The result of the %MinCostArborescence algorithm can be obtained
+/// using these functions.\n
+/// Before the use of these functions,
+/// either run() or start() must be called.
+/// @{
+/// \brief Returns a reference to the arborescence map.
+///
+/// Returns a reference to the arborescence map.
+const ArborescenceMap& arborescenceMap() const {
+return *_arborescence_map;
+}
+/// \brief Returns true if the edge is in the arborescence.
+///
+/// Returns true if the edge is in the arborescence.
+/// \param edge The edge of the graph.
+/// \pre \ref run() must be called before using this function.
+bool arborescenceEdge(Edge edge) const {
+return (*_arborescence_map)[edge];
+}
+/// \brief Returns the cost of the arborescence.
+///
+/// Returns the cost of the arborescence.
+Value arborescenceCost() const {
+Value sum = 0;
+for (EdgeIt it(*graph); it != INVALID; ++it) {
+if (arborescenceEdge(it)) {
+sum += (*cost)[it];
+}
+}
+return sum;
+}
+/// @}
+/// \name Execution control
+/// The simplest way to execute the algorithm is to use
+/// one of the member functions called \c run(...). \n
+/// If you need more control on the execution,
+/// first you must call \ref init(), then you can add several
+/// source nodes with \ref addSource().
+/// Finally \ref start() will perform the actual path
+/// computation.
+///@{
+/// \brief Initializes the internal data structures.
+///
+/// Initializes the internal data structures.
+///
+void init() {
+initStructures();
+for (NodeIt it(*graph); it != INVALID; ++it) {
+(*_cost_edges)[it].edge = INVALID;
+(*_level)[it] = -3;
+}
+for (EdgeIt it(*graph); it != INVALID; ++it) {
+_arborescence_map->set(it, false);
+}
+}
+/// \brief Adds a new source node.
+///
+/// Adds a new source node to the algorithm.
+void addSource(Node source) {
+std::vector<Node> nodes;
+nodes.push_back(source);
+while (!nodes.empty()) {
+Node node = nodes.back();
+nodes.pop_back();
+for (OutEdgeIt it(*graph, node); it != INVALID; ++it) {
+if ((*_level)[graph->target(it)] == -3) {
+(*_level)[graph->target(it)] = -2;
+nodes.push_back(graph->target(it));
+queue.push_back(graph->target(it));
+}
+}
+}
+(*_level)[source] = -1;
+}
+/// \brief Processes the next node in the priority queue.
+///
+/// Processes the next node in the priority queue.
+///
+/// \return The processed node.
+///
+/// \warning The queue must not be empty!
+Node processNextNode() {
+node_counter = 0;
+Node node = queue.back();
+queue.pop_back();
+if ((*_level)[node] == -2) {
+Edge edge = prepare(node);
+while ((*_level)[graph->source(edge)] != -1) {
+if ((*_level)[graph->source(edge)] >= 0) {
+edge = contract(bottom((*_level)[graph->source(edge)]));
+} else {
+edge = prepare(graph->source(edge));
+}
+}
+finalize(graph->target(edge));
+level_stack.clear();
+}
+return node;
+}
+/// \brief Returns the number of the nodes to be processed.
+///
+/// Returns the number of the nodes to be processed.
+int queueSize() const {
+return queue.size();
+}
+/// \brief Returns \c false if there are nodes to be processed.
+///
+/// Returns \c false if there are nodes to be processed.
+bool emptyQueue() const {
+return queue.empty();
+}
+/// \brief Executes the algorithm.
+///
+/// Executes the algorithm.
+///
+/// \pre init() must be called and at least one node should be added
+/// with addSource() before using this function.
+///
+///\note mca.start() is just a shortcut of the following code.
+///\code
+///while (!mca.emptyQueue()) {
+///  mca.processNextNode();
+///}
+///\endcode
+void start() {
+while (!emptyQueue()) {
+processNextNode();
+}
+}
+/// \brief Runs %MinCostArborescence algorithm from node \c s.
+///
+/// This method runs the %MinCostArborescence algorithm from
+/// a root node \c s.
+///
+///\note mca.run(s) is just a shortcut of the following code.
+///\code
+///mca.init();
+///mca.addSource(s);
+///mca.start();
+///\endcode
+void run(Node node) {
+init();
+addSource(node);
+start();
+}
+///@}
+protected:
+void initStructures() {
+if (!_arborescence_map) {
+local_arborescence_map = true;
+_arborescence_map = Traits::createArborescenceMap(*graph);
+}
+if (!_level) {
+_level = new LevelMap(*graph);
+}
+if (!_cost_edges) {
+_cost_edges = new CostEdgeMap(*graph);
+}
+}
+void destroyStructures() {
+if (_level) {
+delete _level;
+}
+if (!_cost_edges) {
+delete _cost_edges;
+}
+if (local_arborescence_map) {
+delete _arborescence_map;
+}
+}
+Edge prepare(Node node) {
+std::vector<Node> nodes;
+(*_level)[node] = node_counter;
+for (InEdgeIt it(*graph, node); it != INVALID; ++it) {
+Edge edge = it;
+Value value = (*cost)[it];
+if (graph->source(edge) == node ||
+(*_level)[graph->source(edge)] == -3) continue;
+if ((*_cost_edges)[graph->source(edge)].edge == INVALID) {
+(*_cost_edges)[graph->source(edge)].edge = edge;
+(*_cost_edges)[graph->source(edge)].value = value;
+nodes.push_back(graph->source(edge));
+} else {
+if ((*_cost_edges)[graph->source(edge)].value > value) {
+(*_cost_edges)[graph->source(edge)].edge = edge;
+(*_cost_edges)[graph->source(edge)].value = value;
+}
+}
+}
+CostEdge minimum = (*_cost_edges)[nodes[0]];
+for (int i = 1; i < (int)nodes.size(); ++i) {
+if ((*_cost_edges)[nodes[i]].value < minimum.value) {
+minimum = (*_cost_edges)[nodes[i]];
+}
+}
+StackLevel level;
+level.node_level = node_counter;
+for (int i = 0; i < (int)nodes.size(); ++i) {
+(*_cost_edges)[nodes[i]].value -= minimum.value;
+level.edges.push_back((*_cost_edges)[nodes[i]]);
+(*_cost_edges)[nodes[i]].edge = INVALID;
+}
+level_stack.push_back(level);
+++node_counter;
+_arborescence_map->set(minimum.edge, true);
+return minimum.edge;
+}
+Edge contract(int node_bottom) {
+std::vector<Node> nodes;
+while (!level_stack.empty() &&
+level_stack.back().node_level >= node_bottom) {
+for (int i = 0; i < (int)level_stack.back().edges.size(); ++i) {
+Edge edge = level_stack.back().edges[i].edge;
+Value value = level_stack.back().edges[i].value;
+if ((*_level)[graph->source(edge)] >= node_bottom) continue;
+if ((*_cost_edges)[graph->source(edge)].edge == INVALID) {
+(*_cost_edges)[graph->source(edge)].edge = edge;
+(*_cost_edges)[graph->source(edge)].value = value;
+nodes.push_back(graph->source(edge));
+} else {
+if ((*_cost_edges)[graph->source(edge)].value > value) {
+(*_cost_edges)[graph->source(edge)].edge = edge;
+(*_cost_edges)[graph->source(edge)].value = value;
+}
+}
+}
+level_stack.pop_back();
+}
+CostEdge minimum = (*_cost_edges)[nodes[0]];
+for (int i = 1; i < (int)nodes.size(); ++i) {
+if ((*_cost_edges)[nodes[i]].value < minimum.value) {
+minimum = (*_cost_edges)[nodes[i]];
+}
+}
+StackLevel level;
+level.node_level = node_bottom;
+for (int i = 0; i < (int)nodes.size(); ++i) {
+(*_cost_edges)[nodes[i]].value -= minimum.value;
+level.edges.push_back((*_cost_edges)[nodes[i]]);
+(*_cost_edges)[nodes[i]].edge = INVALID;
+}
+level_stack.push_back(level);
+_arborescence_map->set(minimum.edge, true);
+return minimum.edge;
+}
+int bottom(int level) {
+int k = level_stack.size() - 1;
+while (level_stack[k].node_level > level) {
+--k;
+}
+return level_stack[k].node_level;
+}
+void finalize(Node source) {
+std::vector<Node> nodes;
+nodes.push_back(source);
+while (!nodes.empty()) {
+Node node = nodes.back();
+nodes.pop_back();
+for (OutEdgeIt it(*graph, node); it != INVALID; ++it) {
+if ((*_level)[graph->target(it)] >= 0 && (*_arborescence_map)[it]) {
+(*_level)[graph->target(it)] = -1;
+nodes.push_back(graph->target(it));
+} else {
+_arborescence_map->set(it, false);
+}
+}
+}
+(*_level)[source] = -1;
+}
+};
+/// \ingroup spantree
+///
+/// \brief Function type interface for MinCostArborescence algorithm.
+///
+/// Function type interface for MinCostArborescence algorithm.
+/// \param graph The Graph that the algorithm runs on.
+/// \param cost The CostMap of the edges.
+/// \param source The source of the arborescence.
+/// \retval arborescence The bool EdgeMap which stores the arborescence.
+/// \return The cost of the arborescence.
+///
+/// \sa MinCostArborescence
+template <typename Graph, typename CostMap, typename ArborescenceMap>
+typename CostMap::Value minCostArborescence(const Graph& graph,
+const CostMap& cost,
+typename Graph::Node source,
+ArborescenceMap& arborescence) {
+typename MinCostArborescence<Graph, CostMap>
+::template DefArborescenceMap<ArborescenceMap>
+::Create mca(graph, cost);
+mca.arborescenceMap(arborescence);
+mca.run(source);
+return mca.arborescenceCost();
+}
+}
+#endif
+// Hilbert - Huang

changeset 2020	332245399dc6
child 2025	93fcadf94ab0