Question regarding min wt perfect matching

[Srinivas]

Hi,
I am looking for a min-weight perfect matching algorithm/
implementation. I came across a few papers that discuss such a
problem. I found this in NetworkX which is a max-matching. Can this be
used for my purpose of finding the min-wt perfect matching? I have n^2
nodes ...can get perfect matching.

I tried looking at the implementation of Joris van Rantwijk. But,
then, gave up for now.

I think I can negate all the edge weights and then use
"networkx.max_weight_matching(G)" . And, if I have a graph where all
the edge weights are 1, then, I think I can **JUST** use
"networkx.max_weight_matching(G)" to get what I want. Right?

Please let me know if I am right. Any suggestions would be
appreciated.

Thanks,
Sri.

[Srinivas]

regarding number of nodes, I have 2^k nodes, which will enable me to
get a perfect matching.

[Srinivas]

Hi all,
For some reason, I am not getting a nice matching when I
execute "max-weight_matching" on a graph with negative weights. Am I
doing something wrong here? My aim is to get a min-wt matching on a
given graph with edge-weights. I presumed that if I negate all the
weights of the given graph and run "max-wt-matching", I will achieve
what I want. But, the function "max-weight-matching" doesn't seem to
work with negative weights.

Is this a bug or am I doing something wrong??

This is what I did :

==============================================================
srivathsan@Adithya:~$ ipython
Python 2.6.2 (release26-maint, Apr 19 2009, 01:56:41)
Type "copyright", "credits" or "license" for more information.

IPython 0.10 -- An enhanced Interactive Python.
? -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help -> Python's own help system.
object? -> Details about 'object'. ?object also works, ?? prints
more.

In [1]: import networkx as nx

In [2]: G=nx.grid_2d_graph(4,4)

In [3]: G=nx.convert_node_labels_to_integers(G,
1,ordering="sorted",discard_old_labels="False")

In [4]: G.nodes()
Out[4]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

In [5]: G.edges()
Out[5]:
[(1, 2),
(1, 5),
(2, 3),
(2, 6),
(3, 4),
(3, 7),
(4, 8),
(5, 6),
(5, 9),
(6, 10),
(6, 7),
(7, 8),
(7, 11),
(8, 12),
(9, 10),
(9, 13),
(10, 11),
(10, 14),
(11, 15),
(11, 12),
(12, 16),
(13, 14),
(14, 15),
(15, 16)]

In [6]: G.edges(data="True")
Out[6]:
[(1, 2, {}),
(1, 5, {}),
(2, 3, {}),
(2, 6, {}),
(3, 4, {}),
(3, 7, {}),
(4, 8, {}),
(5, 6, {}),
(5, 9, {}),
(6, 10, {}),
(6, 7, {}),
(7, 8, {}),
(7, 11, {}),
(8, 12, {}),
(9, 10, {}),
(9, 13, {}),
(10, 11, {}),
(10, 14, {}),
(11, 15, {}),
(11, 12, {}),
(12, 16, {}),
(13, 14, {}),
(14, 15, {}),
(15, 16, {})]

In [7]: for e in G.edges():
...: G[e[0]][e[1]]['weight'] = 1
...:
...:

In [8]: G.edges(data=True)
Out[8]:
[(1, 2, {'weight': 1}),
(1, 5, {'weight': 1}),
(2, 3, {'weight': 1}),
(2, 6, {'weight': 1}),
(3, 4, {'weight': 1}),
(3, 7, {'weight': 1}),
(4, 8, {'weight': 1}),
(5, 6, {'weight': 1}),
(5, 9, {'weight': 1}),
(6, 10, {'weight': 1}),
(6, 7, {'weight': 1}),
(7, 8, {'weight': 1}),
(7, 11, {'weight': 1}),
(8, 12, {'weight': 1}),
(9, 10, {'weight': 1}),
(9, 13, {'weight': 1}),
(10, 11, {'weight': 1}),
(10, 14, {'weight': 1}),
(11, 15, {'weight': 1}),
(11, 12, {'weight': 1}),
(12, 16, {'weight': 1}),
(13, 14, {'weight': 1}),
(14, 15, {'weight': 1}),
(15, 16, {'weight': 1})]


