[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);


Thanks in advance,


Haroldo Gambini Santos
Computing Department - Universidade Federal de Ouro Preto - UFOP
email: haroldo [at ]
home/research page:

"Computer science is no more about computers than astronomy
is about telescopes." Edsger Dijkstra

reply via email to

[Prev in Thread] Current Thread [Next in Thread]