RAMA: Rapid algorithm for multicut problem

Related tags

Deep Learning RAMA
Overview

RAMA: Rapid algorithm for multicut problem

Solves multicut (correlation clustering) problems orders of magnitude faster than CPU based solvers without compromising solution quality on NVIDIA GPU. It also gives lower bound guarantees. Paper available here.

animation

Requirements

We use CUDA 11.2 and GCC 10. Other combinations might also work but not tested. CMake is required for compilation.

Installation

C++ solver:

mkdir build
cd build
cmake ..
make -j 4

Python bindings:

We also provide python bindings using pybind. Simply run the following command:

python -m pip install git+https://github.com/pawelswoboda/RAMA.git

Usage

C++ solver:

We require multicut instance stored in a (.txt) file in the following format:

MULTICUT
i_1, j_1, cost_1
i_2, j_2, cost_2
...
i_n, j_n, cost_n

which corresponds to a graph with N edges. Where i and j should be vertex indices and cost is a floating point number. Positive costs implies that the nodes are similar and thus would prefer to be in same component and viceversa. Afterwards run:

./rama_text_input -f <PATH_TO_MULTICUT_INSTANCE>

For more details and downloading multicut instances see LPMP.

Python solver:

An example to compute multicut on a triangle graph:

import rama_py
rama_py.rama_cuda([0, 1, 2], [1, 2, 0], [1.1, -2, 3], rama_py.multicut_solver_options())

Parameters:

The default set of parameters are defined here which correspond to algorithm PD from the paper. This algorithm offers best compute time versus solution quality trade-off. Parameters for other variants are:

  • Fast purely primal algorithm (P): This algorithm can be slightly worse than sequential CPU heuristics but is 30 to 50 times faster. 
    ./rama_text_input -f <PATH_TO_MULTICUT_INSTANCE> 0 0 0 0
  • Best primal algorithm (PD+) : This algorithm can even be better than CPU solvers in terms of solution quality as it uses dual information. Still, it is 5 to 10 faster than best CPU solver. 
     ./rama_text_input -f <PATH_TO_MULTICUT_INSTANCE> 5 10 5 10
  • Dual algorithm (D): Use this algorithm for only computing the lower bound. Our lower bounds are slightly better than ICP and are computed up to 100 times faster. 
     ./rama_text_input -f <PATH_TO_MULTICUT_INSTANCE> 5 10 0 0 5

Run ./rama_text_input --help for details about the parameters.

Comments
  • CUDA Error while using Python solver

    CUDA Error while using Python solver

    Hi,

    For some graphs, I am encountering cudaErrorIllegalAddress error while running rama_cuda function. I am adding a script that reproduces this error in the next comment. Here is the full output:

    Running solver type PD which offers best compute time versus quality tradeoff.
