Min-Cut Tree Algorithms

Building

./waf configure
./waf

Running

# generate cut-tree
bin/gomory_hu -graph /data/graph_edges.tsv -cut_tree_output_path=cut_tree.tree
# query test : output execution time
bin/gomory_hu_tree_query -cut_tree_path=cut_tree.tree
# calculate connectivity distribution
bin/connectivity_distribution -cut_tree_input_path=cut_tree.tree -cut_tree_output_path=connectivity.txt
# connectivity query
bin/query_connectivity -cut_tree_path=cut_tree.tree -query_path=query.txt -output_path=output.txt
# partition query
bin/query_cutset -cut_tree_path=cut_tree.tree -query_path=query.txt -output_path=output.txt

Options

bin/gomory_hu

Options		Type	Default
-type	Graph file type (auto, tsv, gen)	string	"auto"
-graph	Input graph	string	"-"
-cut_tree_builder	cut_tree_with_2ecc, PlainGusfield,PlainGusfield_bi_dinitz	string	"cut_tree_with_2ecc"
-cut_tree_output_path	output cut tree path	string	""
-cut_tree_contraction_lower_bound	contraction upper bound	int32	2
-cut_tree_enable_goal_oriented_search	enable_goal_oriented_search	bool	true
-cut_tree_enable_greedy_tree_packing	enable_greedy_tree_packing	bool	true
-cut_tree_separate_near_pairs_d	separate near pairs radius	int32	1
-cut_tree_try_greedy_tree_packing	number of tree packing	int32	1
-cut_tree_try_large_degreepairs	number of tree packing	int32	10
-cut_tree_gtp_dfs_edge_max	number of tree packing	int32	1000000000

bin/gomory_hu_tree_query

Options		Type	Default
-cut_tree_node_pair_random_seed	output gomory_hu tree path	int64	922337203685477583
-cut_tree_num_query	number of queries	int32	10000000
-cut_tree_path	input cut tree path	string	""

bin/connectivity_distribution

Options		Type	Default
-cut_tree_input_path	input cut tree path	string	""
-cut_tree_output_path	output connectivity distribution path	string	""

bin/query_connectivity

Options		Type	Default
-cut_tree_path	input cut tree path	string	""
-query_path	input query path	string	""
-output_path	output connectivity path	string	""

bin/query_cutset

Options		Type	Default
-cut_tree_path	input cut tree path	string	""
-query_path	input query path	string	""
-output_path	output partition path	string	""

Supported Formats

TSV files

• By using the option -type=tsv, you can specify .tsv file as the graph file with the option -graph=....
• In a .tsv file, each line should contain two integers describing an edge (see below).
• Vertices should be described by integers starting from zero.

TSV file example

0 1
0 2
0 3
1 2
1 3
2 3

Unit Test

Execute bin/test to run tests.

LICENSE

This software is released under the MIT License, see LICENSE.txt.

References

• Takuya Akiba, Yoichi Iwata, Yosuke Sameshima, Naoto Mizuno, Yosuke Yano, "Cut Tree Construction from Massive Graphs", ICDM'16 (to appear).