karlsruhemis / kamis Goto Github PK

clang-13 fails to compile KaMIS:

In file included from /disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-17-g171b753/lib/mis/evolutionary/reduction_evolution.cpp:14:
/disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-17-g171b753/lib/mis/evolutionary/combine/multiway_combine.h:115:98: error: reference to 'partition' is ambiguous
        void apply_k_partition_kahip(MISConfig & config, graph_access & G, separator_pool *pool, partition & part);
                                                                                                 ^
/disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-17-g171b753/lib/mis/evolutionary/separator_pool.h:21:8: note: candidate found by name lookup is 'partition'
struct partition {
       ^
/usr/include/c++/v1/__algorithm/partition.h:78:1: note: candidate found by name lookup is 'std::partition'
partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
^
1 error generated.

OS: FreeBSD 13.1

When compiling on Mac with clang, following error occurs while compiling dependencies:

In file included from /Users/henrik/dev/graph/KaMIS/lib/mis/evolutionary/reduction_evolution.cpp:14:
/Users/henrik/dev/graph/KaMIS/lib/mis/evolutionary/combine/multiway_combine.h:115:98: error: reference to 'partition' is ambiguous
        void apply_k_partition_kahip(MISConfig & config, graph_access & G, separator_pool *pool, partition & part);
                                                                                                 ^
/Users/henrik/dev/graph/KaMIS/lib/mis/evolutionary/separator_pool.h:21:8: note: candidate found by name lookup is 'partition'
struct partition {
       ^
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX12.0.sdk/usr/include/c++/v1/algorithm:3446:1: note: candidate found by name lookup is 'std::partition'
partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
^
1 error generated.

and

[  0%] Building CXX object CMakeFiles/libkaffpa.dir/extern/KaHIP/lib/partition/graph_partitioner.cpp.o
In file included from /Users/henrik/dev/graph/KaMIS/extern/KaHIP/lib/partition/graph_partitioner.cpp:10:
In file included from /Users/henrik/dev/graph/KaMIS/extern/KaHIP/lib/partition/graph_partitioner.h:15:
In file included from /Users/henrik/dev/graph/KaMIS/extern/KaHIP/lib/partition/uncoarsening/refinement/refinement.h:13:
In file included from /Users/henrik/dev/graph/KaMIS/extern/KaHIP/lib/partition/uncoarsening/refinement/quotient_graph_refinement/complete_boundary.h:15:
/Users/henrik/dev/graph/KaMIS/extern/KaHIP/lib/partition/uncoarsening/refinement/quotient_graph_refinement/boundary_lookup.h:17:17: error: expected namespace name
using namespace __gnu_cxx;

When using g++-11 (installed via homebrew, inspired by KaHIP/KaHIP#5 (comment)) KaMIS compiles fine.

On the following graph

graph.metis:
2 1
2
1

./deploy/online_mis ~/Desktop/test_graph_1edge.txt --time_limit=2
is not terminating.

This causes failure on ARM.

In the other place KaMIS first checks that -march=native is supported.

For the main algorithms, it would be nice to be able to use them in Python.

Currently OnlineMIS doesn't terminate when given complete graphs with 4 or more vertices. For example, the inputs

K4:

4 6
2 3 4
1 3 4
1 2 4
1 2 3

K5:

5 10
2 3 4 5
1 3 4 5
1 2 4 5
1 2 3 5
1 2 3 4

make the program get stuck in an infinite loop.

cp: cannot stat ‘./build/redumis’: No such file or directory
cp: cannot stat ‘./build/graphchecker’: No such file or directory
cp: cannot stat ‘./build/sort_adjacencies’: No such file or directory
cp: cannot stat ‘./build/online_mis’: No such file or directory
cp: cannot stat ‘./build/wmis/branch_reduce’: No such file or directory
cp: cannot stat ‘./build/wmis/weighted_ls’: No such file or directory

Hi, is there a way to adapt this program to work when finding the MWIS from graphs that contain negative weights?

Thanks.

In file included from /disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-18-g275a875/lib/mis/evolutionary/reduction_evolution.cpp:7:
In file included from /disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-18-g275a875/lib/mis/evolutionary/reduction_evolution.h:16:
In file included from /disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-18-g275a875/lib/mis/evolutionary/../kernel/ParFastKer/fast_reductions/src/full_reductions.h:30:
/disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-18-g275a875/lib/mis/kernel/ParFastKer/LinearTime/MIS_sigmod_pub/Graph.h:2:15: error: unknown type name 'C'
 * Copyright (C) 2019 Lijun Chang <[email protected]>
              ^
/disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-18-g275a875/lib/mis/kernel/ParFastKer/LinearTime/MIS_sigmod_pub/Graph.h:2:18: error: expected function body after function declarator
 * Copyright (C) 2019 Lijun Chang <[email protected]>
                 ^
/disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-18-g275a875/lib/mis/kernel/ParFastKer/LinearTime/MIS_sigmod_pub/Graph.h:38:2: error: unknown type name 'ui'
        ui n, m; //number of nodes and edges of the graph
        ^
/disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-18-g275a875/lib/mis/kernel/ParFastKer/LinearTime/MIS_sigmod_pub/Graph.h:40:2: error: unknown type name 'ui'
        ui *pstart; //offset of neighbors of nodes
        ^
/disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-18-g275a875/lib/mis/kernel/ParFastKer/LinearTime/MIS_sigmod_pub/Graph.h:41:2: error: unknown type name 'ui'
        ui *edges; //adjacent ids of edges
        ^
/disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-18-g275a875/lib/mis/kernel/ParFastKer/LinearTime/MIS_sigmod_pub/Graph.h:45:5: error: unknown type name 'ui'
    ui *reverse_mapping;

It looks like beginning of comment is missing.

There is a cmake build folder commited in wmis/build.
As far as I can tell, the project builds just fine without it, so I suppose the folder can be removed from the index without implications.

clang-13 prints this error:

/disk-samsung/freebsd-ports/math/kamis/work/KaMIS-2.0-19-g254fd16/extern/KaHIP/lib/partition/uncoarsening/refinement/kway_graph_refinement/kway_graph_refinement_commons.cpp:28:111: error: reinterpret_cast from 'nullptr_t' to 'kway_graph_refinement_commons *' is not allowed
                        m_instances = new std::vector< kway_graph_refinement_commons*>(omp_get_max_threads(), reinterpret_cast<kway_graph_refinement_commons*>(NULL));
                                                                                                              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1 error generated.

Is it possible to print the temporary solution at the end of each step of the weighted branch and reduce algorithm?

Hi,

I am trying to apply the reductions from lib/mis/kernel/branch_and_reduce_algorithm individually and I get the following assertion error. It comes from the dominateReduction() which is not called in the normal workflow because the REDUCTION value of branch_and_reduce_algorithm.cpp is set to 3 which avoids dominance reduction. But when called directly it raises the following:

0   libreduce.so                        0x000000011fd14157 _ZN27branch_and_reduce_algorithm3setEii + 71
1   libreduce.so                        0x000000011fd198b1 _ZN27branch_and_reduce_algorithm17dominateReductionEv + 465
2   libreduce.so                        0x000000011fd105f2 Reduce + 626
3   _ctypes.cpython-37m-darwin.so       0x000000010e0f51d7 ffi_call_unix64 + 79
4   ???                                 0x00007ffee651a560 0x0 + 140732762531168

Assertion failed: (x[v] < 0), function set, file ./lib/mis/kernel/branch_and_reduce_algorithm.cpp, line 110.

Process finished with exit code 134 (interrupted by signal 6: SIGABRT)

You can use the following graph to reproduce:

 7 11
%
 5  3  2
 1  3  4
 5  4  2  1
 2  3  6  7
 1  3  6
 5  4  7
 6  4

And this is a snippet that I am running to do the reduction:

branch_and_reduce_algorithm* reducer = new branch_and_reduce_algorithm(adj, adj.size());
reducer->dominateReduction();

This seems to be fixed by minor changes to the dominateReduction() function:

Which on the graph above it seems to perform correctly for one invocation of the function :

1. 2 dominates 0
2. 3 dominates 6
3. 5 dominates 6

So I noticed that graphchecker will report errors on graphs defined with weights. Seems ew is only read in but not used, so some extra logic is needed to handle both edge and node weights.

Reproduction

To give a test case, I modified examples/simple.graph to have node weights:

6 7 10
1 2 6
2 1 3 6
1 2 4
2 3 5
1 4 6
2 1 2 5

Which can be solved with weighted_branch_reduce, but graphchecker reports:

The number of edges specified in the beginning of the file does not match the number of edges that are in the file.
You specified 14 but there are 20

Potential Fix

I wrote a patch by taking the extra checks from KaHIPs and made it conform to the styling: bahorn@b3ddbcd

Though seems it's possible just to rip it from the repo directly.

First, I wanted to thank the authors and maintainers of KaMIS. It's a fantastic research as well as making, maintaining, and sharing KaMIS. It's very easy to get up and running as well as use. The update to migrate to using CMake is also a nice improvement.

For anyone who is developing and working on MacOS, I thought it might be helpful to share a little more detail on how I was able to get the project to build and run using the current release on MacOS (v10.15.6), gcc (v10.1.0), and KaMIS (v2.0).

1. Install Homebrew (https://brew.sh/)

   /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install.sh)"

2. Install gcc (which includes g++)
   Even though MacOS claims it has g++ installed the default OS call of g++ will actually result in a call to clang and not g++.

   brew install gcc

   As of this post will install g++ v10 which install the executable as /usr/local/bin/g++-10

3. Install OpenMP

   brew install libomp
   

4. Ensure that /usr/local/bin is part of the user PATH environment variable.
   Brew installs both g++ and the OpenMP library to /usr/local/bin so it needs to be discoverable by CMake during compilation.
   This can be done by adding the following to your your ~/.bash_profile (or whatever your shell profile is)

   export PATH=/usr/local/bin:$PATH

   Then executing:

   source ~/.bash_profile 

5. Compile KaMIS using the g++-10 compile, instead of clang.
   The default settings will have KaMIS try to compile with Clang, so instead we need to pass an extra variable to CMake to tell it to compile with g++ installed above. To do this we need to edit the base build script ~/.compile_withcmake.sh to change the line:

   cmake ../
   

   to

   cmake ../ -DCMAKE_C_COMPILER=/usr/local/bin/gcc-10 -DCMAKE_CXX_COMPILER=/usr/local/bin/g++-10

6. Now you can run the base compile script as normal:

   ./compile_withcmake.sh

7. That’s it! You have now built KaMIS on MacOS.

parallel/numeric is Linux-only.

Hi all,

I’m using KaMIS to find the exact Maximum Weighted Independent sets for some small weighted Erdős–Rényi graphs (Number of Vertices< 20) and am using the functions weighted_branch_reduce & weighted_local_search to do so.

Is there a method to output the vertices that form the found set ? From what I can tell, the --output method only gives the maximum weight found. This is in contrast to the same method in ReduMIS, which gives the vertices in a maximum unweighted independent set. Is there a special usage needed to get the maximum weight set out? Or is there a simple code change I can implement to do this ?

Second of all, as these are small graphs compared to the problems solved in this paper, will these methods always give the exact solution?
I’m using a Mac OS 10.15.7 with a C++ installation from Xcode, and followed the instructions in the Github to install the package.

Is there any way to predict how much memory KaMIS will use to process a certain input? For example, if I start KaMIS and run it for five minutes, would the maximum memory that it uses within those five minutes be a reasonable upper bound for how much memory it will use later, or do I risk that it enters some new phase later that requires a lot more memory than what it needed during the first five minutes?

I'm going to use this information to properly allocate resources to jobs that I am starting on a HPC cluster.