LEMON/LEMON-main Changeset - r875:07ec2b52e53d

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r875:07ec2b52e53d

« 867:5b926c
« 874:d8ea85

876:7f6e2b »

r875:07ec2b52e53d

Wed, 17 Mar 2010 10:29:57

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge #356

0 2 0

merge default

2 files changed with 71 insertions and 2 deletions:

lemon/matching.h

lemon/unionfind.h

↑ Collapse diff ↑

lemon/matching.h

Show inline comments

@@ -789,83 +789,102 @@
 		    BinHeap<Value, IntNodeMap> *_delta1;
 		    IntIntMap *_delta2_index;
 		    BinHeap<Value, IntIntMap> *_delta2;
 		    IntEdgeMap *_delta3_index;
 		    BinHeap<Value, IntEdgeMap> *_delta3;
 		    IntIntMap *_delta4_index;
 		    BinHeap<Value, IntIntMap> *_delta4;
 		    Value _delta_sum;
 		    int _unmatched;
 		    typedef MaxWeightedFractionalMatching<Graph, WeightMap> FractionalMatching;
 		    FractionalMatching *_fractional;
 		    void createStructures() {
 		      _node_num = countNodes(_graph);
 		      _blossom_num = _node_num * 3 / 2;
 		      if (!_matching) {
 		        _matching = new MatchingMap(_graph);
+		      }
 		      if (!_node_potential) {
 		        _node_potential = new NodePotential(_graph);
+		      }
 		      if (!_blossom_set) {
 		        _blossom_index = new IntNodeMap(_graph);
 		        _blossom_set = new BlossomSet(*_blossom_index);
 		        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
 		      } else if (_blossom_data->size() != _blossom_num) {
 		        delete _blossom_data;
 		        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
+		      }
 		      if (!_node_index) {
 		        _node_index = new IntNodeMap(_graph);
 		        _node_heap_index = new IntArcMap(_graph);
 		        _node_data = new RangeMap<NodeData>(_node_num,
-		                                              NodeData(*_node_heap_index));
 		                                            NodeData(*_node_heap_index));
 		      } else {
 		        delete _node_data;
 		        _node_data = new RangeMap<NodeData>(_node_num,
 		                                            NodeData(*_node_heap_index));
+		      }
 		      if (!_tree_set) {
 		        _tree_set_index = new IntIntMap(_blossom_num);
 		        _tree_set = new TreeSet(*_tree_set_index);
 		      } else {
 		        _tree_set_index->resize(_blossom_num);
+		      }
 		      if (!_delta1) {
 		        _delta1_index = new IntNodeMap(_graph);
 		        _delta1 = new BinHeap<Value, IntNodeMap>(*_delta1_index);
+		      }
 		      if (!_delta2) {
 		        _delta2_index = new IntIntMap(_blossom_num);
 		        _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
 		      } else {
 		        _delta2_index->resize(_blossom_num);
+		      }
 		      if (!_delta3) {
 		        _delta3_index = new IntEdgeMap(_graph);
 		        _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index);
+		      }
 		      if (!_delta4) {
 		        _delta4_index = new IntIntMap(_blossom_num);
 		        _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
 		      } else {
 		        _delta4_index->resize(_blossom_num);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_matching) {
 		        delete _matching;
+		      }
 		      if (_node_potential) {
 		        delete _node_potential;
+		      }
 		      if (_blossom_set) {
 		        delete _blossom_index;
 		        delete _blossom_set;
 		        delete _blossom_data;
+		      }
 		      if (_node_index) {
 		        delete _node_index;
 		        delete _node_heap_index;
 		        delete _node_data;
+		      }
 		      if (_tree_set) {
 		        delete _tree_set_index;
@@ -1567,74 +1586,86 @@
 		        _delta_sum(), _unmatched(0),
 		        _fractional(0)
 		    {}
 		    ~MaxWeightedMatching() {
 		      destroyStructures();
 		      if (_fractional) {
 		        delete _fractional;
+		      }
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to use the
 		    /// \ref run() member function.
 		    ///@{
 		    /// \brief Initialize the algorithm
 		    ///
 		    /// This function initializes the algorithm.
 		    void init() {
 		      createStructures();
 		      _blossom_node_list.clear();
 		      _blossom_potential.clear();
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
+		      }
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        (*_delta1_index)[n] = _delta1->PRE_HEAP;
+		      }
 		      for (EdgeIt e(_graph); e != INVALID; ++e) {
 		        (*_delta3_index)[e] = _delta3->PRE_HEAP;
+		      }
 		      for (int i = 0; i < _blossom_num; ++i) {
 		        (*_delta2_index)[i] = _delta2->PRE_HEAP;
 		        (*_delta4_index)[i] = _delta4->PRE_HEAP;
+		      }
 		      _unmatched = _node_num;
 		      _delta1->clear();
 		      _delta2->clear();
 		      _delta3->clear();
 		      _delta4->clear();
 		      _blossom_set->clear();
 		      _tree_set->clear();
 		      int index = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        Value max = 0;
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          if (_graph.target(e) == n) continue;
 		          if ((dualScale * _weight[e]) / 2 > max) {
 		            max = (dualScale * _weight[e]) / 2;
+		          }
+		        }
 		        (*_node_index)[n] = index;
 		        (*_node_data)[index].heap_index.clear();
 		        (*_node_data)[index].heap.clear();
 		        (*_node_data)[index].pot = max;
 		        _delta1->push(n, max);
 		        int blossom =
 		          _blossom_set->insert(n, std::numeric_limits<Value>::max());
 		        _tree_set->insert(blossom);
 		        (*_blossom_data)[blossom].status = EVEN;
 		        (*_blossom_data)[blossom].pred = INVALID;
 		        (*_blossom_data)[blossom].next = INVALID;
 		        (*_blossom_data)[blossom].pot = 0;
 		        (*_blossom_data)[blossom].offset = 0;
 		        ++index;
