weighted_blossom_example.cc File Reference

Maximum-weight matching in general graphs (weighted blossom). More...

#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <string>
#include <utility>
#include <Blossom_Weighted.H>
#include <tpl_agraph.H>
#include <tpl_dynArray.H>
#include <tpl_dynSetTree.H>
#include <tpl_graph.H>
#include <tpl_sgraph.H>

Include dependency graph for weighted_blossom_example.cc:

Go to the source code of this file.

Functions
int	main ()
	Runs example scenarios demonstrating maximum-weight matching and writes TikZ visualizations.

Detailed Description

Maximum-weight matching in general graphs (weighted blossom).

Demonstrates:

• Weighted blossom matching on non-bipartite graphs
• Pure maximum-weight objective vs maximum-cardinality mode
• Cross-backend consistency on List/SGraph/Array graph types
• TikZ exports with weighted labels and highlighted matched arcs

Build and run:

cmake -S . -B build cmake –build build –target weighted_blossom_example ./build/Examples/weighted_blossom_example

Generated files (examples):

• /tmp/weighted_blossom_odd_cycle_bridge_max_weight.tex
• /tmp/weighted_blossom_odd_cycle_bridge_max_cardinality.tex
• /tmp/weighted_blossom_tradeoff_max_weight.tex
• /tmp/weighted_blossom_tradeoff_max_cardinality.tex

Definition in file weighted_blossom_example.cc.

Function Documentation

main()

int main

(

)

Runs example scenarios demonstrating maximum-weight matching and writes TikZ visualizations.

Executes two predefined graph scenarios that exercise the weighted blossom algorithm in both pure max-weight and max-cardinality-then-max-weight modes across multiple graph backends, prints per-backend results and warnings on objective mismatches, and emits .tex files visualizing each computed matching.

Returns

int Exit status code; 0 on successful completion.

Definition at line 380 of file weighted_blossom_example.cc.

References Aleph::divide_and_conquer_partition_dp().