Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

Advanced Algorithms HW 8 (Martin Valgur)

1654 views
Tweet
Share
Share
1
## -*- encoding: utf-8 -*-

2
## This file (HW8.sagetex.sage) was *autogenerated* from HW8.tex with sagetex.sty version 2012/01/16 v2.3.3-69dcb0eb93de.

3
import sagetex

4
_st_ = sagetex.SageTeXProcessor('HW8', version='2012/01/16 v2.3.3-69dcb0eb93de', version_check=True)

5
_st_.blockbegin()

6
try:

7
 def find_sccs(V, E):

8
     V = set(V)

9
     found = set()

10
     finished = dict()

11
     reverse = False

12
 

13
     def dfs(u, t):

14
         found.add(u)

15
         for a, b, w in E:

16
             if reverse:

17
                 a, b = b, a

18
             if a == u and b not in found:

19
                 t = dfs(b, t+1)

20
         finished[u] = t + 1

21
         return finished[u]

22
 

23
     # Calculate the finishing times

24
     t = 0

25
     while len(V) > len(found):

26
         t = dfs((V - found).pop(), t+1)

27
 

28
     # Find the SCCs

29
     sccs = []

30
     reverse = True

31
     found = set()

32
     original_finished = finished.copy()

33
     while len(V) > len(found):

34
         # Find the vertex with the highest finishing time from the set of unvisited vertices

35
         next_u = max((original_finished[u], u) for u in (V - found))[1]

36
         prev_found = found.copy()

37
         dfs(next_u, 0)

38
         sccs.append(found - prev_found)

39
 

40
     sccs = sorted(sccs, key=lambda scc: (-len(scc), max(scc)))

41
     node_to_scc = dict()

42
     for i, scc in enumerate(sccs):

43
         for u in scc:

44
             node_to_scc[u] = i

45
 

46
     scc_edges = [set() for i in range(len(sccs))]

47
     for a, b, w in E:

48
         if node_to_scc[a] != node_to_scc[b]:

49
             scc_edges[node_to_scc[a]].add(node_to_scc[b])

50
 

51
     return sccs, node_to_scc, scc_edges, original_finished

52
except:

53
 _st_.goboom(252)

54
_st_.blockend()

55
_st_.blockbegin()

56
try:

57
 G = DiGraph()

58
 G.add_edges((

59
 ('A', 'D'), ('A', 'C'), ('N', 'A'), ('A', 'G'), ('D', 'B'), ('B', 'K'),

60
 ('K', 'D'), ('C', 'D'), ('C', 'E'), ('E', 'N'), ('N', 'G'), ('E', 'F'),

61
 ('E', 'H'), ('H', 'G'), ('F', 'I'), ('J', 'I'), ('M', 'F'), ('M', 'L'), ('L', 'M')))

62
 E = G.edges()

63
 V = G.vertices()

64
 

65
 sccs, node_to_scc, scc_edges, finish_times = find_sccs(V, E)

66
 # Calculate the topological ordering of the SCC graph

67
 topo_sort = sorted(list(range(1, len(sccs) + 1)), key=lambda i: -finish_times[iter(sccs[i-1]).next()])

68
except:

69
 _st_.goboom(265)

70
_st_.blockend()

71
_st_.blockbegin()

72
try:

73
 H = G.plot(partition = sccs)

74
except:

75
 _st_.goboom(268)

76
_st_.blockend()

77
try:

78
 _st_.plot(0, format='notprovided', _p_=H)

79
except:

80
 _st_.goboom(269)

81
_st_.endofdoc()

82


83