Skip to content
Snippets Groups Projects
Select Git revision
  • jk/issue-96
  • devel default
  • master
  • fo
  • jirka/typing
  • fo-base
  • mj/submit-images
  • jk/issue-196
  • honza/add-contestant
  • honza/mr7
  • honza/mrf
  • honza/mrd
  • honza/mra
  • honza/mr6
  • honza/submit-images
  • honza/kolo-vs-soutez
  • jh-stress-test-wip
  • shorten-schools
18 results

export-orgs

Blame
  • 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)