bjoern-andres / graph Goto Github PK

View Code? Open in Web Editor NEW

232.0 232.0 86.0 558 KB

Graphs and Graph Algorithms in C++, including Minimum Cost (Lifted) Multicuts

Home Page: http://www.andres.sc/graph.html

C++ 98.83% CMake 1.17%

graph's People

Contributors

Stargazers

Watchers

Forkers

mark-matten dimatura ibeling wang17 aaronjoel kalofoli levinkov anmolsingh20 sarvex langdead githubzqk derthorsten zincxenon ezfin yaoxiaokui caomw ernest-dzf hertz1239 oztc bluescarni maasouza deliangye shllhs sue602 vivzqs xuelang-wang glancefox rempfler oronanschel janhendriklange pinnamanivenkat tangmin0714 lpplbiubiubiub mheistermann jutanke wospt jizhihang pawelswoboda bhuwendongchao excellenperson chandanksingh chenyuan1994 clarklj constantinpape chapayghub riverm4n unilang hypercubic ktp-forked-repos trantorrepository zhuyifan1993 dorahuiki inocsin kewenjing1020 decayale kangzhiyong shitou7630 babaee graphtools tide999 cybertron1609 lwllovewf2010 hustllz drlilab em-yu superjay1996 gregoryistratov fuyiqing czfdlut xy0xy jannikirmai schaudge chenchr rlombard ezhangle chinahuangyong malay-gaherwar hmaarrfk albrechtl982 shixia-w yes-jumby tdurgesh08

graph's Issues

template error

When I try to compile it on mac, I get this error:

graph/include/andres/graph/multicut/lp.hxx:31:21: note: 'lp' should be declared prior to the call site or in namespace 'andres::graph' std::vector<double> lp(CompleteGraph<VISITOR> const& graph, ECA const& edgeCosts, VIS& visitor, size_t numberOfIterations = std::numeric_limits<size_t>::max())

std namespace issue in lifted multicut unit tests

I am not sure if I am doing something wrong but there seem to be missing namespace declarations in the lifted multicut unit tests when compiling the project.
I added std namespace declarations so that the code now compiles: jutanke@39edadb

I am working on Ubuntu 16.04 with Gurobi 7.5.1

lifted mc graph

the lifted graph, in a lifted multicut setting has to contain all edges of the 'orginal-graph',right?
Is there a way to construct a "semi-view" graph which takes all the edges from the orginal-graph, and some additional edges.

One can do that relatively simple, but I was wondering if such a thing is already implemented.

FFWD to 2019

Great well researched with right kind of right-sized abstractions.

But. Not standard C++. 2019Q4 standard C++ is ISO C++17. Some benefits of moving the code completely to standard C++ are:

increased performance
- by using more compile time code, constexpr code, smart pointers ...
smaller code
- using the std algorithms and types (std::array, std::optional, ... )
cleaner code
- simplification due to modernization

A big cleaning for good housekeeping in essence ...

real worl lifted mc models

are there some real work hdf5 lifted multicut models available.
Would be great to test new solvers on non synthetic models!

Greetings

How to use the nl-lmp to solve a new problem

I'm new to the Cmake things. Is there someone who could provide some guidance and suggestions about how to solve a new problem with the nl-lmp solution here?

I've cloned the repository, and successfully installed by run 'cmake .', 'make', and 'ctest -W', but not clear what's the next step. How to write a script to solve a new nl-lmp problem? Which file should be imported, and which function should be called to solve the problem?

Thanks pretty much.

lifted mc algorithms API

@bjoern-andres why are the results of lifted mc algorithms passed by edge labels of the lifted graph.
I propose to use the connected comp. labeling of the orginal graph. And there should be the guarantee that this connected comp. labeling is valid wrt. the path constraints / lifted stuff (all nodes with the same number must be connected with a path in the orginal graph).

Also internally, algorithms could use that representation since it should be cheaper in memory.

Test failing on OSX

A graph test is failing on the OSX conda-forge pipeline. The test is test-graph-multicut-greedy-additive. I have added some debug output to the test, see the patch here:

https://github.com/conda-forge/staged-recipes/pull/2807/files#diff-5f7894804b06e6bb15d1ca73db6353d5R1

With the output debug enabled, this is the screen output of the test:

https://travis-ci.org/conda-forge/staged-recipes/builds/220550265#L553

Python Bindings

