折腾来折腾去

pikipity的blog

Algorithms: Design and Analysis Part 1 -- Programming Questions (Week4)

这里主要记录下来在 “Algorithms: Design and Analysis Part 1” 的Programming Questions 中的算法、实现和作业中的困难。我是用的是 Python。Week 3 Programming Question 在这里Week 4 Programming Question 的题目可以到这里查看作业用到的数据可以到这里下载

第四周,作业要求找出 “Strongly Connected Components” (SCC) 并计算其内部所含点的数量。如果一幅图上的任意一点都可以经由边与其他所有点相连,这个图就被称为 SCC,可以直观的理解为内部的点形成了回路的图。对于定向图,寻找 SCC 的方法基本可以分为以下几个步骤:

  1. 生成定向图的反向图;
  2. 对生成的反向图中的点进行深度优先搜索,纪录搜索结束的时间,最先搜索完成的点(也就是最底层的点)记为1,其次搜索完成的点(次底层点)记为2,依次类推;
  3. 对原定向图进行深度优先搜索,点的搜索顺序按照刚刚得到的完成顺序由大到小进行,纪录每一个点的上层点 (leader);
  4. 根据每个点的上层点 (leader),倒推得到 SCC。

作业的难点在于深度优先算法在 python 中的实现。由于作业给的图非常大,如果在 python 中使用迭代的方式循环调用同一个函数来实现深度优先搜索,很有可能会导致达到迭代次数上限,所以只能用普通的循环语句来实现。推荐熟悉并使用 “itertools” 这个模组,循环执行某个固定功能的时候非常好用。

Python 代码如下。由于给的图非常大,即使是图的读入过程都可能会很漫长,所以我将整个进度打印在屏幕上,方便监视。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
# -*- coding: utf-8 -*-
import time
from itertools import groupby
from collections import defaultdict

def dfs(input_graph,order,step):
    # Depth-First Search
    leader=dict()
    time=0
    finish_time=dict()
    visited=set()
    track=[]
    N=0
    for node in order:
        N+=1
        if step==1:
            print "%.5f%% -- DFS for reverse graph"%(N/float(len(order))*100)
        else:
            print "%.5f%% -- DFS for graph"%(N/float(len(order))*100)
        if node not in visited:
            current_source=node
            visited.add(node)
            leader[node]=current_source
            track.extend(list(set(input_graph[node])-visited))
            while track:
                p=track[-1]
                visited.add(p)
                leader[p]=current_source
                if not set(input_graph[p])-visited:
                    track.pop()
                    time+=1
                    finish_time[p]=time
                else:
                    track.extend(list(set(input_graph[p])-visited))
            time+=1
            finish_time[node]=time
    return finish_time,leader
 

    
def readgraph(lines):
    # Generate graph
    graph=defaultdict(list)
    N=0
    for line in lines:
        N+=1
        print "%.5f%% -- Read graph"%(N/float(len(lines))*100)
        line=map(int,line.split())
        if line[0]!=line[1]:
            graph[line[0]].append(line[1])
            graph[line[1]]
    return graph
    
def reversegraph(lines):
    # Generate reverse graph
    regraph=defaultdict(list)
    N=0
    for line in lines:
        N+=1
        print "%.5f%% -- Generate reverse graph"%(N/float(len(lines))*100)
        line=map(int,line.split())
        if line[0]!=line[1]:
            regraph[line[1]].append(line[0])
            regraph[line[0]]
    return regraph
    
def leader2SCC(leader_dict):
    # Obtain length of SCC (reverse order) and SCC
    SCC=defaultdict(list)
    for i,k in groupby(leader_dict.keys(),leader_dict.get):
        SCC[i].extend(list(k))
    SCC_len=sorted([len(SCC[x]) for x in SCC.keys()],reverse=True)
    while len(SCC_len)<5:
        SCC_len.append(0)
    return SCC,SCC_len
    

file=["SCC.txt"]
for file_name in file:
    print ""
    # Record time
    t1=time.clock()
    # Read file
    f=open(file_name)
    lines=f.readlines()
    f.close()
    # Generate graph and reverse graph
    graph=readgraph(lines)
    regraph=reversegraph(lines)
    # DFS for reverse graph and count finish time
    finish_time_regraph,leader_regraph=dfs(regraph,sorted(regraph.keys(),reverse=True),1)
    # reorder finish time
    finishtime=[0]*len(finish_time_regraph)
    finishtime=sorted(finish_time_regraph,key=finish_time_regraph.get,reverse=True)
    # DFS for graph based on finish time to get SCC
    finish_time_graph,leader_graph=dfs(graph,finishtime,2)
    SCC,SCC_len=leader2SCC(leader_graph)
    t2=time.clock()
    # print and store result
    print file_name+" result:"
    if len(SCC_len)>5:
        SCC_len=SCC_len[0:5]
    print SCC_len
    print "time: %.3f CPU seconds"%(t2-t1)
    f=open('result.txt','w')
    f.write('''
    "%s" results: %s
    time: %.3f CPU seconds
    '''%(file_name,SCC_len,t2-t1))
    f.close()

答案:434821,968,459,313,211。总用时:730.875 CPU seconds。



Comments