attachment:cur_coerce_diagram.sage of days4/projects/arith

   1 def brute_force_rings(args):
   2     """
   3     Just try and create all sorts of rings, with the given arguments as constructors
   4     """
   5     for name, obj in sage.rings.all.__dict__.iteritems():
   6         if obj is farey or obj is ComplexNumber:
   7             continue
   8         for arg in args:
   9             try:
  10                 R = obj(*arg)
  11                 if is_Ring(R):
  12                     yield R
  13             except Exception, e:
  14                 pass
  15                 
  16 def rand_elm(R):
  17     try:
  18         return R.random_element()
  19     except:
  20         try:
  21             return R.random_element(10)
  22         except:
  23             return R.random_element(-10, 10)
  24 
  25 
  26 def coercion_graph(objs):
  27     G = DiGraph()
  28     for obj in objs:
  29         G.add_vertex(obj)
  30     for A in objs:
  31         for B in objs:
  32             try:
  33                 a, b = canonical_coercion(rand_elm(A), rand_elm(B))
  34                 if a.parent() != A:
  35                     G.add_arc(A, a.parent())
  36                 if b.parent() != B:
  37                     G.add_arc(B, b.parent())
  38             except:
  39                 pass
  40     return G
  41 
  42 # The functions below are kind of brute-force, but work for small graphs. 
  43 
  44 def find_longest_path(G, a, b, max_len=None):
  45     if a is b:
  46         return []
  47     elif max_len is None:
  48         max_len = len(G)-1
  49     elif max_len < 1:
  50         return None
  51     all = []
  52     for out in G.outgoing_arc_iterator(a):
  53         s = out[1]
  54         if s is b:
  55             all.append([b])
  56         else:
  57             p = find_longest_path(G, s, b, max_len-1)
  58             if p:
  59                 all.append([s] + p)
  60     if len(all) == 0:
  61         return None
  62     else:
  63         m = max([len(p) for p in all])
  64         for p in all:
  65             if len(p) == m:
  66                 return p
  67                 
  68 # Performs a kind of inverse to transative closure. 
  69                 
  70 def remove_redundant(G):
  71     """
  72     Performs a kind of inverse to transative closure 
  73     on a directed acyclic graph.
  74     """
  75     G = G.copy()
  76     for top in G.vertex_iterator():
  77         if len(G.incoming_arcs([top])) == 0:
  78             dists = {}
  79             for v in G.vertex_iterator():
  80                 p = find_longest_path(G, top, v)
  81                 if p is None:
  82                     dists[v] = -1
  83                 else:
  84                     dists[v] = len(p)
  85             for e in G.arcs():
  86                 if dists[e[1]] - dists[e[0]] > 1 and dists[e[0]] != -1:
  87                     p = find_longest_path(G, e[0], e[1], dists[e[1]] - dists[e[0]])
  88                     if len(p) != 1:
  89                         G.delete_arc(e[0], e[1])
  90     return G
  91     
  92 
  93 def dot(G):
  94     s = "digraph" if G.is_directed() else "graph"
  95     s += ' "%r" {\n'%G
  96     for v in G.vertex_iterator():
  97         s += '  "%r"\n'%v
  98     if G.is_directed():
  99         for e in G.arc_iterator():
 100             s += '  "%r" -> "%r"\n'%(e[0], e[1])
 101     else:
 102         for e in G.edge_iterator():
 103             s += '  "%r" -> "%r"\n'%(e[0], e[1])
 104     s += "}"
 105     return s
 106         
 107 ################
 108 
 109 args = [(), (7,), (7^3,), (7^3, 'a'), (ZZ, 'x')]
 110 print "Constructing rings"
 111 all = set(brute_force_rings(args))
 112 # all.remove(RR) # gets messy
 113 
 114 print len(all), "unique rings"
 115 print "Creating coercion graph..."
 116 G = coercion_graph(all);
 117 G.save("coerce")
 118 G.plot().save("coerce.png")
 119 f = open("coerce.dot", "w")
 120 f.write(dot(G))
 121 f.close()
 122 
 123 print "Simplifying..."
 124 GG = remove_redundant(G)
 125 G.save("coerce_simple")
 126 G.plot().save("coerce_simple.png")
 127 f = open("coerce_simple.dot", "w")
 128 f.write(dot(GG))
 129 f.close()