[Help-glpk] Create and Solve Maximal Matching Problem

[Haroldo Santos]

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