Graph::Bipartite - Graph algorithms on bipartite graphs.
use Graph::Bipartite; $g = Graph::Bipartite->new( 5, 4 ); $g->insert_edge( 3, 5 ); $g->insert_edge( 2, 7 ); %h = $g->maximum_matching();
This algorithm computes the maximum matching of a bipartite unweighted and undirected graph in worst case running time O( sqrt(|V|) * |E| ).
The constructor takes as first argument the number of vertices of the first partition V1, as second argument the number of vertices of the second partition V2. For nodes of the first partition the valid range is [0..|V1|-1], for nodes of the second partition it is [|V1|..|V1|+|V2|-1].
The function maximum_matching() returns a maximum matching as a hash where the keys represents the vertices of V1 and the value of each key an edge to a vertex in V2 being in the matching.
Daniel Etzold, detzold@gmx.de
perl(1).
To install Graph::Bipartite, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Graph::Bipartite
CPAN shell
perl -MCPAN -e shell install Graph::Bipartite
For more information on module installation, please visit the detailed CPAN module installation guide.