Changeset 2550:f26368148b9c in lemon-0.x
- Timestamp:
- 12/30/07 19:23:32 (15 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3427
- Location:
- lemon
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bipartite_matching.h
r2488 r2550 579 579 /// \param _WeightMap Type of weight map. 580 580 template <typename _BpUGraph, typename _WeightMap> 581 struct WeightedBipartiteMatchingDefaultTraits {581 struct MaxWeightedBipartiteMatchingDefaultTraits { 582 582 /// \brief The type of the weight of the undirected edges. 583 583 typedef typename _WeightMap::Value Value; … … 592 592 /// 593 593 /// 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; 596 596 597 597 /// \brief Instantiates a HeapCrossRef. … … 645 645 template <typename _BpUGraph, 646 646 typename _WeightMap = typename _BpUGraph::template UEdgeMap<int>, 647 typename _Traits = WeightedBipartiteMatchingDefaultTraits<_BpUGraph, _WeightMap> > 647 typename _Traits = 648 MaxWeightedBipartiteMatchingDefaultTraits<_BpUGraph, _WeightMap> > 648 649 #endif 649 650 class MaxWeightedBipartiteMatching { … … 865 866 Value bvalue = avalue - (*weight)[jt] + 866 867 anode_potential[anode] + bnode_potential[bnode]; 868 if (bvalue > bdistMax) { 869 bdistMax = bvalue; 870 } 867 871 if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) { 868 872 bdist[bnode] = bvalue; 869 873 bpred[bnode] = jt; 870 } 871 if (bvalue > bdistMax) { 872 bdistMax = bvalue; 873 } 874 } else continue; 874 875 if (bnode_matching[bnode] != INVALID) { 875 876 Node newanode = graph->aNode(bnode_matching[bnode]); … … 1242 1243 template <typename _BpUGraph, 1243 1244 typename _CostMap = typename _BpUGraph::template UEdgeMap<int>, 1244 typename _Traits = MinCostMaxBipartiteMatchingDefaultTraits<_BpUGraph, _CostMap> > 1245 typename _Traits = 1246 MinCostMaxBipartiteMatchingDefaultTraits<_BpUGraph, _CostMap> > 1245 1247 #endif 1246 1248 class MinCostMaxBipartiteMatching { … … 1452 1454 Value bvalue = avalue + (*cost)[jt] + 1453 1455 anode_potential[anode] - bnode_potential[bnode]; 1456 if (bvalue > bdistMax) { 1457 bdistMax = bvalue; 1458 } 1454 1459 if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) { 1455 1460 bdist[bnode] = bvalue; 1456 1461 bpred[bnode] = jt; 1457 } 1458 if (bvalue > bdistMax) { 1459 bdistMax = bvalue; 1460 } 1462 } else continue; 1461 1463 if (bnode_matching[bnode] != INVALID) { 1462 1464 Node newanode = graph->aNode(bnode_matching[bnode]); -
lemon/unionfind.h
r2548 r2550 963 963 private: 964 964 965 static const int cmax = 3;965 static const int cmax = 16; 966 966 967 967 ItemIntMap& index; … … 1125 1125 kd = nodes[kd].next; 1126 1126 } 1127 nodes[id].right = nodes[jd].right; 1127 1128 } 1128 1129
Note: See TracChangeset
for help on using the changeset viewer.