Changeset 810:e9fbc747ca47 in lemon-0.x

Timestamp:

09/06/04 19:12:00 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1105

Message:

Kruskal alg. (src/hugo/kruskal.h, src/test/kruskal_test.cc) is (almost) done.

• Some input adaptor is still missing.
• The class and function names should be revised.
• Docs still needs some improvement.

Location:

src

Files:

• hugo/Makefile.am (modified) (1 diff)
• hugo/kruskal.h (added)
• hugo/unionfind.h (modified) (1 diff)
• test/Makefile.am (modified) (2 diffs)
• test/kruskal_test.cc (added)
• work/johanna/kruskal.h (deleted)

src/hugo/Makefile.am

@@ -12 +12 @@
         graph_wrapper.h                                                 \
         invalid.h                                                       \
+        kruskal.h                                                       \
         list_graph.h                                                    \
         map_defines.h                                                   \

src/hugo/unionfind.h

@@ -33 +33 @@
    * For more features see the \ref UnionFindEnum class.
    *
+   * It is primarily used in Kruskal algorithm for finding minimal
+   * cost spanning tree in a graph.
+   * \sa kruskal()
+   *
    * \pre The elements are automatically added only if the map 
    * given to the constructor was filled with -1's. Otherwise you
    * need to add all the elements by the \ref insert() method.
+   * \bug It is not clear what the constructor parameter is used for.
    */
 

src/test/Makefile.am

@@ -3 +3 @@
 noinst_HEADERS = test_tools.h graph_test.h
 
-check_PROGRAMS = test_tools_pass test_tools_fail \
+check_PROGRAMS = \
+        bfs_test \
+        dfs_test \
+        dijkstra_test \
+        error_test \
         graph_test \
-        dijkstra_test bfs_test dfs_test \
-        minlengthpaths_test mincostflows_test \
-        unionfind_test xy_test \
+        kruskal_test \
+        mincostflows_test \
+        minlengthpaths_test \
+        test_tools_fail \
+        test_tools_pass \
         time_measure_test \
-        error_test 
+        unionfind_test \
+        xy_test
 
 
@@ -20 +27 @@
 error_test_SOURCES = error_test.cc
 graph_test_SOURCES = graph_test.cc
+kruskal_test_SOURCES = kruskal_test.cc
 mincostflows_test_SOURCES = mincostflows_test.cc
 minlengthpaths_test_SOURCES = minlengthpaths_test.cc