Select Git revision
-
Petr Baudis authored
Complete basic implementation, compiles but not tested yet.
Petr Baudis authoredComplete basic implementation, compiles but not tested yet.
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)