In [15]: M = nx.max_weight_matching(G)

In [16]: M
Out[16]:
{1: 5,
2: 6,
3: 7,
4: 8,
5: 1,
6: 2,
7: 3,
8: 4,
9: 13,
10: 14,
11: 15,
12: 16,
13: 9,
14: 10,
15: 11,
16: 12}

### --- Negating all the edge weights. AIM: to get min-wt-matching.

In [17]: for e in G.edges():
G[e[0]][e[1]]['weight'] = -1
....:
....:

In [18]: G.edges(data=True)
Out[21]:
[(1, 2, {'weight': -1}),
(1, 5, {'weight': -1}),
(2, 3, {'weight': -1}),
(2, 6, {'weight': -1}),
(3, 4, {'weight': -1}),
(3, 7, {'weight': -1}),
(4, 8, {'weight': -1}),
(5, 6, {'weight': -1}),
(5, 9, {'weight': -1}),
(6, 10, {'weight': -1}),
(6, 7, {'weight': -1}),
(7, 8, {'weight': -1}),
(7, 11, {'weight': -1}),
(8, 12, {'weight': -1}),
(9, 10, {'weight': -1}),
(9, 13, {'weight': -1}),
(10, 11, {'weight': -1}),
(10, 14, {'weight': -1}),
(11, 15, {'weight': -1}),
(11, 12, {'weight': -1}),
(12, 16, {'weight': -1}),
(13, 14, {'weight': -1}),
(14, 15, {'weight': -1}),
(15, 16, {'weight': -1})]

In [19]: M1 = nx.max_weight_matching(G)

In [20]: M1
Out[20]: {}

In [21]:
======================================================================

Any suggestions to get min-wt-matching is appreciated.

Thanks,
Sri.

On Nov 7, 6:26 pm, Srinivas <srivathsan.srini...@gmail.com> wrote:

[Dan Schult]

I haven't looked at this routine but many weighted graph algorithms
don't work with negative weights. The standard "trick" is instead of
negating the weights, subtract them from a large number--large enough
to make all weights then positive.

So in your example, you could change the weights from w to 1.5-w.
If the weights vary then w-> max(wlist)+epsilon-w or something like
that.

Dan

[Srinivas]

Hi Dan,
I **think** doing the following will give min-wt matching
(untested):
1) Negate all weights
2) call max_weight_matching with 'maxcardinality=True'.

If someone can affirm that, it will be nice. Your solution of having a
larger wt and
subtracting the current wts is also elegant.

Thanks,
Sri.

[alex]

Srinivas wrote:
> Hi Dan,
> I **think** doing the following will give min-wt matching
> (untested):
> 1) Negate all weights
> 2) call max_weight_matching with 'maxcardinality=True'.
>
> If someone can affirm that, it will be nice. Your solution of having a
> larger wt and
> subtracting the current wts is also elegant.
>
> Thanks,
> Sri.

Maybe this is relevant:
http://healthyalgorithms.wordpress.com/2009/03/23/aco-in-python-minimum-weight-perfect-matchings-aka-matching-algorithms-and-reproductive-health-part-4/

[Srinivas]

Hmmm...interesting. The code is complicated and I had given up long
back. But, this link has given a
fresh hope to proceed without hacking the code. Will give it a shot...

Thanks,
Sri.

On Nov 9, 3:50 pm, alex <argri...@ncsu.edu> wrote:
> Srinivas wrote:
> > Hi Dan,
> >     I **think** doing the following will give min-wt matching
> > (untested):
> > 1) Negate all weights
> > 2) call max_weight_matching with 'maxcardinality=True'.
>
> > If someone can affirm that, it will be nice. Your solution of having a
> > larger wt and
> > subtracting the current wts is also elegant.
>
> > Thanks,
> > Sri.
>

> Maybe this is relevant:http://healthyalgorithms.wordpress.com/2009/03/23/aco-in-python-minim...