Download the text filehere. (Right click and save link as)
The file contains the adjacency list representation of a simple undirected graph. There are 200 vertices labeled 1 to 200. The first column in the file represents the vertex label, and the particular row (other entries except the first column) tells all
the vertices that the vertex is adjacent to. So for example, the<nobr style="border:0px; padding:0px; margin:0px; max-width:none; max-height:none; vertical-align:0px; line-height:normal; text-decoration:none; white-space:nowrap!important"><span class="math" id="MathJax-Span-1" style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none; width:23px; height:0px; font-size:18px"><span style="display:inline; position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none; top:-41px; left:0px"><span class="mrow" id="MathJax-Span-2" style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none"><span class="msubsup" id="MathJax-Span-3" style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none; width:22.4px; height:0px"><span style="display:inline; position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none; top:-41px; left:0px"><span class="mn" id="MathJax-Span-4" style="font-family:MathJax_Main; display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none">6</span></span><span style="display:inline; position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none; top:-48.3px; left:9px"><span class="texatom" id="MathJax-Span-5" style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none"><span class="mrow" id="MathJax-Span-6" style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none"><span class="mi" id="MathJax-Span-7" style="font-family:MathJax_Math; display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none; font-size:13px; font-style:italic">t</span><span class="mi" id="MathJax-Span-8" style="font-family:MathJax_Math; display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; line-height:normal; text-decoration:none; font-size:13px; font-style:italic">h</span></span></span></span></span></span></span></span></span></span></nobr>row
looks like : "6 155 56 52 120 ......". This just means that the vertex with label 6 is adjacent to (i.e., shares an edge with) the vertices with labels 155,56,52,120,......,etc
Your task is to code up and run the randomized contraction algorithm for the min cut problem and use it on the above graph to compute the min cut. (HINT: Note that you'll have to figure out an implementation of edge contractions. Initially, you might want to
do this naively, creating a new graph from the old every time there's an edge contraction. But you should also think about more efficient implementations.) (WARNING: As per the video lectures, please make sure to run the algorithm many times with different
random seeds, and remember the smallest cut that you ever find.) Write your numeric answer in the space provided. So e.g., if your answer is 5, just type 5 in the space provided.
第三单元课件中的算法python实现代码如下:
import copy
import random
def contraCut(mapD,edgeList):
while len(mapD)>2:
[u,v]=edgeList.pop(random.randrange(0,len(edgeList)-1))
while([v,u] in edgeList):
edgeList.remove([v,u])
while([u,v] in edgeList):
edgeList.remove([u,v])
for ind in range(0,len(edgeList)):
if edgeList[ind][0]==v:edgeList[ind][0]=u
if edgeList[ind][1]==v:edgeList[ind][1]=u
mapD[u]=mapD[u]-{v}
mapD[v]=mapD[v]-{u}
for [x,y] in mapD.items():
if v in y:
mapD[x]=(mapD[x]|{u})-{v}
mapD[u]=mapD[u]|mapD[v]
del mapD[v]
return len(edgeList)/2
if __name__ == '__main__':
f=open('kargerMinCut.txt','r')
mapDict={}
for line in f.readlines():
tmp=[int(x) for x in line.split()]
mapDict[tmp[0]]=set(tmp[1:])
f.close()
edgeList=[]
for [x,y] in mapDict.items():
edgeList.extend([[x,v] for v in y])
numList=[]
for i in range(20):
cpmapDict=copy.deepcopy(mapDict)
cpedgeList=copy.deepcopy(edgeList)
#print cpmapDict
num=contraCut(cpmapDict,cpedgeList)
numList.append(num)
numList.sort()
print num,
i+=1
print numList
读取的txt文件sample如下:
1 3 5
2 4 5
3 1
4 2
5 1 2
每行第一列代表pointer,后面跟的是邻接点。
分享到:
相关推荐
Algorithm-Problem-Solving-with-Algorithms-and-Data-Structures-using-Python.zip,使用python的算法和数据结构解决问题的代码,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
problem-solving-with-algorithms-and-data-structure-using-python 中文版
python-algorithms-mastering-basic-algorithms-in-the-python-language.9781430232377.53502.pdf
python-algorithms-mastering-basic-algorithms-in-the-python-language(英文正版)1
Algorithms for Non-negative Matrix论文描述希望帮助到大家
最大流/最小割算法的简介,理解常用最大流最小割概念的文献,值得学习。 minimum cut/maximum flow algorithms on graphs emerged as an increasingly useful tool for exact or approximate energy minimization in...
Multicore DSP_From Algorithms to Real-time Implementation on the TMS320C66x SoC
A-Comparative-Study-of-Reco-mmendation-Algorithms-in-E-Commerce-Applications
Introduction to algorithms ppt -----from USTC
Neo4j,用户手册,涵盖所有集成的图算法及应用场景,非常适合图算法的学习和应用
Chapter 1 - The Role of Algorithms in Computing Chapter 2 - Getting Started Chapter 3 - Growth of Functions Chapter 4 - Recurrences Chapter 5 - Probabilistic Analysis and Randomized ...
Multicore DSP From Algorithms to Real-time Implementation on the TMS320C66x SoC Naim Dahnoun 2018
Data Structures And Algorithms With Object-oriented Design Patterns In Java.chm
Data Structures and Algorithms with Object-Oriented Design Patterns in C++.rar Data Structures and Algorithms with Object-Oriented Design Patterns in C++.rar
Algorithms for hyper-parameter optimization.pdf,讲述贝叶斯算法的TPE过程的专业论文
Algorithms for Non-negative Matrix Factorization
《Introduction to Algorithms》---MIT教材 本书自第一版出版以来,已经成为世界范围内广泛使用的大学教材和专业人员的标准参考手册。本书全面论述了算法的内容,从一定深度上涵盖了算法的诸多方面,同时其讲授和...
Chapter 1 - The Role of Algorithms in Computing Chapter 2 - Getting Started Chapter 3 - Growth of Functions Chapter 4 - Recurrences Chapter 5 - Probabilistic Analysis and Randomized ...
(eBook)(math) P.Embree - C Algorithms for real-time dsp
Introduction to Algorithms Second Edition - MIT.chm part3