Going to use NVIDIA GeForce GTX 1050 Ti 6.1, device number 0
3-cycles: found # of triangles: 0, budget: 7004
3-cycles: found # of triangles: 0, budget: 7004
4-cycles: number of expansions: 89675
4-cycles: found # of triangles: 0, budget: 7004
3-cycles: found # of triangles: 0, budget: 7004
4-cycles: number of expansions: 89675
4-cycles: found # of triangles: 0, budget: 7004
5-cycles: number of expansions: 2270526
5-cycles: found # of triangles: 0, budget: 7004
initial energy = 41519
matched sum: 66, rel_increase: 66
matched sum: 132, rel_increase: 0.985075
matched sum: 198, rel_increase: 0.496241
matched sum: 264, rel_increase: 0.331658
matched sum: 330, rel_increase: 0.249057
matched sum: 396, rel_increase: 0.199396
matched sum: 462, rel_increase: 0.166247
matched sum: 528, rel_increase: 0.142549
matched sum: 594, rel_increase: 0.124764
matched sum: 660, rel_increase: 0.110924
# vertices = 2383
# matched edges = 330 / 48523
original A size 2383x2349
contracted A size 2053x2019
energy reduction 330
energy after iteration 0: 41189, #components = 2053
3-cycles: found # of triangles: 0, budget: 2571
matched sum: 72, rel_increase: 72
matched sum: 142, rel_increase: 0.958904
matched sum: 210, rel_increase: 0.475524
matched sum: 278, rel_increase: 0.322275
matched sum: 344, rel_increase: 0.236559
matched sum: 410, rel_increase: 0.191304
matched sum: 474, rel_increase: 0.155718
matched sum: 538, rel_increase: 0.134737
matched sum: 602, rel_increase: 0.118738
matched sum: 666, rel_increase: 0.106136
# vertices = 2053
# matched edges = 333 / 37814
original A size 2053x2019
contracted A size 1720x1687
energy reduction 821
energy after iteration 1: 40368, #components = 1720
3-cycles: found # of triangles: 0, budget: 1792
matched sum: 74, rel_increase: 74
matched sum: 146, rel_increase: 0.96
matched sum: 216, rel_increase: 0.47619
matched sum: 282, rel_increase: 0.304147
matched sum: 346, rel_increase: 0.226148
matched sum: 412, rel_increase: 0.190202
matched sum: 476, rel_increase: 0.154964
matched sum: 540, rel_increase: 0.134172
matched sum: 604, rel_increase: 0.118299
matched sum: 668, rel_increase: 0.105785
# vertices = 1720
# matched edges = 334 / 28267
original A size 1720x1687
contracted A size 1386x1353
energy reduction 1713
energy after iteration 2: 38655, #components = 1386
3-cycles: found # of triangles: 0, budget: 1203
matched sum: 72, rel_increase: 72
matched sum: 142, rel_increase: 0.958904
matched sum: 206, rel_increase: 0.447552
matched sum: 274, rel_increase: 0.328502
matched sum: 338, rel_increase: 0.232727
matched sum: 402, rel_increase: 0.188791
matched sum: 470, rel_increase: 0.168734
matched sum: 538, rel_increase: 0.144374
matched sum: 602, rel_increase: 0.118738
matched sum: 666, rel_increase: 0.106136
# vertices = 1386
# matched edges = 333 / 20020
original A size 1386x1353
contracted A size 1053x1021
energy reduction 3347
energy after iteration 3: 35308, #components = 1053
3-cycles: found # of triangles: 0, budget: 770
matched sum: 76, rel_increase: 76
matched sum: 144, rel_increase: 0.883117
matched sum: 212, rel_increase: 0.468966
matched sum: 278, rel_increase: 0.309859
matched sum: 342, rel_increase: 0.229391
matched sum: 404, rel_increase: 0.180758
matched sum: 468, rel_increase: 0.158025
matched sum: 530, rel_increase: 0.132196
matched sum: 592, rel_increase: 0.116761
matched sum: 654, rel_increase: 0.104553
# vertices = 1053
# matched edges = 327 / 12750
original A size 1053x1021
contracted A size 726x694
energy reduction 5538
energy after iteration 4: 29770, #components = 726
3-cycles: found # of triangles: 0, budget: 452
matched sum: 68, rel_increase: 68
matched sum: 134, rel_increase: 0.956522
matched sum: 200, rel_increase: 0.488889
matched sum: 264, rel_increase: 0.318408
matched sum: 326, rel_increase: 0.233962
matched sum: 388, rel_increase: 0.189602
matched sum: 446, rel_increase: 0.1491
matched sum: 502, rel_increase: 0.12528
matched sum: 556, rel_increase: 0.107356
matched sum: 608, rel_increase: 0.0933573
# vertices = 726
# matched edges = 304 / 6582
original A size 726x694
contracted A size 422x393
energy reduction 6775
energy after iteration 5: 22995, #components = 422
3-cycles: found # of triangles: 0, budget: 217
matched sum: 66, rel_increase: 66
matched sum: 132, rel_increase: 0.985075
matched sum: 194, rel_increase: 0.466165
matched sum: 254, rel_increase: 0.307692
matched sum: 304, rel_increase: 0.196078
matched sum: 350, rel_increase: 0.15082
matched sum: 388, rel_increase: 0.108262
matched sum: 388, rel_increase: 0
# vertices = 422
# matched edges = 194 / 2357
original A size 422x393
contracted A size 228x204
energy reduction 7963
energy after iteration 6: 15032, #components = 228
3-cycles: found # of triangles: 0, budget: 95
matched sum: 64, rel_increase: 64
matched sum: 126, rel_increase: 0.953846
matched sum: 178, rel_increase: 0.409449
matched sum: 214, rel_increase: 0.201117
matched sum: 214, rel_increase: 0
# vertices = 228
# matched edges = 107 / 693
original A size 228x204
contracted A size 121x115
energy reduction 7655
energy after iteration 7: 7377, #components = 121
3-cycles: found # of triangles: 0, budget: 41
matched sum: 62, rel_increase: 62
matched sum: 104, rel_increase: 0.666667
matched sum: 104, rel_increase: 0
# vertices = 121
# matched edges = 52 / 193
original A size 121x115
contracted A size 68x61
energy reduction 6249
energy after iteration 8: 1128, #components = 68
3-cycles: found # of triangles: 0, budget: 21
matched sum: 56, rel_increase: 56
matched sum: 56, rel_increase: 0
# vertices = 68
# matched edges = 28 / 56
original A size 68x61
contracted A size 40x35
energy reduction 4479
energy after iteration 9: -3351, #components = 40
3-cycles: found # of triangles: 0, budget: 10
matched sum: 12, rel_increase: 12
matched sum: 12, rel_increase: 0
# vertices = 40
# matched edges = 6 / 16
original A size 40x35
contracted A size 33x28
energy reduction 151
energy after iteration 10: -3502, #components = 33
terminate called after throwing an instance of 'thrust::system::system_error'
  what():  CUDA free failed: cudaErrorIllegalAddress: an illegal memory access was encountered