+		      }
 		      for (EdgeIt e(_graph); e != INVALID; ++e) {
 		        int si = (*_node_index)[_graph.u(e)];
 		        int ti = (*_node_index)[_graph.v(e)];
 		        if (_graph.u(e) != _graph.v(e)) {
 		          _delta3->push(e, ((*_node_data)[si].pot + (*_node_data)[ti].pot -
 		                            dualScale * _weight[e]) / 2);
+		        }
+		      }
+		    }
@@ -2216,79 +2247,97 @@
 		    IntIntMap *_delta2_index;
 		    BinHeap<Value, IntIntMap> *_delta2;
 		    IntEdgeMap *_delta3_index;
 		    BinHeap<Value, IntEdgeMap> *_delta3;
 		    IntIntMap *_delta4_index;
 		    BinHeap<Value, IntIntMap> *_delta4;
 		    Value _delta_sum;
 		    int _unmatched;
 		    typedef MaxWeightedPerfectFractionalMatching<Graph, WeightMap>
 		    FractionalMatching;
 		    FractionalMatching *_fractional;
 		    void createStructures() {
 		      _node_num = countNodes(_graph);
 		      _blossom_num = _node_num * 3 / 2;
 		      if (!_matching) {
 		        _matching = new MatchingMap(_graph);
+		      }
 		      if (!_node_potential) {
 		        _node_potential = new NodePotential(_graph);
+		      }
 		      if (!_blossom_set) {
 		        _blossom_index = new IntNodeMap(_graph);
 		        _blossom_set = new BlossomSet(*_blossom_index);
 		        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
 		      } else if (_blossom_data->size() != _blossom_num) {
 		        delete _blossom_data;
 		        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
+		      }
 		      if (!_node_index) {
 		        _node_index = new IntNodeMap(_graph);
 		        _node_heap_index = new IntArcMap(_graph);
 		        _node_data = new RangeMap<NodeData>(_node_num,
 		                                            NodeData(*_node_heap_index));
 		      } else if (_node_data->size() != _node_num) {
 		        delete _node_data;
 		        _node_data = new RangeMap<NodeData>(_node_num,
 		                                            NodeData(*_node_heap_index));
+		      }
 		      if (!_tree_set) {
 		        _tree_set_index = new IntIntMap(_blossom_num);
 		        _tree_set = new TreeSet(*_tree_set_index);
 		      } else {
 		        _tree_set_index->resize(_blossom_num);
+		      }
 		      if (!_delta2) {
 		        _delta2_index = new IntIntMap(_blossom_num);
 		        _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
 		      } else {
 		        _delta2_index->resize(_blossom_num);
+		      }
 		      if (!_delta3) {
 		        _delta3_index = new IntEdgeMap(_graph);
 		        _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index);
+		      }
 		      if (!_delta4) {
 		        _delta4_index = new IntIntMap(_blossom_num);
 		        _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
 		      } else {
 		        _delta4_index->resize(_blossom_num);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_matching) {
 		        delete _matching;
+		      }
 		      if (_node_potential) {
 		        delete _node_potential;
+		      }
 		      if (_blossom_set) {
 		        delete _blossom_index;
 		        delete _blossom_set;
 		        delete _blossom_data;
+		      }
 		      if (_node_index) {
 		        delete _node_index;
 		        delete _node_heap_index;
 		        delete _node_data;
+		      }
 		      if (_tree_set) {
 		        delete _tree_set_index;
@@ -2947,71 +2996,82 @@
 		        _delta_sum(), _unmatched(0),
 		        _fractional(0)
 		    {}
 		    ~MaxWeightedPerfectMatching() {
 		      destroyStructures();
 		      if (_fractional) {
 		        delete _fractional;
+		      }
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to use the
 		    /// \ref run() member function.
 		    ///@{
 		    /// \brief Initialize the algorithm
 		    ///
 		    /// This function initializes the algorithm.
 		    void init() {
 		      createStructures();
 		      _blossom_node_list.clear();
 		      _blossom_potential.clear();
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
+		      }
 		      for (EdgeIt e(_graph); e != INVALID; ++e) {
 		        (*_delta3_index)[e] = _delta3->PRE_HEAP;
+		      }
 		      for (int i = 0; i < _blossom_num; ++i) {
 		        (*_delta2_index)[i] = _delta2->PRE_HEAP;
 		        (*_delta4_index)[i] = _delta4->PRE_HEAP;
+		      }
 		      _unmatched = _node_num;
 		      _delta2->clear();
 		      _delta3->clear();
 		      _delta4->clear();
 		      _blossom_set->clear();
 		      _tree_set->clear();
 		      int index = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        Value max = - std::numeric_limits<Value>::max();
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          if (_graph.target(e) == n) continue;
 		          if ((dualScale * _weight[e]) / 2 > max) {
 		            max = (dualScale * _weight[e]) / 2;
+		          }
+		        }
 		        (*_node_index)[n] = index;
 		        (*_node_data)[index].heap_index.clear();
 		        (*_node_data)[index].heap.clear();
 		        (*_node_data)[index].pot = max;
 		        int blossom =
 		          _blossom_set->insert(n, std::numeric_limits<Value>::max());
 		        _tree_set->insert(blossom);
 		        (*_blossom_data)[blossom].status = EVEN;
 		        (*_blossom_data)[blossom].pred = INVALID;
 		        (*_blossom_data)[blossom].next = INVALID;
 		        (*_blossom_data)[blossom].pot = 0;
 		        (*_blossom_data)[blossom].offset = 0;
 		        ++index;
+		      }
 		      for (EdgeIt e(_graph); e != INVALID; ++e) {
 		        int si = (*_node_index)[_graph.u(e)];
 		        int ti = (*_node_index)[_graph.v(e)];
 		        if (_graph.u(e) != _graph.v(e)) {
 		          _delta3->push(e, ((*_node_data)[si].pot + (*_node_data)[ti].pot -
 		                            dualScale * _weight[e]) / 2);
+		        }
+		      }
+		    }
 		    /// \brief Initialize the algorithm with fractional matching

