Skip to content

Latest commit

 

History

History
106 lines (78 loc) · 3.64 KB

README.md

File metadata and controls

106 lines (78 loc) · 3.64 KB

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).