HW8.sagetex.py

## -*- encoding: utf-8 -*-
# This file was *autogenerated* from the file HW8.sagetex.sage.
from sage.all_cmdline import *   # import sage library
_sage_const_269 = Integer(269); _sage_const_268 = Integer(268); _sage_const_1 = Integer(1); _sage_const_0 = Integer(0); _sage_const_265 = Integer(265); _sage_const_252 = Integer(252)## This file (HW8.sagetex.sage) was *autogenerated* from HW8.tex with sagetex.sty version 2012/01/16 v2.3.3-69dcb0eb93de.
import sagetex
_st_ = sagetex.SageTeXProcessor('HW8', version='2012/01/16 v2.3.3-69dcb0eb93de', version_check=True)
_st_.blockbegin()
try:
 def find_sccs(V, E):
     V = set(V)
     found = set()
     finished = dict()
     reverse = False
 
     def dfs(u, t):
         found.add(u)
         for a, b, w in E:
             if reverse:
                 a, b = b, a
             if a == u and b not in found:
                 t = dfs(b, t+_sage_const_1 )
         finished[u] = t + _sage_const_1 
         return finished[u]
 
     # Calculate the finishing times
     t = _sage_const_0 
     while len(V) > len(found):
         t = dfs((V - found).pop(), t+_sage_const_1 )
 
     # Find the SCCs
     sccs = []
     reverse = True
     found = set()
     original_finished = finished.copy()
     while len(V) > len(found):
         # Find the vertex with the highest finishing time from the set of unvisited vertices
         next_u = max((original_finished[u], u) for u in (V - found))[_sage_const_1 ]
         prev_found = found.copy()
         dfs(next_u, _sage_const_0 )
         sccs.append(found - prev_found)
 
     sccs = sorted(sccs, key=lambda scc: (-len(scc), max(scc)))
     node_to_scc = dict()
     for i, scc in enumerate(sccs):
         for u in scc:
             node_to_scc[u] = i
 
     scc_edges = [set() for i in range(len(sccs))]
     for a, b, w in E:
         if node_to_scc[a] != node_to_scc[b]:
             scc_edges[node_to_scc[a]].add(node_to_scc[b])
 
     return sccs, node_to_scc, scc_edges, original_finished
except:
 _st_.goboom(_sage_const_252 )
_st_.blockend()
_st_.blockbegin()
try:
 G = DiGraph()
 G.add_edges((
 ('A', 'D'), ('A', 'C'), ('N', 'A'), ('A', 'G'), ('D', 'B'), ('B', 'K'),
 ('K', 'D'), ('C', 'D'), ('C', 'E'), ('E', 'N'), ('N', 'G'), ('E', 'F'),
 ('E', 'H'), ('H', 'G'), ('F', 'I'), ('J', 'I'), ('M', 'F'), ('M', 'L'), ('L', 'M')))
 E = G.edges()
 V = G.vertices()
 
 sccs, node_to_scc, scc_edges, finish_times = find_sccs(V, E)
 # Calculate the topological ordering of the SCC graph
 topo_sort = sorted(list(range(_sage_const_1 , len(sccs) + _sage_const_1 )), key=lambda i: -finish_times[iter(sccs[i-_sage_const_1 ]).next()])
except:
 _st_.goboom(_sage_const_265 )
_st_.blockend()
_st_.blockbegin()
try:
 H = G.plot(partition = sccs)
except:
 _st_.goboom(_sage_const_268 )
_st_.blockend()
try:
 _st_.plot(_sage_const_0 , format='notprovided', _p_=H)
except:
 _st_.goboom(_sage_const_269 )
_st_.endofdoc()