lemon/unionfind.h

Show inline comments

@@ -1267,48 +1267,57 @@
 		    ///
 		    /// Returns true when the given class is alive, ie. the class is
 		    /// not nested into other class.
 		    bool alive(int cls) const {
 		      return classes[cls].parent < 0;
+		    }
 		    /// \brief Returns true when the given class is trivial.
 		    ///
 		    /// Returns true when the given class is trivial, ie. the class
 		    /// contains just one item directly.
 		    bool trivial(int cls) const {
 		      return classes[cls].left == -1;
+		    }
 		    /// \brief Constructs the union-find.
 		    ///
 		    /// Constructs the union-find.
 		    /// \brief _index The index map of the union-find. The data
 		    /// structure uses internally for store references.
 		    HeapUnionFind(ItemIntMap& _index)
 		      : index(_index), first_class(-1),
 		        first_free_class(-1), first_free_node(-1) {}
 		    /// \brief Clears the union-find data structure
 		    ///
 		    /// Erase each item from the data structure.
 		    void clear() {
 		      nodes.clear();
 		      classes.clear();
 		      first_free_node = first_free_class = first_class = -1;
+		    }
 		    /// \brief Insert a new node into a new component.
 		    ///
 		    /// Insert a new node into a new component.
 		    /// \param item The item of the new node.
 		    /// \param prio The priority of the new node.
 		    /// \return The class id of the one-item-heap.
 		    int insert(const Item& item, const Value& prio) {
 		      int id = newNode();
 		      nodes[id].item = item;
 		      nodes[id].prio = prio;
 		      nodes[id].size = 0;
 		      nodes[id].prev = -1;
 		      nodes[id].next = -1;
 		      nodes[id].left = -1;
 		      nodes[id].right = -1;
 		      nodes[id].item = item;
 		      index[item] = id;
 		      int class_id = newClass();
 		      classes[class_id].parent = ~id;
 		      classes[class_id].depth = 0;

0 comments (0 inline)

RhodeCode

Login to your account