Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Is there a functional way to manipulate cycles extracted from a digraph?

I wrote a worksheet that defines a digraph and extracts all of its simple cycles.

pr = prime_range(3600)
wief = DiGraph([pr, lambda p, q: power_mod(p, q - 1, q^2) == 1]) # could take a while!
sc = wief.all_simple_cycles()
sc.append([0, 0])

Then it uses mostly procedural code to:

  1. Remove the duplicate endpoints
  2. Reverse-sort the cycle
  3. Group cycles by length
  4. Sort the group of cycles
  5. Return the first (lexicographically earliest) cycle of each length

maxn = 0
for c in sc:
    del c[0] # duplicate
    maxn = max(maxn, len(c))
    c.sort(reverse=True) # reverse lexicographic
# group by length
tbl = [[c for c in sc if len(c) == n] for n in range(1,maxn)]
n = 1
for t in tbl: # sort tuples by max element, get smallest tuple
    print 'n=%d:'%(n),
    # why can't join handle a list of integers?
    print ', '.join(map(lambda m: '%s'%(m), t[0]))
    n = n + 1

The worksheet is adequate - it performs step 5 correctly, but a listing of the code will be posted as the PROG paragraph of an OEIS entry. So I would really like to reduce the numbered steps to as few lines as possible. Are there more graceful ways to tweak the output of one function before passing it on to another?