Aborted
    opened by ocetintas 7
  • Installation with CUDA11

    Installation with CUDA11

    Hi,

    I tried to install RAMA with CUDA11, using the pip installation instruction (python -m pip install git+https://github.com/pawelswoboda/RAMA.git). Using

    CUDA version 11.1
GCC version 10.2
CMAKE version 3.20

    This fails with the following error:

      /tmp/pip-req-build-d9hjyjt3/external/cudaMST/gpuMST/gpuMST.cu(138): warning: function "__any"                                         
  /g/easybuild/x86_64/CentOS/7/skylake/software/CUDAcore/11.1.1/bin/../targets/x86_64-linux/include/device_atomic_functions.h(178): here was declared deprecated ("__any() is deprecated in favor of __any_sync() and may be removed in a future release (Use -Wno-deprecated-declarations to suppress this warning).")
  
  /g/easybuild/x86_64/CentOS/7/skylake/software/GCCcore/10.2.0/include/c++/10.2.0/tuple(566): error: pack "_UElements" does not have the same number of elements as "_Elements"
            detected during instantiation of "__nv_bool std::tuple<_Elements...>::__nothrow_constructible<_UElements...>() [with _Elements=<const thrust::device_vector<int, thrust::device_allocator<int>> &, const thrust::device_vector<int, thrust::device_allocator<int>> &, const thrust::device_vector<float, thrust::device_allocator<float>> &>, _UElements=<>]"
  /tmp/pip-req-build-d9hjyjt3/src/multicut_message_passing.cu(350): here
  
  /g/easybuild/x86_64/CentOS/7/skylake/software/GCCcore/10.2.0/include/c++/10.2.0/tuple(566): error: pack "_UElements" does not have the same number of elements as "_Elements"
            detected during:
              instantiation of "__nv_bool std::tuple<_Elements...>::__nothrow_constructible<_UElements...>() [with _Elements=<thrust::device_vector<int, thrust::device_allocator<int>> &, thrust::device_vector<int, thrust::device_allocator<int>> &, thrust::device_vector<float, thrust::device_allocator<float>> &>, _UElements=<>]"
  (1616): here
              instantiation of "std::tuple<_Elements &...> std::tie(_Elements &...) noexcept [with _Elements=<thrust::device_vector<int, thrust::device_allocator<int>>, thrust::device_vector<int, thrust::device_allocator<int>>, thrust::device_vector<float, thrust::device_allocator<float>>>]"
  /tmp/pip-req-build-d9hjyjt3/src/dCOO.cu(166): here

    I also tried with CUDA 10, but ran into other issues. CUDA 11 would be much better for me in order to be compatible with our stack.

    opened by constantinpape 7
  • Cannot build the file correctly

    Cannot build the file correctly

    Hello,

    Thanks for the great project. I am very interested in this subject. However, when I tried to build the code, I faced the following problem and cannot solve it. If you have any idea, please help!

    In the beginning I begin with Cuda 11.2 and gcc-10.3， however I encountered the following problem:

    /usr/include/c++/10/chrono:473:154:` required from here

    /usr/include/c++/10/chrono:428:27: internal compiler error: Segmentation fault 428 | _S_gcd(intmax_t __m, intmax_t __n) noexcept | ^~~~~~ Please submit a full bug report, with preprocessed source if appropriate.

    Therefore, I switch to gcc-9.3.0 and compile again, but still have the following problem:

    /root/RAMA/src/rama_py.cpp:` In function 'std::vectorat::Tensor rama_torch(const at::Tensor&, const at::Tensor&, const at::Tensor&, const multicut_solver_options&)':

    /root/RAMA/src/rama_py.cpp:48:44: error: cannot bind rvalue reference of type 'thrust::device_vector&&' to lvalue of type 'thrust::device_vector' 48 | std::tie(node_mapping, lb) = rama_cuda(i, j, costs, opts, device); | ^ In file included from /root/RAMA/src/rama_py.cpp:5: /root/RAMA/include/rama_cuda.h:9:87: note: initializing argument 1 of 'std::tuple<thrust::device_vector<int, thrust::device_allocator >, double> rama_cuda(thrust::device_vector&&, thrust::device_vector&&, thrust::device_vector&&, const multicut_solver_options&, int)

    Do you have any suggestions? Thanks a lot!

    opened by chihchiehchen 2
  • Documentation for options in rama_py

    Documentation for options in rama_py

    The multicut_solver_options class has two constructors, one without parameters and one with a lot of parameters, see https://github.com/pawelswoboda/RAMA/blob/master/src/rama_py.cpp#L15-L17.

    It would be nice to document this a bit, especially how it relates to the parameters mentioned in the README: https://github.com/pawelswoboda/RAMA#parameters.

    Which parameters determine the trade-off between speed and accuracy?

    opened by constantinpape 2
  • install not working google colab

    install not working google colab

    hey there I wanted to test your package on google colab to see if it will work well with my wide field imaging neuro data. I am having issues with installation and can'r parse the error after i run python -m pip install git+https://github.com/pawelswoboda/RAMA.git i get the following error ERROR: Command errored out with exit status 1: /usr/bin/python3 -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-req-build-lwauoshr/setup.py'"'"'; __file__='"'"'/tmp/pip-req-build-lwauoshr/setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(__file__) if os.path.exists(__file__) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' install --record /tmp/pip-record-x5sjf458/install-record.txt --single-version-externally-managed --compile --install-headers /usr/local/include/python3.7/RAMA Check the logs for full command output.

    here is the verbose version

    
/content# python -m pip install --verbose git+https://github.com/pawelswoboda/RAMA.git
Using pip 21.1.3 from /usr/local/lib/python3.7/dist-packages/pip (python 3.7)
Value for scheme.platlib does not match. Please report this to <https://github.com/pypa/pip/issues/9617>
distutils: /usr/local/lib/python3.7/dist-packages
sysconfig: /usr/lib/python3.7/site-packages
Value for scheme.purelib does not match. Please report this to <https://github.com/pypa/pip/issues/9617>
distutils: /usr/local/lib/python3.7/dist-packages
sysconfig: /usr/lib/python3.7/site-packages
Value for scheme.headers does not match. Please report this to <https://github.com/pypa/pip/issues/9617>
distutils: /usr/local/include/python3.7/UNKNOWN
sysconfig: /usr/include/python3.7m/UNKNOWN
Value for scheme.scripts does not match. Please report this to <https://github.com/pypa/pip/issues/9617>
distutils: /usr/local/bin
sysconfig: /usr/bin
Value for scheme.data does not match. Please report this to <https://github.com/pypa/pip/issues/9617>
distutils: /usr/local
sysconfig: /usr
Additional context:
user = False
home = None
root = None
prefix = None
Non-user install because site-packages writeable
Created temporary directory: /tmp/pip-ephem-wheel-cache-f0myxyp3
Created temporary directory: /tmp/pip-req-tracker-uo9l71am
Initialized build tracking at /tmp/pip-req-tracker-uo9l71am
Created build tracker: /tmp/pip-req-tracker-uo9l71am
Entered build tracker: /tmp/pip-req-tracker-uo9l71am
Created temporary directory: /tmp/pip-install-h3xkri48
Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/
Collecting git+https://github.com/pawelswoboda/RAMA.git
  Created temporary directory: /tmp/pip-req-build-v6dnit4h
  Cloning https://github.com/pawelswoboda/RAMA.git to /tmp/pip-req-build-v6dnit4h
  Running command git clone -q https://github.com/pawelswoboda/RAMA.git /tmp/pip-req-build-v6dnit4h
  Running command git submodule update --init --recursive -q
  Added git+https://github.com/pawelswoboda/RAMA.git to build tracker '/tmp/pip-req-tracker-uo9l71am'
    Running setup.py (path:/tmp/pip-req-build-v6dnit4h/setup.py) egg_info for package from git+https://github.com/pawelswoboda/RAMA.git
    Created temporary directory: /tmp/pip-pip-egg-info-lffp9u2p
    Running command python setup.py egg_info
    running egg_info
    creating /tmp/pip-pip-egg-info-lffp9u2p/RAMA.egg-info
    writing /tmp/pip-pip-egg-info-lffp9u2p/RAMA.egg-info/PKG-INFO
    writing dependency_links to /tmp/pip-pip-egg-info-lffp9u2p/RAMA.egg-info/dependency_links.txt
    writing top-level names to /tmp/pip-pip-egg-info-lffp9u2p/RAMA.egg-info/top_level.txt
    writing manifest file '/tmp/pip-pip-egg-info-lffp9u2p/RAMA.egg-info/SOURCES.txt'
    adding license file 'LICENSE'
    writing manifest file '/tmp/pip-pip-egg-info-lffp9u2p/RAMA.egg-info/SOURCES.txt'
  Source in /tmp/pip-req-build-v6dnit4h has version 0.0.7, which satisfies requirement RAMA==0.0.7 from git+https://github.com/pawelswoboda/RAMA.git
  Removed RAMA==0.0.7 from git+https://github.com/pawelswoboda/RAMA.git from build tracker '/tmp/pip-req-tracker-uo9l71am'
Created temporary directory: /tmp/pip-unpack-a2e478b2
Building wheels for collected packages: RAMA
  Created temporary directory: /tmp/pip-wheel-vohkvad6
  Building wheel for RAMA (setup.py) ...   Destination directory: /tmp/pip-wheel-vohkvad6
  Running command /usr/bin/python3 -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-req-build-v6dnit4h/setup.py'"'"'; __file__='"'"'/tmp/pip-req-build-v6dnit4h/setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(__file__) if os.path.exists(__file__) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' bdist_wheel -d /tmp/pip-wheel-vohkvad6
  running bdist_wheel
  running build
  running build_ext
  build_with_torch:OFF


  Testing gcc...
  ...has version 7.5.0
  ...has version 7.5.0-3ubuntu1~18.04)
  Testing gcc-7...
  ...has version 7.5.0
  ...has version 7.5.0-3ubuntu1~18.04)
  Traceback (most recent call last):
    File "<string>", line 1, in <module>
    File "/tmp/pip-req-build-v6dnit4h/setup.py", line 128, in <module>
      setup_requires=['wheel']
    File "/usr/local/lib/python3.7/dist-packages/setuptools/__init__.py", line 153, in setup
      return distutils.core.setup(**attrs)
    File "/usr/lib/python3.7/distutils/core.py", line 148, in setup
      dist.run_commands()
    File "/usr/lib/python3.7/distutils/dist.py", line 966, in run_commands
      self.run_command(cmd)
    File "/usr/lib/python3.7/distutils/dist.py", line 985, in run_command
      cmd_obj.run()
    File "/usr/local/lib/python3.7/dist-packages/wheel/bdist_wheel.py", line 299, in run
      self.run_command('build')
    File "/usr/lib/python3.7/distutils/cmd.py", line 313, in run_command
      self.distribution.run_command(command)
    File "/usr/lib/python3.7/distutils/dist.py", line 985, in run_command
      cmd_obj.run()
    File "/usr/lib/python3.7/distutils/command/build.py", line 135, in run
      self.run_command(cmd_name)
    File "/usr/lib/python3.7/distutils/cmd.py", line 313, in run_command
      self.distribution.run_command(command)
    File "/usr/lib/python3.7/distutils/dist.py", line 985, in run_command
      cmd_obj.run()
    File "/tmp/pip-req-build-v6dnit4h/setup.py", line 33, in run
      self.build_extension(ext)
    File "/tmp/pip-req-build-v6dnit4h/setup.py", line 110, in build_extension
      self._prepare_environment()
    File "/tmp/pip-req-build-v6dnit4h/setup.py", line 77, in _prepare_environment
      gcc, gpp = self._find_suitable_gcc_gpp()
    File "/tmp/pip-req-build-v6dnit4h/setup.py", line 73, in _find_suitable_gcc_gpp
      raise RuntimeError("gcc >= 8.0 not found on the system")
  RuntimeError: gcc >= 8.0 not found on the system
