On Fri, 17 Oct 2003, Jon Klingensmith wrote:
Does anyone know where to find an implementation in C of the
Dulmage-Mendelsohn decomposition of a sparse matrix, like the 'dmperm'
command in MATLAB?
This question is fairly off-topic here; a better question would
have been, "Here's some code that is supposed to find a maximal
matching in a bipartite graph; why doesn't it work right?"
Note also that you've really got two questions here: how to perform
DMD, and how to handle sparse matrices in C. Perhaps some people
here have had experience with sparse matrices, but I doubt many
have had occasion to use DMD ::brings foot to neck level in
preparation:: :-)
Several solutions present themselves immediately:
'open dmperm' in Matlab; cut and paste; translate into C.
Use MCC to link your C files with mlfDmperm(); but then
you'll have to struggle with Matlab's defined types instead
of simple arrays and whatnot.
Read Problem 2 in this handout
http://www.cs.mcgill.ca/~fukuda/610A...ssignment2.pdf
and see if you can follow the algorithm given. That's the
best thing I could find in five minutes with Google. Requires
knowledge of some acronyms.
If all else fails, hire yourself a C programmer to write the
code for you.
HTH,
-Arthur