pawelswoboda / rama Goto Github PK

View Code? Open in Web Editor NEW

78.0 78.0 14.0 19.46 MB

License: BSD 3-Clause "New" or "Revised" License

CMake 2.85% C++ 23.56% Cuda 70.43% C 0.11% Python 3.04%

rama's People

Contributors

Stargazers

Watchers

Forkers

aabbas90 atlantisanalytics digital-idiot jungwonkim jin-park-oci peterzhousz trendingtechnology ocetintas mushroommaula bqm1111 yashpatel1994 omathiak yi-guang

rama's Issues

pip install failing due to submodules not getting fetched

Hello :)
are you ever planning to publish version working with more recent coda versions? I would love to continue using you project, but it's a bit hard with newer pytorch versions.
Would be awesome! :)

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

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.

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

Demo Code?

Hi @pawelswoboda

This work is awesome! Do you have any script or hints for generating the cover segmentation figure?

Thanks!

Unknown CMake command "CPMAddPackage" when building

hello, I downloaded the RAMA source code to the /src/RAMA-master/RAMA-master directory and then I executed the following command. Since I was using conda for package management, I activated my conda environment emseg beforehand

cd /src/RAMA-master/RAMA-master
python setup.py install

This resulted in the following error on the console, aside from the WARNING message, the obvious error is that the

CMake Error at CMakeLists.txt:41 (CPMAddPackage):
  Unknown CMake command "CPMAddPackage".

setup.py:10: DeprecationWarning: pkg_resources is deprecated as an API. See https://setuptools.pypa.io/en/latest/pkg_resources.html
  from pkg_resources import parse_version
/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/__init__.py:80: _DeprecatedInstaller: setuptools.installer and fetch_build_eggs are deprecated.
!!

        ********************************************************************************
        Requirements should be satisfied by a PEP 517 installer.
        If you are using pip, you can try `pip install --use-pep517`.
        ********************************************************************************

!!
  dist.fetch_build_eggs(dist.setup_requires)
running install
/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/cmd.py:66: SetuptoolsDeprecationWarning: setup.py install is deprecated.
!!

        ********************************************************************************
        Please avoid running ``setup.py`` directly.
        Instead, use pypa/build, pypa/installer or other
        standards-based tools.

        See https://blog.ganssle.io/articles/2021/10/setup-py-deprecated.html for details.
        ********************************************************************************

!!
  self.initialize_options()
/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/cmd.py:66: EasyInstallDeprecationWarning: easy_install command is deprecated.
!!

        ********************************************************************************
        Please avoid running ``setup.py`` and ``easy_install``.
        Instead, use pypa/build, pypa/installer or other
        standards-based tools.

        See https://github.com/pypa/setuptools/issues/917 for details.
        ********************************************************************************

!!
  self.initialize_options()
running bdist_egg
running egg_info
writing RAMA.egg-info/PKG-INFO
writing dependency_links to RAMA.egg-info/dependency_links.txt
writing top-level names to RAMA.egg-info/top_level.txt
reading manifest file 'RAMA.egg-info/SOURCES.txt'
adding license file 'LICENSE'
writing manifest file 'RAMA.egg-info/SOURCES.txt'
installing library code to build/bdist.linux-x86_64/egg
running install_lib
running build_ext
build_with_torch:OFF


Testing gcc...
...has version 10.5.0
Found suitable gcc/g++ version gcc g++
CMake Error at CMakeLists.txt:41 (CPMAddPackage):
  Unknown CMake command "CPMAddPackage".


