Select Git revision
-
Radek Hušek authored
Sage cannot compute Jordan form of larger matrices in reasonable time.
Radek Hušek authoredSage cannot compute Jordan form of larger matrices in reasonable time.
groupConnectivityNaive.py 3.54 KiB
from sage.all import ZZ # to fix bug in sage in following imports
from sage.graphs.graph import Graph, DiGraph
from sage.rings.finite_rings.integer_mod_ring import Integers
def Zkn(k, n):
"""Create group Z_k^n
EXAMPLES:
>>> list(Zkn(4, 1))
[0, 1, 2, 3]
>>> list(Zkn(3,2))
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
>>> list(Zkn(2,3)) # doctest: +NORMALIZE_WHITESPACE
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),
(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]
"""
Zk = Integers(k)
if n == 1:
return Zk
else:
return Zk.cartesian_product( *([Zk] * (n - 1)) )
def prettifyGraph(G_):
"""Convert graph into directed one and number its edges."""
E = [ (u, v, i) for i, (u, v, _) in enumerate(G_.edges()) ]
return DiGraph([G_.vertices(), E], format='vertices_and_edges')
def flowEnumerator(G, group):
"""Enumerate all flows of given graph.
Graph G must be directed and it edges labeled with numbers 0 to |E(G)|.
"""
m = G.num_edges()
assert(G.is_directed())
assert(set(x for _, _, x in G.edges()) == set(range(m)))
def to_elem_vector(cycle):
vec = [ group.zero() ] * m
for (u, v, x) in cycle:
if u > v:
vec[x] = -group.one()
else:
vec[x] = group.one()
return vec
elemVecs = map(to_elem_vector, Graph(G).cycle_basis(output = "edge"))
def combine(vec, i):
if i >= len(elemVecs):
yield vec
return
for e in group:
for v in combine(map(lambda x: x[0] + e * x[1], zip(vec, elemVecs[i])), i + 1):
yield v
for v in combine([group.zero()] * m, 0):
yield tuple(v)
def testGroupConnectivityNaive(G_, group, forb_spanning_tree = True,
list_all = False, counts = False):
E = [ (u, v, i) for i, (u, v, _) in enumerate(G_.edges()) ]
G = DiGraph([G_.vertices(), E], format='vertices_and_edges')
m = G.num_edges()
C = {}
info = { 'graph': G, 'edges': E, 'counts': C }
if counts:
list_all = True
if forb_spanning_tree:
T = G.min_spanning_tree()
else:
T = G.edges()
info['span_tree'] = T
T = [ x for _, _, x in T ]
flows = list(flowEnumerator(G, group))
info['all_flows'] = flows
mask = [group.zero()] * m
for e in T:
mask[e] = None
def is_compatible(f, x):
for i in xrange(m):
if f[i] == x[i]:
return False
return True
flows = [ f for f in flows if is_compatible(f, mask) ]
info['compatible_flows'] = flows
Elems = [ x for x in group ]
forb_ = [ group.zero() ] * m
def forb_iter(e):
if e >= len(T):
yield tuple(forb_)
return
for v in Elems:
forb_[T[e]] = v
for r in forb_iter(e + 1):
yield r
if not counts:
def find_flow(forb):
for f in flows:
if is_compatible(f, forb):
return True
return False
else:
def find_flow(forb):
C[forb] = filter(lambda f: is_compatible(f, forb), flows)
return (len(C[forb]) > 0)
ret = []
for forb in forb_iter(0):
if not find_flow(forb):
if not list_all:
return (False, info, [forb])
ret.append(forb)
return (len(ret) == 0, info, ret)
def labelsFromArray(G, E, labels):
for (u, v, i) in E:
G.set_edge_label(u, v, labels[i])
def dictMap(f, d):
return { k: f(v) for k, v in d.iteritems() }
def myHistogram(data):
s = dict()
for i in data:
if i not in s:
s[i] = 0
s[i] += 1
return s
if __name__ == "__main__":
import doctest
(f, t) = doctest.testmod()
print "%s: %i tests of %i failed." % (__file__, f, t)
if f > 0:
from sys import exit
exit(1)