flagser_weighted does not terminate/takes forever when coeff > 2

[ulupo]

Description

flagser_weighted seems to take forever or even not to terminate, on computations of trivial weighted graphs whencoeff is 3 or above.

Steps/Code to Reproduce

import numpy as np

X = np.random.random((5, 5))
np.fill_diagonal(X, 0.)

flagser_weighted(X, coeff=3)

Expected Results

flagser_weighted terminates in a reasonable time.

Actual Results

flagser_weighted does not terminate. But note that it would terminate if I had X = np.random.random((3, 3)) or X = np.random.random((4, 4)) instead.

Versions

macOS-10.15.6-x86_64-i386-64bit Python 3.8.2 (default, May 6 2020, 02:49:43) [Clang 4.0.1 (tags/RELEASE_401/final)] pyflagser 0.4.0

I observe this both with the PyPI version and with the developer install.

[ulupo]

@gtauzin flagging this for your interest.

[MonkeyBreaker]

@ulupo thanks for reporting, I tried directly on flagser to see if it also encounter this interminable run.

With the following code, I added a print for the generated vertices and edges in function flagser_weighted::_extract_weighted_graph

#!/usr/bin/env python

import numpy as np
import pyflagser

x = np.random.random((5, 5))
np.fill_diagonal(x, 0.)
print(x)
pyflagser.flagser_weighted(x, coeff=3)

Intermediate print:

x = [[0.         0.84707679 0.18398522 0.96259247 0.54167621]
 [0.34772313 0.         0.97810088 0.72855808 0.27364796]
 [0.18882756 0.89481899 0.         0.52133444 0.17973438]
 [0.38915903 0.56670509 0.07425402 0.         0.60400914]
 [0.81306144 0.907335   0.23578294 0.27208927 0.        ]]
vertices = [0. 0. 0. 0. 0.]
edges = [[0.         1.         0.84707679]
 [0.         2.         0.18398522]
 [0.         3.         0.96259247]
 [0.         4.         0.54167621]
 [1.         0.         0.34772313]
 [1.         2.         0.97810088]
 [1.         3.         0.72855808]
 [1.         4.         0.27364796]
 [2.         0.         0.18882756]
 [2.         1.         0.89481899]
 [2.         3.         0.52133444]
 [2.         4.         0.17973438]
 [3.         0.         0.38915903]
 [3.         1.         0.56670509]
 [3.         2.         0.07425402]
 [3.         4.         0.60400914]
 [4.         0.         0.81306144]
 [4.         1.         0.907335  ]
 [4.         2.         0.23578294]
 [4.         3.         0.27208927]]

Then I created a file to pass it directly to flagser test.txt. And then run flagser with coefficients enable:

./flagser-coefficients --out result_coeff_3.txt --modulus 3 --max-dim -1 --min-dim 0 --filtration max test.txt

The program finish almost instantly, you can check the result in result_coeff_3.txt

Seems that the issue is on pyflagser let me know if there's an error in my procedure, I'll investigate if there's an error with the bindings.

[ulupo]

@MonkeyBreaker thank you! Indeed I do not think this issue has a mathematical basis, and since the C++ code is immune it must be about the bindings. Thanks for looking into this.

[MonkeyBreaker]

Okay, seems I found out the issue.

In the past, flagser manages options by command line arguments, and it forwards everywhere this arguments. And of course, again, I failed on checking all possible functions that received a certain argument. I did not add test for different coeffthan 2, so I did not catch this.

The issue can be resolved by adding this in src/flagser_bindings.cpp starting at line 29:

// Passing coeff as a command line argument
std::string str_modulus = std::to_string(modulus);
named_arguments["modulus"] = str_modulus.c_str();

If it's urgent I can create a PR just for adding this + a test of course :).

But, I modified some weeks ago flagser library to better manages this arguments. Daniel already merged the changes. I would prefer to make a PR integrating the new changes added in flagser, update the bindings, and we shall not encounter this issues in the future.

What do you think ?

[ulupo]

But, I modified some weeks ago flagser library to better manages this arguments. Daniel already merged the changes. I would prefer to make a PR integrating the new changes added in flagser, update the bindings, and we shall not encounter this issues in the future.

Go for it! Thanks :)