-- Configuring incomplete, errors occurred!
See also "/src/RAMA-master/RAMA-master/build/temp.linux-x86_64-cpython-38/CMakeFiles/CMakeOutput.log".
Traceback (most recent call last):
  File "setup.py", line 120, in <module>
    setup(
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/__init__.py", line 103, in setup
    return distutils.core.setup(**attrs)
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/core.py", line 185, in setup
    return run_commands(dist)
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/core.py", line 201, in run_commands
    dist.run_commands()
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/dist.py", line 969, in run_commands
    self.run_command(cmd)
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/dist.py", line 963, in run_command
    super().run_command(command)
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/dist.py", line 988, in run_command
    cmd_obj.run()
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/command/install.py", line 84, in run
    self.do_egg_install()
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/command/install.py", line 132, in do_egg_install
    self.run_command('bdist_egg')
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/cmd.py", line 318, in run_command
    self.distribution.run_command(command)
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/dist.py", line 963, in run_command
    super().run_command(command)
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/dist.py", line 988, in run_command
    cmd_obj.run()
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/command/bdist_egg.py", line 167, in run
    cmd = self.call_command('install_lib', warn_dir=0)
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/command/bdist_egg.py", line 153, in call_command
    self.run_command(cmdname)
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/cmd.py", line 318, in run_command
    self.distribution.run_command(command)
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/dist.py", line 963, in run_command
    super().run_command(command)
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/dist.py", line 988, in run_command
    cmd_obj.run()
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/command/install_lib.py", line 11, in run
    self.build()
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/command/install_lib.py", line 111, in build
    self.run_command('build_ext')
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/cmd.py", line 318, in run_command
    self.distribution.run_command(command)
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/dist.py", line 963, in run_command
    super().run_command(command)
  File "/src/anaconda3/envs/emseg/lib/python3.8/site-packages/setuptools/_distutils/dist.py", line 988, in run_command
    cmd_obj.run()
  File "setup.py", line 33, in run
    self.build_extension(ext)
  File "setup.py", line 117, in build_extension
    subprocess.check_call(['cmake', ext.sourcedir] + cmake_args, cwd=self.build_temp, env=env)
  File "/src/anaconda3/envs/emseg/lib/python3.8/subprocess.py", line 364, in check_call
    raise CalledProcessError(retcode, cmd)
subprocess.CalledProcessError: Command '['cmake', '/src/RAMA-master/RAMA-master', '-DCMAKE_LIBRARY_OUTPUT_DIRECTORY=/src/RAMA-master/RAMA-master/build/lib.linux-x86_64-cpython-38', '-DPYTHON_EXECUTABLE=/src/anaconda3/envs/emseg/bin/python', '-DCMAKE_BUILD_TYPE=Release']' returned non-zero exit status 1.

My relative tools' version:

CUDA Version: 11.7 
gcc version 10.5.0
cmake version 3.16.3
pip 23.3.2

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

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

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):

Are these behaviors expected?

Thanks a lot!

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?

Found bad contractions for nn graph

Hi there!
First of all, thanks for open-sourcing this super cool algorithm! Also saw you guys are active wrt to issues, so I'll give it a shot :)

I'm encountering the "Found bad contractions" Runtime Error. As input, I have a Nearest Neighbor graph representation consisting of source nodes, connecting nodes, and edge costs. I'm using a 10-NN graph with 3600 source nodes.
Here are the prints for .shape, .min() and .max()

source_nodes (36000,) 0 3599
connecting_nodes (36000,) 0 3599
costs (36000,) 0.0 1.0314723253250122

Inside source and connecting nodes, it looks something like this:

source_nodes [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
connecting_nodes [0, 60, 1, 61, 120, 2, 121, 62, 122, 3, 1, 61, 2, 0, 60, 62, 121, 3, 120, 122]

For this case, RAMA works just fine without any error, and produces 0s for all nodes (as expected).

But when I then normalize the costs with mean 0 and std 1, my range is shifted to the negative (-1 to 1), causing the error.
I made sure that all vertices of nodes connect to themselves (e.g node 0 to 0) have a cost of 0.0.

I've tried to look at the implementation and traced back the error to a diagonal assertion. Can you maybe help here what I'm doing wrong?

Here is some code that might help:

source_nodes = np.repeat(np.arange(neigh_dist.shape[0]), repeats=args.k_knn).tolist()
connecting_nodes = nn.tolist()
costs = neigh_dist.reshape(-1)

costs = (costs - np.mean(costs)) / np.std(costs).astype(np.float32).tolist()

...

res = rama_py.rama_cuda(source_nodes, connecting_nodes, costs, opts)

Thanks in advance!
Leon

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

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!

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?