Time complexity of max_weight_matching

[Jun Fujisaki]

Hello.

I'm using  networkx.algorithms.matching.max_weight_matching and now going to confirm that the time complexity of max_weight_matching as O(number of nodes**3) as described in the document, but there is no function returning the number of iterations in the actual calculation.

I think I can solve it if I count the number of iterations at the line just below line 786 "for w in G.neighbors(v):" in "\networkx\algorithms\matching.py" because the alternating path is created there by searching the all nodes.

However, the result was O(number of nodes**2), and I'm wondering if I should also count the number at the other line.

If does anyone know about this, please tell me how to count exactly the number of iterations.

Thanks.

[Dan Schult]

The line you reference is in a loop that calls `ScanBlossom`.  Now I don't know the details of this code, but the name of that function suggests that it could iterate over the nodes -- which would give O(n^3).

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/d991f7dd-c669-41ef-a29f-a6e74d0f75cfn%40googlegroups.com.

[Jun Fujisaki]

Thank you for reply. I tried to increment the number of iterations within "ScanBlossom" function but that resulted in O(n).

Though I don't know well about this algorithm, now I think other functions matter such as "addBlossom" and "expandBlossom".

2021年6月28日月曜日 0:32:01 UTC+9 Dan Schult:

[Jun Fujisaki]

I'm still wondering which line I count the number of iterations in  "max_weight_matching" to make sure O(n^3).

Does anyone have an idea for it?

Thanks.

2021年6月28日月曜日 9:23:49 UTC+9 Jun Fujisaki:

[David Menéndez Hurtado]

Counting execution of lines if code is not a great proxy for big-Oh. For example, removing an element from the beginning of a list is one line, but it takes O(n) because the rest of the list has to be reorganised.

I would measure wall time instead.

/David 

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/c52e9a45-8fdd-4a93-8a16-639691e393bfn%40googlegroups.com.

[Jun Fujisaki]

Thank you very much, David.  Counting execution of lines will work, and the measurement of wall time is also a good idea. I will try them. 

Thanks.

2021年6月30日水曜日 18:53:15 UTC+9 Daπid:

[Jun Fujisaki]

 I have a simple question.

The time complexity of max_weight_matching is described as "O(number_of_nodes ** 3) " in the manual (https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.matching.max_weight_matching.html).

However, it is written as O(nodes*edges*log(nodes)) in the reference paper, “Efficient Algorithms for Finding Maximum Matching in Graphs” (Zvi Galil, ACM Computing Surveys, 1986), of course the author introduces O(nodes**3) algorithm in the paper as one of the previous works.

Does anyone know about this?  If I misunderstand, please point it out.

Thanks.

2021年6月30日水曜日 21:31:33 UTC+9 Jun Fujisaki: