-
Notifications
You must be signed in to change notification settings - Fork 0
/
enumerate_choices.py
35 lines (21 loc) · 855 Bytes
/
enumerate_choices.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from networkx import DiGraph, contracted_edge, weakly_connected_components, subgraph
def enumerate_disconnected_graph(G: DiGraph) -> int:
sum = 0
for comp in weakly_connected_components(G):
print(subgraph(G, comp))
sum += enumerate_graph(subgraph(G, comp))
return sum
def enumerate_graph(G: DiGraph) -> int:
if G.number_of_edges() == 0:
return 0
edges = [(u, v) for u, v in G.edges]
edge = edges[0]
lhs = enumerate_graph(contracted_edge(G, edge, self_loops=False,
copy=True))
new_graph = DiGraph()
new_graph.add_nodes_from(G.nodes())
new_graph.add_edges_from([e for e in edges if e != edge])
rhs = 0
for comp in weakly_connected_components(G):
rhs += enumerate_graph(subgraph(new_graph, comp))
return lhs + rhs + 1