# 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 |
"" |
bin/connectivity_distribution
| 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.
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).
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent