Newer
Older
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
"""
Goldberg's exact max flow algorithm.
Parameters
----------
G: undirected, graph (networkx).
Returns
-------
subg: list, subset of nodes corresponding to densest subgraph.
opt: float, density of subg induced subgraph.
"""
import networkx as nx
import copy
def exact_densest(G: nx.Graph):
m = G.number_of_edges()
n = G.number_of_nodes()
low = 0
up = (n - 1) / 2
opt = 0
subg = G.nodes()
if low == up:
return subg, up
# binary search
while up - low > 1 / (n *(n -1)):
guess = (up + low) / 2
H = create_flow_network(G, guess)
solution = nx.minimum_cut(H, 's', 't', capacity='capacity')
cut = solution[1][0]
if cut == {'s'}:
up = guess
else:
low = guess
subg = cut
opt = guess
subg = list(set(subg)&set(G.nodes()))
return subg, opt
def create_flow_network(G, guess):
m = G.number_of_edges()
G = nx.DiGraph(G)
H = G.copy()
H.add_node('s')
H.add_node('t')
for e in G.edges():
H.add_edge(e[0], e[1], capacity=G.edges[e[0], e[1]]['weight'])
for v in G.nodes():
H.add_edge('s', v, capacity=m)
H.add_edge(v, 't', capacity=m + 2 * guess - G.in_degree(v, 'weight'))
return H