55import random
66from typing import Dict , List , Set , Tuple
77
8-
98# Adjacency list representation of this graph:
109# https://en.wikipedia.org/wiki/File:Single_run_of_Karger%E2%80%99s_Mincut_algorithm.svg
1110TEST_GRAPH = {
12- '1' : ['2' , '3' , '4' , '5' ],
13- '2' : ['1' , '3' , '4' , '5' ],
14- '3' : ['1' , '2' , '4' , '5' , '10' ],
15- '4' : ['1' , '2' , '3' , '5' , '6' ],
16- '5' : ['1' , '2' , '3' , '4' , '7' ],
17- '6' : ['7' , '8' , '9' , '10' , '4' ],
18- '7' : ['6' , '8' , '9' , '10' , '5' ],
19- '8' : ['6' , '7' , '9' , '10' ],
20- '9' : ['6' , '7' , '8' , '10' ],
21- '10' : ['6' , '7' , '8' , '9' , '3' ]
11+ "1" : ["2" , "3" , "4" , "5" ],
12+ "2" : ["1" , "3" , "4" , "5" ],
13+ "3" : ["1" , "2" , "4" , "5" , "10" ],
14+ "4" : ["1" , "2" , "3" , "5" , "6" ],
15+ "5" : ["1" , "2" , "3" , "4" , "7" ],
16+ "6" : ["7" , "8" , "9" , "10" , "4" ],
17+ "7" : ["6" , "8" , "9" , "10" , "5" ],
18+ "8" : ["6" , "7" , "9" , "10" ],
19+ "9" : ["6" , "7" , "8" , "10" ],
20+ "10" : ["6" , "7" , "8" , "9" , "3" ],
2221}
2322
2423
@@ -61,8 +60,9 @@ def partition_graph(graph: Dict[str, List[str]]) -> Set[Tuple[str, str]]:
6160 for neighbor in uv_neighbors :
6261 graph_copy [neighbor ].append (uv )
6362
64- contracted_nodes [uv ] = {contracted_node for contracted_node in
65- contracted_nodes [u ].union (contracted_nodes [v ])}
63+ contracted_nodes [uv ] = {
64+ node for node in contracted_nodes [u ].union (contracted_nodes [v ])
65+ }
6666
6767 # Remove nodes u and v.
6868 del graph_copy [u ]
@@ -75,8 +75,12 @@ def partition_graph(graph: Dict[str, List[str]]) -> Set[Tuple[str, str]]:
7575
7676 # Find cutset.
7777 groups = [contracted_nodes [node ] for node in graph_copy ]
78- return {(node , neighbor ) for node in groups [0 ]
79- for neighbor in graph [node ] if neighbor in groups [1 ]}
78+ return {
79+ (node , neighbor )
80+ for node in groups [0 ]
81+ for neighbor in graph [node ]
82+ if neighbor in groups [1 ]
83+ }
8084
8185
8286if __name__ == "__main__" :
0 commit comments