error
  ERROR: Failed building wheel for RAMA
  Running setup.py clean for RAMA
  Running command /usr/bin/python3 -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-req-build-v6dnit4h/setup.py'"'"'; __file__='"'"'/tmp/pip-req-build-v6dnit4h/setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(__file__) if os.path.exists(__file__) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' clean --all
  running clean
  'build/lib.linux-x86_64-3.7' does not exist -- can't clean it
  'build/bdist.linux-x86_64' does not exist -- can't clean it
  'build/scripts-3.7' does not exist -- can't clean it
Failed to build RAMA
Installing collected packages: RAMA
  Value for scheme.platlib does not match. Please report this to <https://github.com/pypa/pip/issues/9617>
  distutils: /usr/local/lib/python3.7/dist-packages
  sysconfig: /usr/lib/python3.7/site-packages
  Value for scheme.purelib does not match. Please report this to <https://github.com/pypa/pip/issues/9617>
  distutils: /usr/local/lib/python3.7/dist-packages
  sysconfig: /usr/lib/python3.7/site-packages
  Value for scheme.headers does not match. Please report this to <https://github.com/pypa/pip/issues/9617>
  distutils: /usr/local/include/python3.7/RAMA
  sysconfig: /usr/include/python3.7m/RAMA
  Value for scheme.scripts does not match. Please report this to <https://github.com/pypa/pip/issues/9617>
  distutils: /usr/local/bin
  sysconfig: /usr/bin
  Value for scheme.data does not match. Please report this to <https://github.com/pypa/pip/issues/9617>
  distutils: /usr/local
  sysconfig: /usr
  Additional context:
  user = False
  home = None
  root = None
  prefix = None
  Created temporary directory: /tmp/pip-record-s252ix_u
    Running command /usr/bin/python3 -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-req-build-v6dnit4h/setup.py'"'"'; __file__='"'"'/tmp/pip-req-build-v6dnit4h/setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(__file__) if os.path.exists(__file__) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' install --record /tmp/pip-record-s252ix_u/install-record.txt --single-version-externally-managed --compile --install-headers /usr/local/include/python3.7/RAMA
    running install
    running build
    running build_ext
    build_with_torch:OFF


    Testing gcc...
    ...has version 7.5.0
    ...has version 7.5.0-3ubuntu1~18.04)
    Testing gcc-7...
    ...has version 7.5.0
    ...has version 7.5.0-3ubuntu1~18.04)
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/tmp/pip-req-build-v6dnit4h/setup.py", line 128, in <module>
        setup_requires=['wheel']
      File "/usr/local/lib/python3.7/dist-packages/setuptools/__init__.py", line 153, in setup
        return distutils.core.setup(**attrs)
      File "/usr/lib/python3.7/distutils/core.py", line 148, in setup
        dist.run_commands()
      File "/usr/lib/python3.7/distutils/dist.py", line 966, in run_commands
        self.run_command(cmd)
      File "/usr/lib/python3.7/distutils/dist.py", line 985, in run_command
        cmd_obj.run()
      File "/usr/local/lib/python3.7/dist-packages/setuptools/command/install.py", line 61, in run
        return orig.install.run(self)
      File "/usr/lib/python3.7/distutils/command/install.py", line 589, in run
        self.run_command('build')
      File "/usr/lib/python3.7/distutils/cmd.py", line 313, in run_command
        self.distribution.run_command(command)
      File "/usr/lib/python3.7/distutils/dist.py", line 985, in run_command
        cmd_obj.run()
      File "/usr/lib/python3.7/distutils/command/build.py", line 135, in run
        self.run_command(cmd_name)
      File "/usr/lib/python3.7/distutils/cmd.py", line 313, in run_command
        self.distribution.run_command(command)
      File "/usr/lib/python3.7/distutils/dist.py", line 985, in run_command
        cmd_obj.run()
      File "/tmp/pip-req-build-v6dnit4h/setup.py", line 33, in run
        self.build_extension(ext)
      File "/tmp/pip-req-build-v6dnit4h/setup.py", line 110, in build_extension
        self._prepare_environment()
      File "/tmp/pip-req-build-v6dnit4h/setup.py", line 77, in _prepare_environment
        gcc, gpp = self._find_suitable_gcc_gpp()
      File "/tmp/pip-req-build-v6dnit4h/setup.py", line 73, in _find_suitable_gcc_gpp
        raise RuntimeError("gcc >= 8.0 not found on the system")
    RuntimeError: gcc >= 8.0 not found on the system
    Running setup.py install for RAMA ... error
ERROR: Command errored out with exit status 1: /usr/bin/python3 -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-req-build-v6dnit4h/setup.py'"'"'; __file__='"'"'/tmp/pip-req-build-v6dnit4h/setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(__file__) if os.path.exists(__file__) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' install --record /tmp/pip-record-s252ix_u/install-record.txt --single-version-externally-managed --compile --install-headers /usr/local/include/python3.7/RAMA Check the logs for full command output.
Exception information:
Traceback (most recent call last):
  File "/usr/local/lib/python3.7/dist-packages/pip/_internal/req/req_install.py", line 825, in install
    req_description=str(self.req),
  File "/usr/local/lib/python3.7/dist-packages/pip/_internal/operations/install/legacy.py", line 81, in install
    raise LegacyInstallFailure
pip._internal.operations.install.legacy.LegacyInstallFailure

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/usr/local/lib/python3.7/dist-packages/pip/_internal/cli/base_command.py", line 180, in _main
    status = self.run(options, args)
  File "/usr/local/lib/python3.7/dist-packages/pip/_internal/cli/req_command.py", line 199, in wrapper
    return func(self, options, args)
  File "/usr/local/lib/python3.7/dist-packages/pip/_internal/commands/install.py", line 402, in run
    pycompile=options.compile,
  File "/usr/local/lib/python3.7/dist-packages/pip/_internal/req/__init__.py", line 85, in install_given_reqs
    pycompile=pycompile,
  File "/usr/local/lib/python3.7/dist-packages/pip/_internal/req/req_install.py", line 829, in install
    six.reraise(*exc.parent)
  File "/usr/local/lib/python3.7/dist-packages/pip/_vendor/six.py", line 703, in reraise
    raise value
  File "/usr/local/lib/python3.7/dist-packages/pip/_internal/operations/install/legacy.py", line 71, in install
    cwd=unpacked_source_directory,
  File "/usr/local/lib/python3.7/dist-packages/pip/_internal/utils/subprocess.py", line 278, in runner
    spinner=spinner,
  File "/usr/local/lib/python3.7/dist-packages/pip/_internal/utils/subprocess.py", line 244, in call_subprocess
    raise InstallationSubprocessError(proc.returncode, command_desc)
