# Changeset 2337:9c3d44ac39fb in lemon-0.x

Ignore:
Timestamp:
01/11/07 22:05:00 (17 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3129
Message:

Based on:
http://www.avglab.com/andrew/pub/neci-tr-96-132.ps

File:
1 edited

### Legend:

Unmodified
 r2284 */ #ifndef LEMON_MIN_CUT_H #define LEMON_MIN_CUT_H /// \ingroup topology /// \file /// \brief Maximum cardinality search and min cut in undirected graphs. #ifndef LEMON_NAGAMOCHI_IBARAKI_H #define LEMON_NAGAMOCHI_IBARAKI_H /// \ingroup topology /// \file /// \brief Maximum cardinality search and minimum cut in undirected /// graphs. #include #include #include #include #include #include #include #include #include namespace lemon { return new CardinalityMap(graph); } }; Value cardinality(Node node) const { return (*_cardinality)[node]; } /// \brief The current cardinality of a node. /// /// Returns the current cardinality of a node. /// \pre the given node should be reached but not processed Value currentCardinality(Node node) const { return (*_heap)[node]; } /// \brief Returns a reference to the NodeMap of cardinalities. /// } /// \brief The CutValueMap type /// /// The type of the map that stores the cut value of a node. typedef AuxGraph::NodeMap AuxCutValueMap; /// \brief Instantiates a AuxCutValueMap. /// /// This function instantiates a \ref AuxCutValueMap. static AuxCutValueMap *createAuxCutValueMap(const AuxGraph& graph) { return new AuxCutValueMap(graph); } /// \brief The AuxCapacityMap type /// /// The type of the map that stores the auxing edge capacities. /// The type of the map that stores the auxiliary edge capacities. typedef AuxGraph::UEdgeMap AuxCapacityMap; }; namespace _min_cut_bits { template class LastTwoMap { public: typedef _Key Key; typedef bool Value; LastTwoMap(int _num) : num(_num) {} void set(const Key& key, bool val) { if (!val) return; --num; if (num > 1) return; keys[num] = key; } Key operator[](int index) const { return keys[index]; } private: Key keys[2]; int num; }; } /// \ingroup topology /// /// The complexity of the algorithm is \f$O(ne\log(n)) \f$ but with /// Fibonacci heap it can be decreased to \f$O(ne+n^2\log(n)) /// \f$. When capacity map is neutral then it uses BucketHeap which /// Fibonacci heap it can be decreased to \f$O(ne+n^2\log(n)) \f$. /// When capacity map is neutral then it uses BucketHeap which /// results \f$O(ne) \f$ time complexity. /// /// \warning The value type of the capacity map should be able to hold /// any cut value of the graph, otherwise the result can overflow. #ifdef DOXYGEN template /// The type of the aux capacity map typedef typename Traits::AuxCapacityMap AuxCapacityMap; /// The type of the aux cut value map typedef typename Traits::AuxCutValueMap AuxCutValueMap; /// The cross reference type used for the current heap. typedef typename Traits::HeapCrossRef HeapCrossRef; /// (\c true) or not. bool local_aux_capacity; /// Pointer to the aux cut value map AuxCutValueMap *_aux_cut_value; /// \brief Indicates if \ref _aux_cut_value is locally allocated /// (\c true) or not. bool local_aux_cut_value; /// Pointer to the heap cross references. HeapCrossRef *_heap_cross_ref; /// The number of the nodes of the aux graph. int _node_num; /// The first and last node of the min cut in the next list; typename Graph::Node _first_node, _last_node; /// The first and last node of the min cut in the next list. std::vector _cut; /// \brief The first and last element in the list associated ListRefMap *_next; void create_structures() { void createStructures() { if (!_capacity) { local_capacity = true; _aux_capacity = Traits::createAuxCapacityMap(*_aux_graph); } if(!_aux_cut_value) { local_aux_cut_value = true; _aux_cut_value = Traits::createAuxCutValueMap(*_aux_graph); } _first = Traits::createNodeRefMap(*_aux_graph); _next = Traits::createListRefMap(*_graph); typename Graph::template NodeMap ref(*_graph); for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) { _next->set(it, INVALID); typename AuxGraph::Node node = _aux_graph->addNode(); _first->set(node, it); _last->set(node, it); ref.set(it, node); } for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) { if (_graph->source(it) == _graph->target(it)) continue; typename AuxGraph::UEdge uedge = _aux_graph->addEdge(ref[_graph->source(it)], ref[_graph->target(it)]); _aux_capacity->set(uedge, (*_capacity)[it]); } if (!_heap_cross_ref) { } } void createAuxGraph() { typename Graph::template NodeMap ref(*_graph); for (typename Graph::NodeIt n(*_graph); n != INVALID; ++n) { _next->set(n, INVALID); typename AuxGraph::Node node = _aux_graph->addNode(); _first->set(node, n); _last->set(node, n); ref.set(n, node); } typename AuxGraph::template NodeMap edges(*_aux_graph, INVALID); for (typename Graph::NodeIt n(*_graph); n != INVALID; ++n) { for (typename Graph::IncEdgeIt e(*_graph, n); e != INVALID; ++e) { typename Graph::Node tn = _graph->runningNode(e); if (n < tn || n == tn) continue; if (edges[ref[tn]] != INVALID) { Value value = (*_aux_capacity)[edges[ref[tn]]] + (*_capacity)[e]; _aux_capacity->set(edges[ref[tn]], value); } else { edges.set(ref[tn], _aux_graph->addEdge(ref[n], ref[tn])); Value value = (*_capacity)[e]; _aux_capacity->set(edges[ref[tn]], value); } } for (typename Graph::IncEdgeIt e(*_graph, n); e != INVALID; ++e) { typename Graph::Node tn = _graph->runningNode(e); edges.set(ref[tn], INVALID); } } _cut.resize(1, INVALID); _min_cut = std::numeric_limits::max(); for (typename AuxGraph::NodeIt n(*_aux_graph); n != INVALID; ++n) { Value value = 0; for (typename AuxGraph::IncEdgeIt e(*_aux_graph, n); e != INVALID; ++e) { value += (*_aux_capacity)[e]; } if (_min_cut > value) { _min_cut = value; _cut[0] = (*_first)[n]; } (*_aux_cut_value)[n] = value; } } public : _aux_graph(0), local_aux_graph(false), _aux_capacity(0), local_aux_capacity(false), _aux_cut_value(0), local_aux_cut_value(false), _heap_cross_ref(0), local_heap_cross_ref(false), _heap(0), local_heap(false), _aux_graph(0), local_aux_graph(false), _aux_capacity(0), local_aux_capacity(false), _aux_cut_value(0), local_aux_cut_value(false), _heap_cross_ref(0), local_heap_cross_ref(false), _heap(0), local_heap(false), if (_next) delete _next; if (local_aux_capacity) delete _aux_capacity; if (local_aux_cut_value) delete _aux_cut_value; if (local_aux_graph) delete _aux_graph; if (local_capacity) delete _capacity; /// Initializes the internal data structures. void init() { create_structures(); _first_node = _last_node = INVALID; _node_num = countNodes(*_graph); } createStructures(); createAuxGraph(); } private: struct EdgeInfo { typename AuxGraph::Node source, target; Value capacity; }; struct EdgeInfoLess { bool operator()(const EdgeInfo& left, const EdgeInfo& right) const { return (left.source < right.source) || (left.source == right.source && left.target < right.target); } }; public: /// \brief Processes the next phase /// /// Processes the next phase in the algorithm. The function /// should be called countNodes(graph) - 1 times to get /// surely the min cut in the graph. The /// Processes the next phase in the algorithm. The function should /// be called at most countNodes(graph) - 1 times to get surely /// the min cut in the graph. /// ///\return %True when the algorithm finished. bool processNextPhase() { if (_node_num <= 1) return true; using namespace _min_cut_bits; typedef typename AuxGraph::Node Node; typedef typename AuxGraph::NodeIt NodeIt; typedef typename AuxGraph::UEdge UEdge; typedef typename AuxGraph::UEdgeIt UEdgeIt; typedef typename AuxGraph::IncEdgeIt IncEdgeIt; typedef typename MaxCardinalitySearch:: template DefHeap:: template DefCardinalityMap >:: template DefProcessedMap >:: Create MaxCardinalitySearch; typename AuxGraph::template UEdgeMap _edge_cut(*_aux_graph); for (NodeIt n(*_aux_graph); n != INVALID; ++n) { _heap_cross_ref->set(n, Heap::PRE_HEAP); } std::vector nodes; nodes.reserve(_node_num); int sep = 0; Value alpha = 0; Value emc = std::numeric_limits::max(); _heap->push(typename AuxGraph::NodeIt(*_aux_graph), 0); while (!_heap->empty()) { Node node = _heap->top(); Value value = _heap->prio(); _heap->pop(); for (typename AuxGraph::IncEdgeIt e(*_aux_graph, node); e != INVALID; ++e) { Node tn = _aux_graph->runningNode(e); switch (_heap->state(tn)) { case Heap::PRE_HEAP: _heap->push(tn, (*_aux_capacity)[e]); _edge_cut[e] = (*_heap)[tn]; break; case Heap::IN_HEAP: _heap->decrease(tn, (*_aux_capacity)[e] + (*_heap)[tn]); _edge_cut[e] = (*_heap)[tn]; break; case Heap::POST_HEAP: break; } } alpha += (*_aux_cut_value)[node]; alpha -= 2 * value; nodes.push_back(node); if (!_heap->empty()) { if (alpha < emc) { emc = alpha; sep = nodes.size(); } } } if ((int)nodes.size() < _node_num) { _aux_graph->clear(); _node_num = 1; _cut.clear(); for (int i = 0; i < (int)nodes.size(); ++i) { typename Graph::Node n = (*_first)[nodes[i]]; while (n != INVALID) { _cut.push_back(n); n = (*_next)[n]; } } _min_cut = 0; return true; } if (emc < _min_cut) { _cut.clear(); for (int i = 0; i < sep; ++i) { typename Graph::Node n = (*_first)[nodes[i]]; while (n != INVALID) { _cut.push_back(n); n = (*_next)[n]; } } _min_cut = emc; } typedef typename AuxGraph::template NodeMap UfeCr; UfeCr ufecr(*_aux_graph); typedef UnionFindEnum Ufe; Ufe ufe(ufecr); for (typename AuxGraph::NodeIt n(*_aux_graph); n != INVALID; ++n) { ufe.insert(n); } for (typename AuxGraph::UEdgeIt e(*_aux_graph); e != INVALID; ++e) { if (_edge_cut[e] >= emc) { ufe.join(_aux_graph->source(e), _aux_graph->target(e)); } } if (ufe.size((typename Ufe::ClassIt)(ufe)) == _node_num) { _aux_graph->clear(); _node_num = 1; return true; } MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity); for (NodeIt it(*_aux_graph); it != INVALID; ++it) { _heap_cross_ref->set(it, Heap::PRE_HEAP); } mcs.heap(*_heap, *_heap_cross_ref); LastTwoMap last_two_nodes(_node_num); mcs.processedMap(last_two_nodes); NullMap cardinality; mcs.cardinalityMap(cardinality); mcs.run(); Node new_node = _aux_graph->addNode(); std::vector remnodes; typename AuxGraph::template NodeMap edges(*_aux_graph, INVALID); Node first_node = last_two_nodes[0]; Node second_node = last_two_nodes[1]; _next->set((*_last)[first_node], (*_first)[second_node]); _first->set(new_node, (*_first)[first_node]); _last->set(new_node, (*_last)[second_node]); Value current_cut = 0; for (IncEdgeIt it(*_aux_graph, first_node); it != INVALID; ++it) { Node node = _aux_graph->runningNode(it); current_cut += (*_aux_capacity)[it]; if (node == second_node) continue; if (edges[node] == INVALID) { edges[node] = _aux_graph->addEdge(new_node, node); (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it]; for (typename Ufe::ClassIt c(ufe); c != INVALID; ++c) { if (ufe.size(c) == 1) continue; for (typename Ufe::ItemIt r(ufe, c); r != INVALID; ++r) { if ((Node)r == (Node)c) continue; _next->set((*_last)[c], (*_first)[r]); _last->set(c, (*_last)[r]); remnodes.push_back(r); --_node_num; } } std::vector addedges; std::vector remedges; for (typename AuxGraph::UEdgeIt e(*_aux_graph); e != INVALID; ++e) { Node sn = ufe.find(_aux_graph->source(e)); Node tn = ufe.find(_aux_graph->target(e)); if ((ufe.size(sn) == 1 && ufe.size(tn) == 1)) { continue; } if (sn == tn) { remedges.push_back(e); continue; } EdgeInfo info; if (sn < tn) { info.source = sn; info.target = tn; } else { (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it]; info.source = tn; info.target = sn; } } if (_first_node == INVALID || current_cut < _min_cut) { _first_node = (*_first)[first_node]; _last_node = (*_last)[first_node]; _min_cut = current_cut; } _aux_graph->erase(first_node); for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) { Node node = _aux_graph->runningNode(it); if (edges[node] == INVALID) { edges[node] = _aux_graph->addEdge(new_node, node); (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it]; } else { (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it]; info.capacity = (*_aux_capacity)[e]; addedges.push_back(info); remedges.push_back(e); } for (int i = 0; i < (int)remedges.size(); ++i) { _aux_graph->erase(remedges[i]); } sort(addedges.begin(), addedges.end(), EdgeInfoLess()); { int i = 0; while (i < (int)addedges.size()) { Node sn = addedges[i].source; Node tn = addedges[i].target; Value ec = addedges[i].capacity; ++i; while (i < (int)addedges.size() && sn == addedges[i].source && tn == addedges[i].target) { ec += addedges[i].capacity; ++i; } typename AuxGraph::UEdge ne = _aux_graph->addEdge(sn, tn); (*_aux_capacity)[ne] = ec; } } _aux_graph->erase(second_node); --_node_num; for (typename Ufe::ClassIt c(ufe); c != INVALID; ++c) { if (ufe.size(c) == 1) continue; Value cutvalue = 0; for (typename AuxGraph::IncEdgeIt e(*_aux_graph, c); e != INVALID; ++e) { cutvalue += (*_aux_capacity)[e]; } (*_aux_cut_value)[c] = cutvalue; } for (int i = 0; i < (int)remnodes.size(); ++i) { _aux_graph->erase(remnodes[i]); } return _node_num == 1; } template Value quickMinCut(NodeMap& nodeMap) const { for (typename Graph::Node it = _first_node; it != _last_node; it = (*_next)[it]) { nodeMap.set(it, true); } nodeMap.set(_last_node, true); for (int i = 0; i < (int)_cut.size(); ++i) { nodeMap.set(_cut[i], true); } return minCut(); } ///@} private: }; }