KuhnMunkresMinimalWeightBipartitePerfectMatching does not seem to accept Double.NaN

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

KuhnMunkresMinimalWeightBipartitePerfectMatching does not seem to accept Double.NaN

Ci Pher
Hi,

I'm using KuhnMunkresMinimalWeightBipartitePerfectMatching from JgraphT for Assignment Problem.

When I pass Double.NaN as weight for any assignment, the algorithm seems to take forever (12 minutes and counting as of last run). It works fine when Double.MAX_VALUE is passed.

For example, for bipartite graph corresponding to following cost matrix - 
                                                  //  1                                                      2  
costs = new double[][]{{1.0 ,                           Double.MAX_VALUE}, // 3
{Double.MAX_VALUE, Double.MAX_VALUE}}; // 4

Algorithm returns matching - 

1 3 1.0
2 4 1.7976931348623157E308

Which is fine, I can always compare EdgeWeight with Double.MAX_VALUE. But Ideally, I'd like to pass Double.NaN to indicate that these edges should not be considered to begin with.

Is it possible?

(HopcroftKarpBipartiteMatching from JGraphT seems to work fine even with Double.NaN as values.)



Thanks.


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: KuhnMunkresMinimalWeightBipartitePerfectMatching does not seem to accept Double.NaN

J Kinable
Hi,

You should not pass Double.NaN as an edge weight. The behavior of the class is pretty much undefined if you do so. Where did you read that you can disable edge that way? I'm pretty sure it's not stated anywhere in any class.

To disable edges, you have (at least) 4 different possibilities:

1. Delete the edge (obviously). Later you can re-add the edge. 
or
2. Create a working graph, i.e. a copy of the original graph without that edge.
or
or

br,

Joris Kinable

On Mon, Jan 2, 2017 at 2:56 PM, Ci Pher <[hidden email]> wrote:
Hi,

I'm using KuhnMunkresMinimalWeightBipartitePerfectMatching from JgraphT for Assignment Problem.

When I pass Double.NaN as weight for any assignment, the algorithm seems to take forever (12 minutes and counting as of last run). It works fine when Double.MAX_VALUE is passed.

For example, for bipartite graph corresponding to following cost matrix - 
                                                  //  1                                                      2  
costs = new double[][]{{1.0 ,                           Double.MAX_VALUE}, // 3
{Double.MAX_VALUE, Double.MAX_VALUE}}; // 4

Algorithm returns matching - 

1 3 1.0
2 4 1.7976931348623157E308

Which is fine, I can always compare EdgeWeight with Double.MAX_VALUE. But Ideally, I'd like to pass Double.NaN to indicate that these edges should not be considered to begin with.

Is it possible?

(HopcroftKarpBipartiteMatching from JGraphT seems to work fine even with Double.NaN as values.)



Thanks.


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users