pip._internal.exceptions.InstallationSubprocessError: Command errored out with exit status 1: /usr/bin/python3 -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-req-build-v6dnit4h/setup.py'"'"'; __file__='"'"'/tmp/pip-req-build-v6dnit4h/setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(__file__) if os.path.exists(__file__) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' install --record /tmp/pip-record-s252ix_u/install-record.txt --single-version-externally-managed --compile --install-headers /usr/local/include/python3.7/RAMA Check the logs for full command output.
Removed build tracker: '/tmp/pip-req-tracker-uo9l71am'
/content# 
[0] 0:bash*                                                                                       "2d83743e0816" 16:39 17-Sep-22
    opened by PhillipMaire 1
  • Edge Costs - Infinite

    Edge Costs - Infinite

    I am currently using your python solver. According to your documentation edge costs should be defined as floating numbers.

    In my graph, I simply want to prevent some specific nodes from belonging to the same cluster. I am planning to do this by creating "edges with a really high negative cost" between nodes that should not be merged together.

    • Do you think such an approach is possible with your solver?
    • Does your python solver support np.inf and -np.inf as edge costs?
    opened by ocetintas 1
  • Request for License and Usage Terms

    Request for License and Usage Terms

    Thank you for making the code online. May I request a license or terms /conditions update. Without a valid licence, the repo is deemed private for usage.

    https://opensource.stackexchange.com/questions/1720/what-can-i-assume-if-a-publicly-published-project-has-no-license

    opened by ittefaq11 1
  • Replaced thrust based cycle enum with more efficient CUDA based

    Replaced thrust based cycle enum with more efficient CUDA based

    1. CUDA based cycle enum is restricted till 5-cycles.
    2. Command line params.
    3. Dual reparameterization during GAEC.
    4. Removed redundant executables.
    5. Filter edges above a positive threshold during max. matching (previously 0).
    6. Filter invalid triangles during cycle enumeration to improve free GPU memory.
    opened by aabbas90 0
  • Bug fix and refactoring

    Bug fix and refactoring

    1. Changed triangulation scheme in conflicted cycles and refactoring
    2. Directed/Undirected graph checks
    3. Removed contiguous offset computation
    4. Changed COO sorting and edge contraction to use default tuple comparison operator and use thrust sorting directly. (30% faster than before).
    5. Refactored multicut MP
    opened by aabbas90 0
  • RuntimeError: Found bad contractions

    RuntimeError: Found bad contractions

    Hello :)

    thank you for providing this great repository!! Can you maybe help me out what exactly it means when I get the error 'RuntimeError: Found bad contractions'?

    Best, Jenny

    opened by JennySeidenschwarz 1
  • Not getting any cuts for nearly disconnected components

    Not getting any cuts for nearly disconnected components

    Hello,

    I'm trying multicut for a graph clustering alternative. I'm testing unweighted graphs with a very modular structure (see figure below) using multicut in an SBM-generated graph.

    I find that rama returns a partition where it puts very node in a single connected component instead of breaking it out into modules. If I randomize the edge weights, I get an apparently randomized partition.

    I understand that if all the costs are equal, there should be no reason to separate edges. However, all the edges that are not present in the edgelist have an implicit negative cost. Is there any way to go around this?

    Here's my code for reference:

    import numpy as np
