tpl_bipartite.H File Reference

Bipartite graph detection and 2-coloring. More...

#include <tpl_dynDlist.H>
#include <tpl_dynMapTree.H>
#include <tpl_dynListQueue.H>
#include <tpl_net.H>
#include <ah-errors.H>
#include <cookie_guard.H>
#include <limits>

Include dependency graph for tpl_bipartite.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Compute_Bipartite< GT, SA >
	Class that takes a bipartite graph and computes the partition sets. More...
class	Aleph::Compute_Maximum_Cardinality_Bipartite_Matching< GT, Max_Flow, SA >
	Class for computing the maximum cardinality matching of a bipartite graph. More...
class	Aleph::Hopcroft_Karp_Matching< GT, SA >
	Functor wrapper for hopcroft_karp_matching. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Enumerations
enum	Aleph::Bipartite_Color { Aleph::Bp_White , Aleph::Bp_Red , Aleph::Bp_Blue }

Functions
template<class GT >
static long &	Aleph::color (typename GT::Node *p)
template<class GT >
static long &	Aleph::color (typename GT::Arc *a)
template<class GT , class SA = Dft_Show_Arc<GT>>
void	Aleph::compute_bipartite (const GT &g, DynDlist< typename GT::Node * > &l, DynDlist< typename GT::Node * > &r)
	Computes the partition sets of a bipartite graph.
template<class GT , template< class > class Max_Flow = Ford_Fulkerson_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
void	Aleph::compute_maximum_cardinality_bipartite_matching (const GT &g, DynDlist< typename GT::Arc * > &matching)
	Computes the maximum cardinality matching of a bipartite graph.
template<class GT , class SA = Dft_Show_Arc<GT>>
bool	Aleph::compute_bipartite_all_components (const GT &g, DynDlist< typename GT::Node * > &l, DynDlist< typename GT::Node * > &r)
	Computes the partition sets of a bipartite graph handling all connected components.
template<class GT , class SA >
static bool	Aleph::hopcroft_karp_dfs (const GT &g, typename GT::Node *u)
template<class GT , class SA = Dft_Show_Arc<GT>>
void	Aleph::hopcroft_karp_matching (const GT &g, DynDlist< typename GT::Arc * > &matching)
	Computes a maximum cardinality matching on a bipartite graph using the Hopcroft-Karp algorithm.

Detailed Description

Bipartite graph detection and 2-coloring.

Tests if a graph is bipartite (can be 2-colored) and computes the bipartition if it exists.

Features

• Test bipartiteness via BFS
• Compute vertex 2-coloring
• Detect odd cycles (non-bipartite proof)

Complexity: O(V + E)

Author

Leandro Rabindranath León

Definition in file tpl_bipartite.H.