COIN-OR::LEMON - Graph Library

Changeset 2550:f26368148b9c in lemon-0.x


Ignore:
Timestamp:
12/30/07 19:23:32 (11 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3427
Message:

Changing degree of tournament tree
Bug fix in union find
Small efficiency improvment in bipartite matchings

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/bipartite_matching.h

    r2488 r2550  
    579579  /// \param _WeightMap Type of weight map.
    580580  template <typename _BpUGraph, typename _WeightMap>
    581   struct WeightedBipartiteMatchingDefaultTraits {
     581  struct MaxWeightedBipartiteMatchingDefaultTraits {
    582582    /// \brief The type of the weight of the undirected edges.
    583583    typedef typename _WeightMap::Value Value;
     
    592592    ///
    593593    /// The cross reference type used by heap.
    594     /// Usually it is \c Graph::NodeMap<int>.
    595     typedef typename BpUGraph::template NodeMap<int> HeapCrossRef;
     594    /// Usually it is \c Graph::ANodeMap<int>.
     595    typedef typename BpUGraph::template ANodeMap<int> HeapCrossRef;
    596596
    597597    /// \brief Instantiates a HeapCrossRef.
     
    645645  template <typename _BpUGraph,
    646646            typename _WeightMap = typename _BpUGraph::template UEdgeMap<int>,
    647             typename _Traits = WeightedBipartiteMatchingDefaultTraits<_BpUGraph, _WeightMap> >
     647            typename _Traits =
     648            MaxWeightedBipartiteMatchingDefaultTraits<_BpUGraph, _WeightMap> >
    648649#endif
    649650  class MaxWeightedBipartiteMatching {
     
    865866          Value bvalue = avalue  - (*weight)[jt] +
    866867            anode_potential[anode] + bnode_potential[bnode];
     868          if (bvalue > bdistMax) {
     869            bdistMax = bvalue;
     870          }
    867871          if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
    868872            bdist[bnode] = bvalue;
    869873            bpred[bnode] = jt;
    870           }
    871           if (bvalue > bdistMax) {
    872             bdistMax = bvalue;
    873           }
     874          } else continue;
    874875          if (bnode_matching[bnode] != INVALID) {
    875876            Node newanode = graph->aNode(bnode_matching[bnode]);
     
    12421243  template <typename _BpUGraph,
    12431244            typename _CostMap = typename _BpUGraph::template UEdgeMap<int>,
    1244             typename _Traits = MinCostMaxBipartiteMatchingDefaultTraits<_BpUGraph, _CostMap> >
     1245            typename _Traits =
     1246            MinCostMaxBipartiteMatchingDefaultTraits<_BpUGraph, _CostMap> >
    12451247#endif
    12461248  class MinCostMaxBipartiteMatching {
     
    14521454          Value bvalue = avalue + (*cost)[jt] +
    14531455            anode_potential[anode] - bnode_potential[bnode];
     1456          if (bvalue > bdistMax) {
     1457            bdistMax = bvalue;
     1458          }
    14541459          if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
    14551460            bdist[bnode] = bvalue;
    14561461            bpred[bnode] = jt;
    1457           }
    1458           if (bvalue > bdistMax) {
    1459             bdistMax = bvalue;
    1460           }
     1462          } else continue;
    14611463          if (bnode_matching[bnode] != INVALID) {
    14621464            Node newanode = graph->aNode(bnode_matching[bnode]);
  • lemon/unionfind.h

    r2548 r2550  
    963963  private:
    964964
    965     static const int cmax = 3;
     965    static const int cmax = 16;
    966966
    967967    ItemIntMap& index;
     
    11251125        kd = nodes[kd].next;
    11261126      }
     1127      nodes[id].right = nodes[jd].right;
    11271128    }
    11281129
Note: See TracChangeset for help on using the changeset viewer.