[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] Create and Solve Maximal Matching Problem
From: |
Haroldo Santos |
Subject: |
[Help-glpk] Create and Solve Maximal Matching Problem |
Date: |
Wed, 21 Jul 2010 00:22:04 -0300 |
Hi All,
I'm trying to use glpk graph functions to create and solve the maximum
matching problem in bipartite graphs. Function: glp_asnprob_hall.
The example contained in the manual reads the problem from a text
file. I'm trying to create the graph using glpk graph functions and
I'm having some problems.
In my attempt, I've created nodes using glp_add_vertices and added
edges using glp_add_arc. It is not working. GLPK is returning -1 as
the maximum cardinality matching. Is there any other information I
need to fill ???
Here is a small example which I build to inform you of what I'm doing:
G = glp_create_graph(sizeof(v_data), sizeof(e_data));
glp_add_vertices( G, 10 );
glp_add_arc( G, 1, 6 );
glp_add_arc( G, 1, 7 );
glp_add_arc( G, 1, 10 );
glp_add_arc( G, 2, 8 );
glp_add_arc( G, 2, 9 );
glp_add_arc( G, 3, 7 );
glp_add_arc( G, 3, 8 );
glp_add_arc( G, 4, 8 );
glp_add_arc( G, 4, 9 );
glp_add_arc( G, 5, 6 );
glp_add_arc( G, 5, 9 );
int card = glp_asnprob_hall(G, offsetof(v_data, set), offsetof(e_data, x));
printf("CARD %d\n", card);
glp_delete_graph(G);
Thanks in advance,
Haroldo
--
=============================================================
Haroldo Gambini Santos
Computing Department - Universidade Federal de Ouro Preto - UFOP
email: haroldo [at ] iceb.ufop.br
home/research page: http://www.iceb.ufop.br/decom/prof/haroldo/
"Computer science is no more about computers than astronomy
is about telescopes." Edsger Dijkstra
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Help-glpk] Create and Solve Maximal Matching Problem,
Haroldo Santos <=