./waf configure
./waf
# 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 | 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 |
| 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 | "" |
| Options | Type | Default | |
|---|---|---|---|
| -cut_tree_input_path | input cut tree path | string | "" |
| -cut_tree_output_path | output connectivity distribution path | string | "" |
| Options | Type | Default | |
|---|---|---|---|
| -cut_tree_path | input cut tree path | string | "" |
| -query_path | input query path | string | "" |
| -output_path | output connectivity path | string | "" |
| Options | Type | Default | |
|---|---|---|---|
| -cut_tree_path | input cut tree path | string | "" |
| -query_path | input query path | string | "" |
| -output_path | output partition path | string | "" |
- 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.
0 1
0 2
0 3
1 2
1 3
2 3
Execute bin/test to run tests.
This software is released under the MIT License, see LICENSE.txt.
- Takuya Akiba, Yoichi Iwata, Yosuke Sameshima, Naoto Mizuno, Yosuke Yano, "Cut Tree Construction from Massive Graphs", ICDM'16 (to appear).