当前位置:网站首页>Minimum cut edge set of undirected graph
Minimum cut edge set of undirected graph
2022-07-06 20:29:00 【Jose H】
reference
- The minimum cut of an undirected graph
- graph theory : Detailed explanation of maximum flow and minimum cut
codes
- The minimum cut of an undirected graph Code corresponding to the method of solving the global minimum cut in
from random import choice
from copy import deepcopy
import networkx as nx
import matplotlib.pyplot as plt
import sys
sys.setrecursionlimit(5000)
def init_graph():
G = nx.Graph()
edges = []
# with open('example.txt', 'r') as graphInput:
with open('case3.txt', 'r') as graphInput:
# with open('case1.txt', 'r') as graphInput:
for line in graphInput:
ints = [int(x) for x in line.split()]
edges.append(ints)
G.add_edges_from(edges,weight=1)
# nx.draw(G,with_labels=True)
# plt.show()
return G
def merge(G,s,t):
neighbours = dict(G[t]) # Cut this point out
G.remove_node(t)
for i in neighbours:
if(s==i):
pass
elif(G.has_edge(s,i)): # If t So are my neighbors s Neighbors of , Just move the size of this stream to s, Give Way s Responsible for transmission
G[s][i]['weight'] += neighbours[i]['weight']
else: # otherwise
G.add_edge(s,i,weight=neighbours[i]['weight'])
return G
def min_cut(G,s,clo):
"""[summary] Args: G ([type]): [list of edges] s ([int]): [start node index] clo ([type]): [description] Returns: [type]: [description] """
if(len(G)>2):
clo = max(G[s].items(),key=lambda x:x[1]['weight'])[0] # Select a neighbor node according to the weight . Parallel words , Still return to the first
# import ipdb
# ipdb.set_trace()
merge(G,s,clo)
return min_cut(G,s,clo)
else:
return list(dict(G[s]).keys())[0],clo,list(dict(G[s]).values())[0]['weight'] # When there are only two sides left , It returns the starting node and weight of the current cut (1st,3rd Elements ) as well as Cut out point col
def stoer_wagner(G,global_cut,u_v,s):
"""[summary] Args: G ([type]): [list of edges] global_cut ([int]): [max cut number so far] u_v ([list]): [ The minimum cut occurs s and t Node pair ] s ([int]): [start node index] Returns: [type]: [final global_cut and u_v] """
#print("number of points:",len(G))
if(len(G)>2):
clo = 0
u,v,w = min_cut(deepcopy(G),s,clo)
merge(G,u,v)
if(w<global_cut):
global_cut = w
u_v = (u,v)
return stoer_wagner(G,global_cut,u_v,s)
else:
last_cut = list(dict(G[s]).values())[0]['weight']
if(last_cut<global_cut):
global_cut = last_cut
u_v = (s,list(G[s])[0])
return global_cut,u_v
if __name__ == '__main__':
G = init_graph()
s = choice(list(G.nodes())) # randomly choose a vertex
global_cut = 99999
u_v = ('0', '0')
global_cut, u_v = stoer_wagner(G, global_cut, u_v, s)
print("global min cut",global_cut,"\nnodes:", u_v)
This can find the minimum cut edge set s and t What is the node pair and what is the corresponding minimum cutting edge .
And then you can use graph theory : Detailed explanation of maximum flow and minimum cut The last method inside is to find the corresponding edge of the minimum cut
import copy
from collections import deque,defaultdict
from linecache import getline
""" order = dict() def buildNode2Order(): global order pass def Node2Order(): pass """
def hasPath(Gf, s, t, path):
# BFS algorithm
# V = len(Gf)
# visited = list(range(V))
# visited = defaultdict(getFalse)
visited = dict()
# for i in range(V):
# visited[i] = False
for node in Gf.keys():
visited[node]=False
visited[s] = True
queue = deque([s])
while queue:
temp = queue.popleft()
if temp == t:
return True
# print("temp =", temp)
for i in Gf.keys():
if not visited[i] and (Gf[temp].get(i,0) > 0):
queue.append(i)
visited[i] = True
path[i] = temp # record precursor
return visited[t]
def max_flow(capDict, s, t):
maxFlow = 0
Gf = copy.deepcopy(capDict)
print(f"Gf is {
Gf}")
V = len(Gf)
# path = list(range(V))
path = dict()
while hasPath(Gf, s, t, path):
print(f"path is {
path}")
min_flow = float('inf')
# find cf(p)
v = t
while v != s:
u = path[v]
min_flow = min(min_flow, Gf[u][v])
v = path[v]
print(min_flow)
# add flow in every edge of the augument path
v = t
while v != s:
u = path[v]
Gf[u][v] -= min_flow
Gf[v][u] += min_flow
v = path[v]
maxFlow += min_flow
nodes = getNodesSet(Gf,s)
return maxFlow, nodes
# return maxFlow
def getNei(cur,resG):
# V = len(resG)
neighs = []
# for idx in range(V):
for node in resG.keys():
if resG[cur].get(node,0)>0:
neighs.append(node)
return neighs
def dfs(cur,visited,resG):
visited[cur]=True
for nei in getNei(cur,resG):
if not visited[nei]:
dfs(nei,visited,resG)
def getNodesSet(Gf,s):
resG =copy.deepcopy(Gf)
V = len(Gf)
visited=dict()
for node in resG.keys():
visited[node]= False
for cur in getNei(s,resG):
dfs(cur,visited,resG)
nodes=[]
# for node in range(V):
for node in resG.keys():
if visited[node]:
nodes.append(node)
return nodes
def testDictInput():
# read in capDict
from collections import defaultdict
capDict = defaultdict(dict)
with open("case1.txt",'r') as f: # nodes with continuous indice
lines= f.readlines()
for line in lines:
nodes = list(map(int,line.split()))
fromNode,toNode = nodes[0],nodes[1]
capDict[fromNode][toNode] = 1
capDict[toNode][fromNode] = 1
print(f"capDict is {
capDict}")
flow,nodes = max_flow(capDict, 0, 4)
print(f"flow is {
flow}, with nodes of {
nodes}")
# flow = max_flow(capDict, 0, 4)
# print(f"flow is {flow}")
def initFromNX(G,s,t):
from collections import defaultdict
capDict = defaultdict(dict)
return capDict
if __name__ == "__main__":
testDictInput()
边栏推荐
- Notes on beagleboneblack
- Rhcsa Road
- 系统与应用监控的思路和方法
- [Yann Lecun likes the red stone neural network made by minecraft]
- Redisson bug analysis
- Function optimization and arrow function of ES6
- "Penalty kick" games
- [weekly pit] calculate the sum of primes within 100 + [answer] output triangle
- Groovy basic syntax collation
- [network planning] Chapter 3 data link layer (3) channel division medium access control
猜你喜欢
[weekly pit] output triangle
小孩子学什么编程?
棋盘左上角到右下角方案数(2)
Rhcsa Road
Crawler (14) - scrape redis distributed crawler (1) | detailed explanation
Digital triangle model acwing 1018 Minimum toll
【GET-4】
Rhcsa Road
Tencent byte and other big companies interview real questions summary, Netease architects in-depth explanation of Android Development
22-07-05 七牛云存储图片、用户头像上传
随机推荐
[weekly pit] information encryption + [answer] positive integer factorization prime factor
Introduction of Xia Zhigang
JMeter server resource indicator monitoring (CPU, memory, etc.)
Tips for web development: skillfully use ThreadLocal to avoid layer by layer value transmission
Extraction rules and test objectives of performance test points
Rhcsa Road
Review questions of anatomy and physiology · VIII blood system
棋盘左上角到右下角方案数(2)
【每周一坑】计算100以内质数之和 +【解答】输出三角形
Web security - payload
夏志刚介绍
使用.Net驱动Jetson Nano的OLED显示屏
Zoom with unity mouse wheel: zoom the camera closer or farther
【DSP】【第二篇】了解C6678和创建工程
2022 nurse (primary) examination questions and new nurse (primary) examination questions
[network planning] Chapter 3 data link layer (3) channel division medium access control
深度学习分类网络 -- ZFNet
recyclerview gridlayout 平分中间空白区域
RT thread I2C tutorial
Number of schemes from the upper left corner to the lower right corner of the chessboard (2)