import networkx as nx
import rama_py as mc

# helper 
def from_nxgraph_to_tuple(g, data=True):

    src = []
    dst = []
    weights = []
    for (i,j,w) in g.edges(data=data):
        src.append(i)
        dst.append(j)
        weights.append(w['weight'])
    
    return src,dst,weights

# generate graph
g = nx.stochastic_block_model([20,20,20], [ [0.8,0.01,0.01], [0.01,0.8,0.01], [0.01,0.01,0.8] ], directed=True)
nx.set_edge_attributes(g, values = 1.0, name = 'weight')
src,dst,weights = from_nxgraph_to_tuple(g)

# obtain multicut partition
opts = mc.multicut_solver_options("PD")
P = mc.rama_cuda(src,dst,weights, opts)

    I then plot the graph g with the obtained partition P, obtaining the following (the node label is the cluster id). I expected a partition of three clusters, each for every almost-disconnected component. I get a partition of the whole graph as a single component image

    If, instead, I randomize the weights (i.e., weights = np.random.rand( len(src) )), I obtain a random partition (node how each node is its own cluster): image

    Are these behaviors expected?

    Thanks a lot!

    opened by blas-ko 2
Owner
Paul Swoboda
Paul Swoboda
GitHub
Problem-943.-ACMP - Problem 943. ACMP

Problem-943.-ACMP В "main.py" расположен вариант моего решения задачи 943 с серв

Konstantin Dyomshin 2 Aug 19, 2022
Birthday-problem - The birthday problem asks for the probability that, in a set of n randomly chosen people, at least two will share a birthday

Birthday-problem In probability theory, the birthday problem asks for the probab