Would you like some python bindings?
I would propose to use https://github.com/DerThorsten/Boost.NumPy to interface with numpy.ndarray (the nd-array of python) and write code on top of that to interface with your marray (where is the latest version ?)
On top of that I would like to add high level bindings for lifted multicuts and other algorithms to python.

Cannot build graph on v1.11

Error:

[  3%] Built target solve-lmp-grid-graph
[  7%] Built target solve-mp-grid-graph
[ 11%] Built target solve-mp-complete-graph
[ 14%] Built target solve-mp
[ 16%] Building CXX object CMakeFiles/lift-mp-grid-graph.dir/src/command-line-tools/lift-mp-grid-graph.cxx.o
In file included from /home/hanslovskyp/git/graph/src/command-line-tools/lift-mp-grid-graph.cxx:13:
/home/hanslovskyp/git/graph/include/andres/graph/lifting.hxx: In instantiation of ‘void andres::graph::lift(const andres::graph::GridGraph<2, INPUT_GRAPH_VISITOR>&, OUTPUT_GRAPH&, std::size_t, std::size_t, andres::graph::LiftingMetric) [with INPUT_GRAPH_VISITOR = andres::graph::IdleGraphVisitor<long unsigned int>; OUTPUT_GRAPH = andres::graph::Graph<>; std::size_t = long unsigned int]’:
/home/hanslovskyp/git/graph/src/command-line-tools/lift-mp-grid-graph.cxx:124:119:   required from here
/home/hanslovskyp/git/graph/include/andres/graph/lifting.hxx:206:62: error: call of overloaded ‘abs(std::size_t)’ is ambiguous
                         const std::size_t distance = std::abs(x - cv[0]) + std::abs(y - cv[1]);
                                                      ~~~~~~~~^~~~~~~~~~~
In file included from /usr/include/c++/8.2.1/cstdlib:77,
                 from /usr/include/c++/8.2.1/ext/string_conversions.h:41,
                 from /usr/include/c++/8.2.1/bits/basic_string.h:6400,
                 from /usr/include/c++/8.2.1/string:52,
                 from /usr/include/c++/8.2.1/stdexcept:39,
                 from /home/hanslovskyp/git/graph/src/command-line-tools/lift-mp-grid-graph.cxx:1:
/usr/include/c++/8.2.1/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   abs(long __i) { return __builtin_labs(__i); }
   ^~~
/usr/include/c++/8.2.1/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   abs(long long __x) { return __builtin_llabs (__x); }
   ^~~
/usr/include/c++/8.2.1/bits/std_abs.h:70:3: note: candidate: ‘constexpr double std::abs(double)’
   abs(double __x)
   ^~~
/usr/include/c++/8.2.1/bits/std_abs.h:74:3: note: candidate: ‘constexpr float std::abs(float)’
   abs(float __x)
   ^~~
/usr/include/c++/8.2.1/bits/std_abs.h:78:3: note: candidate: ‘constexpr long double std::abs(long double)’
   abs(long double __x)
   ^~~
In file included from /usr/include/c++/8.2.1/cstdlib:75,
                 from /usr/include/c++/8.2.1/ext/string_conversions.h:41,
                 from /usr/include/c++/8.2.1/bits/basic_string.h:6400,
                 from /usr/include/c++/8.2.1/string:52,
                 from /usr/include/c++/8.2.1/stdexcept:39,
                 from /home/hanslovskyp/git/graph/src/command-line-tools/lift-mp-grid-graph.cxx:1:
/usr/include/stdlib.h:837:12: note: candidate: ‘int abs(int)’
 extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
            ^~~
In file included from /home/hanslovskyp/git/graph/src/command-line-tools/lift-mp-grid-graph.cxx:13:
/home/hanslovskyp/git/graph/include/andres/graph/lifting.hxx:206:84: error: call of overloaded ‘abs(std::size_t)’ is ambiguous
                         const std::size_t distance = std::abs(x - cv[0]) + std::abs(y - cv[1]);
                                                                            ~~~~~~~~^~~~~~~~~~~
In file included from /usr/include/c++/8.2.1/cstdlib:77,
                 from /usr/include/c++/8.2.1/ext/string_conversions.h:41,
                 from /usr/include/c++/8.2.1/bits/basic_string.h:6400,
                 from /usr/include/c++/8.2.1/string:52,
                 from /usr/include/c++/8.2.1/stdexcept:39,
                 from /home/hanslovskyp/git/graph/src/command-line-tools/lift-mp-grid-graph.cxx:1:
