ls -f

-rw-r--r-- 1 9,3K 2007-01-28 14:37 README
-rw-r--r-- 1 9,1K 2007-01-31 14:37 example.txt
-rwxr-xr-x 1 222K 2007-01-31 14:38 matchfinder
drwxr-xr-x 2  144 2007-01-29 14:40 downloads
-rw-r--r-- 1   50 2007-01-28 20:36 AUTHORS

cat README

Matchfinder is a GPL program to compute a maximal matching of a graph.

A graph or undirected graph G is an ordered pair (V,E), where:

• V is a set of objects, called vertices
• E is a set of unordered pairs of distinct vertices, called edges

A matching of a graph G is a set of pairwise non-adjacent edges of G. A maximal matching for G is a matching of maximum cardinality with respect to G.
Notice that there can be many different maximal matchings for a single graph. For instance, the graph G=( V={1, 2, 3}, E={(1,2), (2,3)} has two maximal matchings: M={(1,2)} and M={(2,3)}.

Matchfinder reads a set of edges from the standard input and returns a maximal matching for such set. The computation is performed using Edmonds's matching algorithm for non-bipartite graphs (see http://www.eecs.berkeley.edu/~karp/greatalgo/lecture05.pdf) and it takes time O(|V|^4). We are still working on the code to improve its readability and to implement optimizations. In particular, we plan to rewrite part of the code and to decrease the time complexity to O(|V|^3).

The development is supported by the Applied Genomics Institute.

cat example.txt

E={(1,2), (1,1), (2,3), (3,4), (5,4), (5,2)}

cat example.txt|./matchfinder

Match = { (1,1), (2,5), (3,4) }

./matchfinder --help

matchfinder 0.0.0alpha

Usage: matchfinder [OPTIONS]...

-h, --help Print help and exit
-V, --version Print version and exit
-o, --outputfile=STRING Ouput file
-i, --inputfile=STRING Input file

ls -goh downloads/

total 640K
-rw-r--r-- 1 264K 2007-01-31 14:22 matchfinder-src-0.0.0alpha.tar.bz2
-rw-r--r-- 1 374K 2007-01-31 14:22 matchfinder-src-0.0.0alpha.tar.gz

cat AUTHORS

Alberto Casagrande <casagrandeappliedgenomics.org>