bipartite_example.C File Reference

Bipartite graphs in Aleph-w (bipartition, tests, matching intuition, and examples). More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <tclap/CmdLine.h>
#include <tpl_graph.H>
#include <tpl_bipartite.H>

Include dependency graph for bipartite_example.C:

Go to the source code of this file.

Typedefs
using	Node = Graph_Node< string >
using	Arc = Graph_Arc< int >
using	Graph = List_Graph< Node, Arc >

Functions
void	print_section (const string &title)
void	print_subsection (const string &title)
void	print_partition (const string &label, DynDlist< Graph::Node * > &nodes)
void	print_matching (Graph &g, DynDlist< Graph::Arc * > &matching)
void	demo_definition ()
void	demo_testing ()
void	demo_matching ()
void	demo_dating ()
void	demo_halls_theorem ()
int	main (int argc, char *argv[])

Detailed Description

Bipartite graphs in Aleph-w (bipartition, tests, matching intuition, and examples).

Overview

This example demonstrates bipartite graphs and common related concepts:

• testing bipartiteness (2-colorability)
• computing a bipartition (left/right sets)
• how bipartite matching relates to max flow (conceptually)
• small themed demos ("dating" example, Hall's theorem illustration)

Data model used by this example

• Graph type: Graph = List_Graph<Graph_Node<string>, Graph_Arc<int>>
• Node info: label (string)
• Arc info: integer value (int) used as a simple tag/weight in examples

Usage / CLI

This example uses TCLAP and a single selector:

• --section / -s <section>: run only one section. Valid values: def, test, match, dating, hall, all (default).
• --help: show help.

If you do not pass -s/--section, the default is all.

# Run all demos
./bipartite_example
 
# Run a specific section
./bipartite_example --section def
./bipartite_example --section test
./bipartite_example --section match
./bipartite_example --section dating
./bipartite_example --section hall
 
# Short form
./bipartite_example -s hall
 
# Show help
./bipartite_example --help

Algorithms and Aleph-w API

• compute_bipartite(g, left, right) computes a bipartition of a connected bipartite graph.
• Bipartiteness testing is equivalent to checking whether the graph is 2-colorable (no odd cycles).

Notes:

• The bipartition computation in tpl_bipartite.H starts from g.get_first_node(); the demo graphs in this file are connected.

Complexity

Let V be the number of vertices and E the number of edges.

• Testing bipartiteness / computing the partition: O(V + E)

(Bipartite maximum matching can be reduced to max flow; see related examples.)

Pitfalls and edge cases

• For disconnected graphs, bipartiteness testing must run a traversal from each unvisited component.
• Traversal/partition order depends on adjacency iteration order.

References / see also

• tpl_bipartite.H (bipartite utilities)
• bfs_dfs_example.C (graph traversal building blocks)
• network_flow_example.C (max flow; matching reduction)

Author

Leandro Rabindranath León

Date

2024

Copyright

GNU General Public License

Definition in file bipartite_example.C.

Typedef Documentation

Arc

using Arc = Graph_Arc<int>

Definition at line 99 of file bipartite_example.C.

Graph

using Graph = List_Graph<Node, Arc>

Definition at line 100 of file bipartite_example.C.

Node

using Node = Graph_Node<string>

Definition at line 98 of file bipartite_example.C.

Function Documentation

demo_dating()

void demo_dating

(

)

Definition at line 381 of file bipartite_example.C.

References Aleph::compute_bipartite(), Aleph::maps(), print_partition(), and print_section().

Referenced by main().

demo_definition()

void demo_definition

(

)

Definition at line 146 of file bipartite_example.C.

References Aleph::compute_bipartite(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), print_partition(), print_section(), and print_subsection().

Referenced by main().

demo_halls_theorem()

void demo_halls_theorem

(

)

Definition at line 430 of file bipartite_example.C.

References Aleph::compute_bipartite(), Aleph::maps(), print_partition(), print_section(), and print_subsection().

Referenced by main().

demo_matching()

void demo_matching

(

)

Definition at line 303 of file bipartite_example.C.

References Aleph::compute_bipartite(), l, Aleph::maps(), print_partition(), print_section(), and print_subsection().

Referenced by main().

demo_testing()

void demo_testing

(

)

Definition at line 206 of file bipartite_example.C.

References Aleph::compute_bipartite(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), print_partition(), print_section(), and print_subsection().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 503 of file bipartite_example.C.

References demo_dating(), demo_definition(), demo_halls_theorem(), demo_matching(), demo_testing(), and Aleph::maps().

print_matching()

void print_matching	(	Graph &	g,
		DynDlist< Graph::Arc * > &	matching
	)

Definition at line 131 of file bipartite_example.C.

References LocateFunctions< Container, Type >::get_it(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::maps(), and Aleph::HTList::size().

print_partition()

void print_partition	(	const string &	label,
		DynDlist< Graph::Node * > &	nodes
	)

Definition at line 118 of file bipartite_example.C.

References Aleph::maps(), and nodes.

Referenced by demo_dating(), demo_definition(), demo_halls_theorem(), demo_matching(), and demo_testing().

print_section()

void print_section

(

const string &

title

)

Definition at line 106 of file bipartite_example.C.

References Aleph::maps().

Referenced by demo_dating(), demo_definition(), demo_halls_theorem(), demo_matching(), and demo_testing().

print_subsection()

void print_subsection

(

const string &

title

)

Definition at line 113 of file bipartite_example.C.

References Aleph::maps().

Referenced by demo_definition(), demo_halls_theorem(), demo_matching(), and demo_testing().