Changeset 869:636dadefe1e6 in lemon-main

Timestamp:

09/25/09 21:51:36 (15 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Phase:

public

Message:

Add fractional matching algorithms (#314)

Files:

• doc/groups.dox (modified) (2 diffs)
• lemon/Makefile.am (modified) (1 diff)
• lemon/fractional_matching.h (added)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (2 diffs)
• test/fractional_matching_test.cc (added)

doc/groups.dox

@@ -350 +350 @@
 problem of maximum flow.
 
-\ref Circulation is a preflow push-relabel algorithm implemented directly 
+\ref Circulation is a preflow push-relabel algorithm implemented directly
 for finding feasible circulations, which is a somewhat different problem,
 but it is strongly related to maximum flow.
@@ -471 +471 @@
   Edmond's blossom shrinking algorithm for calculating maximum weighted
   perfect matching in general graphs.
+- \ref MaxFractionalMatching Push-relabel algorithm for calculating
+  maximum cardinality fractional matching in general graphs.
+- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
+  maximum weighted fractional matching in general graphs.
+- \ref MaxWeightedPerfectFractionalMatching
+  Augmenting path algorithm for calculating maximum weighted
+  perfect fractional matching in general graphs.
 
 \image html bipartite_matching.png

lemon/Makefile.am

@@ -82 +82 @@
         lemon/fib_heap.h \
         lemon/fourary_heap.h \
+        lemon/fractional_matching.h \
         lemon/full_graph.h \
         lemon/glpk.h \

test/CMakeLists.txt

@@ -22 +22 @@
   error_test
   euler_test
+  fractional_matching_test
   gomory_hu_test
   graph_copy_test

test/Makefile.am

@@ -20 +20 @@
         test/error_test \
         test/euler_test \
+        test/fractional_matching_test \
         test/gomory_hu_test \
         test/graph_copy_test \
@@ -66 +67 @@
 test_error_test_SOURCES = test/error_test.cc
 test_euler_test_SOURCES = test/euler_test.cc
+test_fractional_matching_test_SOURCES = test/fractional_matching_test.cc
 test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
 test_graph_copy_test_SOURCES = test/graph_copy_test.cc