/usr/include/c++/8.2.1/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   abs(long __i) { return __builtin_labs(__i); }
   ^~~
/usr/include/c++/8.2.1/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   abs(long long __x) { return __builtin_llabs (__x); }
   ^~~
/usr/include/c++/8.2.1/bits/std_abs.h:70:3: note: candidate: ‘constexpr double std::abs(double)’
   abs(double __x)
   ^~~
/usr/include/c++/8.2.1/bits/std_abs.h:74:3: note: candidate: ‘constexpr float std::abs(float)’
   abs(float __x)
   ^~~
/usr/include/c++/8.2.1/bits/std_abs.h:78:3: note: candidate: ‘constexpr long double std::abs(long double)’
   abs(long double __x)
   ^~~
In file included from /usr/include/c++/8.2.1/cstdlib:75,
                 from /usr/include/c++/8.2.1/ext/string_conversions.h:41,
                 from /usr/include/c++/8.2.1/bits/basic_string.h:6400,
                 from /usr/include/c++/8.2.1/string:52,
                 from /usr/include/c++/8.2.1/stdexcept:39,
                 from /home/hanslovskyp/git/graph/src/command-line-tools/lift-mp-grid-graph.cxx:1:
/usr/include/stdlib.h:837:12: note: candidate: ‘int abs(int)’
 extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
            ^~~
make[2]: *** [CMakeFiles/lift-mp-grid-graph.dir/build.make:63: CMakeFiles/lift-mp-grid-graph.dir/src/command-line-tools/lift-mp-grid-graph.cxx.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:221: CMakeFiles/lift-mp-grid-graph.dir/all] Error 2
make: *** [Makefile:95: all] Error 2

gcc --version
gcc (GCC) 8.2.1 20181127
Copyright (C) 2018 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Steps to reproduce:

git clone [email protected]:bjoern-andres/graph
cd graph
mkdir build-1.11
cd build-1.11
git checkout v1.11
cmake .. -DCMAKE_INSTALL_PREFIX=$LOCAL
make

Might lack of file 'marray.h'

In the file ./include/nl-lmp/problem.hxx : line 5, it includes a file 'andres/marray.h'. But there is no such file in the path.

edge-path / node-path confusion

In the multicut ilp implementation graph/ilp.hxx you search for a path in
(https://github.com/bjoern-andres/graph/blob/master/include/andres/graph/multicut/ilp.hxx#L89)

The path is filled with edge indices.
(https://github.com/bjoern-andres/graph/blob/master/include/andres/graph/shortest-paths.hxx#L639).

But later on in line 100 the path is used as if it would be filled with node indices.
(https://github.com/bjoern-andres/graph/blob/master/include/andres/graph/multicut/ilp.hxx#L100)

Possible bug in overload resolution

I am running in a compilation failure on 32bit platforms for the shortest-paths.cxx test. The symptoms are the following:

/home/bluescarni/repos/graph/include/andres/graph/shortest-paths.hxx:1542:22: error: lvalue required as left operand of assignment
         distances[v] = infinity;
         ~~~~~~~~~~~~~^~~~~~~~~~
/home/bluescarni/repos/graph/include/andres/graph/shortest-paths.hxx:1547:19: error: lvalue required as left operand of assignment
     distances[vs] = 0;
     ~~~~~~~~~~~~~~^~~
/home/bluescarni/repos/graph/include/andres/graph/shortest-paths.hxx:1565:45: error: lvalue required as left operand of assignment
                     distances[it->vertex()] = alternativeDistance;
                     ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

The problem seems to be that, on some 32bit platforms, std::size_t and unsigned are the same type. What happens then is that this call:

https://github.com/bjoern-andres/graph/blob/master/include/andres/graph/shortest-paths.hxx#L1364

resolves to this function (on 32bit platforms)

https://github.com/bjoern-andres/graph/blob/master/include/andres/graph/shortest-paths.hxx#L1376

rather than this:

https://github.com/bjoern-andres/graph/blob/master/include/andres/graph/shortest-paths.hxx#L1448

So when the flow finally gets inside this function:

https://github.com/bjoern-andres/graph/blob/master/include/andres/graph/shortest-paths.hxx#L1516

DISTANCE_ITERATOR is of type UnitEdgeValueIterator, and the line distances[v] = infinity; fails because distances[v] yields a value rather than a reference.

The issue can be reproduced on 32bit build on MSVC, clang and gcc.