null 5 Jan 5, 2023
Official PyTorch implementation of "Rapid Neural Architecture Search by Learning to Generate Graphs from Datasets" (ICLR 2021)

Rapid Neural Architecture Search by Learning to Generate Graphs from Datasets This is the official PyTorch implementation for the paper Rapid Neural A

null 48 Dec 26, 2022
Python Rapid Artificial Intelligence Ab Initio Molecular Dynamics

Python Rapid Artificial Intelligence Ab Initio Molecular Dynamics

null 14 Nov 6, 2022
Simulator for FRC 2022 challenge: Rapid React

rrsim Simulator for FRC 2022 challenge: Rapid React out-1.mp4 Usage In order to run the simulator use the following: python3 rrsim.py [config_path] wh

null 1 Jan 18, 2022
RL algorithm PPO and IRL algorithm AIRL written with Tensorflow.

RL algorithm PPO and IRL algorithm AIRL written with Tensorflow. They have a parallel sampling feature in order to increase computation speed (especially in high-performance computing (HPC)).

Fangjian Li 3 Dec 28, 2021
Code for the paper A Theoretical Analysis of the Repetition Problem in Text Generation

A Theoretical Analysis of the Repetition Problem in Text Generation This repository share the code for the paper "A Theoretical Analysis of the Repeti

Zihao Fu 37 Nov 21, 2022
PGPortfolio: Policy Gradient Portfolio, the source code of "A Deep Reinforcement Learning Framework for the Financial Portfolio Management Problem"(https://arxiv.org/pdf/1706.10059.pdf).

This is the original implementation of our paper, A Deep Reinforcement Learning Framework for the Financial Portfolio Management Problem (arXiv:1706.1

Zhengyao Jiang 1.5k Dec 29, 2022
Code for the paper "Relation of the Relations: A New Formalization of the Relation Extraction Problem"

This repo contains the code for the EMNLP 2020 paper "Relation of the Relations: A New Paradigm of the Relation Extraction Problem" (Jin et al., 2020)

YYY 27 Oct 26, 2022
Source code for the Paper: CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints}

CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints Installation Run pipenv install (at your own risk with --skip-lo

Autonomous Learning Group 65 Dec 27, 2022
We propose a new method for effective shadow removal by regarding it as an exposure fusion problem.

Auto-exposure fusion for single-image shadow removal We propose a new method for effective shadow removal by regarding it as an exposure fusion proble

Qing Guo 146 Dec 31, 2022
Data and Code for ACL 2021 Paper "Inter-GPS: Interpretable Geometry Problem Solving with Formal Language and Symbolic Reasoning"

Introduction Code and data for ACL 2021 Paper "Inter-GPS: Interpretable Geometry Problem Solving with Formal Language and Symbolic Reasoning". We cons

Pan Lu 81 Dec 27, 2022
MWPToolkit is a PyTorch-based toolkit for Math Word Problem (MWP) solving.

MWPToolkit is a PyTorch-based toolkit for Math Word Problem (MWP) solving. It is a comprehensive framework for research purpose that integrates popular MWP benchmark datasets and typical deep learning-based MWP algorithms.

null 119 Jan 4, 2023
Code for the paper "Reinforcement Learning as One Big Sequence Modeling Problem"

Trajectory Transformer Code release for Reinforcement Learning as One Big Sequence Modeling Problem. Installation All python dependencies are in envir

Michael Janner 269 Jan 5, 2023
[ICCV-2021] An Empirical Study of the Collapsing Problem in Semi-Supervised 2D Human Pose Estimation

An Empirical Study of the Collapsing Problem in Semi-Supervised 2D Human Pose Estimation (ICCV 2021) Introduction This is an official pytorch implemen

rongchangxie 42 Jan 4, 2023
Definition of a business problem according to Wilson Lower Bound Score and Time Based Average Rating

Wilson Lower Bound Score, Time Based Rating Average In this study I tried to calculate the product rating and sorting reviews more accurately. I have

null 3 Sep 30, 2021
An end-to-end regression problem of predicting the price of properties in Bangalore.

Bangalore-House-Price-Prediction An end-to-end regression problem of predicting the price of properties in Bangalore. Deployed in Heroku using Flask.

Shruti Balan 1 Nov 25, 2022
Utility tools for the "Divide and Remaster" dataset, introduced as part of the Cocktail Fork problem paper

Divide and Remaster Utility Tools Utility tools for the "Divide and Remaster" dataset, introduced as part of the Cocktail Fork problem paper The DnR d

Darius Petermann 46 Dec 11, 2022
Tracking Pipeline helps you to solve the tracking problem more easily

Tracking_Pipeline Tracking_Pipeline helps you to solve the tracking problem more easily I integrate detection algorithms like: Yolov5, Yolov4, YoloX,

VNOpenAI 32 Dec 21, 2022