spiffyscore

Hex Artifact Content
Login

Artifact 810c677434b740c46117e9e014c142feca1c5118:


0000: 23 20 74 6f 70 73 6f 72 74 20 2d 20 64 65 70 65  # topsort - depe
0010: 6e 64 65 6e 63 79 20 28 74 6f 70 6f 6c 6f 67 69  ndency (topologi
0020: 63 61 6c 29 20 73 6f 72 74 69 6e 67 20 61 6e 64  cal) sorting and
0030: 20 63 79 63 6c 65 20 66 69 6e 64 69 6e 67 20 66   cycle finding f
0040: 75 6e 63 74 69 6f 6e 73 0a 23 20 43 6f 70 79 72  unctions.# Copyr
0050: 69 67 68 74 20 28 43 29 20 32 30 30 37 20 52 41  ight (C) 2007 RA
0060: 44 4c 6f 67 69 63 0a 23 20 0a 23 20 54 68 69 73  DLogic.# .# This
0070: 20 6c 69 62 72 61 72 79 20 69 73 20 66 72 65 65   library is free
0080: 20 73 6f 66 74 77 61 72 65 3b 20 79 6f 75 20 63   software; you c
0090: 61 6e 20 72 65 64 69 73 74 72 69 62 75 74 65 20  an redistribute 
00a0: 69 74 20 61 6e 64 2f 6f 72 0a 23 20 6d 6f 64 69  it and/or.# modi
00b0: 66 79 20 69 74 20 75 6e 64 65 72 20 74 68 65 20  fy it under the 
00c0: 74 65 72 6d 73 20 6f 66 20 74 68 65 20 47 4e 55  terms of the GNU
00d0: 20 4c 65 73 73 65 72 20 47 65 6e 65 72 61 6c 20   Lesser General 
00e0: 50 75 62 6c 69 63 0a 23 20 4c 69 63 65 6e 73 65  Public.# License
00f0: 20 61 73 20 70 75 62 6c 69 73 68 65 64 20 62 79   as published by
0100: 20 74 68 65 20 46 72 65 65 20 53 6f 66 74 77 61   the Free Softwa
0110: 72 65 20 46 6f 75 6e 64 61 74 69 6f 6e 3b 20 0a  re Foundation; .
0120: 23 20 76 65 72 73 69 6f 6e 20 32 2e 31 20 6f 66  # version 2.1 of
0130: 20 74 68 65 20 4c 69 63 65 6e 73 65 2e 0a 23 20   the License..# 
0140: 0a 23 20 54 68 69 73 20 6c 69 62 72 61 72 79 20  .# This library 
0150: 69 73 20 64 69 73 74 72 69 62 75 74 65 64 20 69  is distributed i
0160: 6e 20 74 68 65 20 68 6f 70 65 20 74 68 61 74 20  n the hope that 
0170: 69 74 20 77 69 6c 6c 20 62 65 20 75 73 65 66 75  it will be usefu
0180: 6c 2c 0a 23 20 62 75 74 20 57 49 54 48 4f 55 54  l,.# but WITHOUT
0190: 20 41 4e 59 20 57 41 52 52 41 4e 54 59 3b 20 77   ANY WARRANTY; w
01a0: 69 74 68 6f 75 74 20 65 76 65 6e 20 74 68 65 20  ithout even the 
01b0: 69 6d 70 6c 69 65 64 20 77 61 72 72 61 6e 74 79  implied warranty
01c0: 20 6f 66 0a 23 20 4d 45 52 43 48 41 4e 54 41 42   of.# MERCHANTAB
01d0: 49 4c 49 54 59 20 6f 72 20 46 49 54 4e 45 53 53  ILITY or FITNESS
01e0: 20 46 4f 52 20 41 20 50 41 52 54 49 43 55 4c 41   FOR A PARTICULA
01f0: 52 20 50 55 52 50 4f 53 45 2e 20 53 65 65 20 74  R PURPOSE. See t
0200: 68 65 20 47 4e 55 0a 23 20 4c 65 73 73 65 72 20  he GNU.# Lesser 
0210: 47 65 6e 65 72 61 6c 20 50 75 62 6c 69 63 20 4c  General Public L
0220: 69 63 65 6e 73 65 20 66 6f 72 20 6d 6f 72 65 20  icense for more 
0230: 64 65 74 61 69 6c 73 2e 0a 23 0a 23 20 53 65 65  details..#.# See
0240: 20 68 74 74 70 3a 2f 2f 77 77 77 2e 66 73 66 2e   http://www.fsf.
0250: 6f 72 67 2f 6c 69 63 65 6e 73 69 6e 67 2f 6c 69  org/licensing/li
0260: 63 65 6e 73 65 73 2f 6c 67 70 6c 2e 74 78 74 20  censes/lgpl.txt 
0270: 66 6f 72 20 66 75 6c 6c 20 6c 69 63 65 6e 73 65  for full license
0280: 20 74 65 78 74 2e 0a 22 22 22 50 72 6f 76 69 64   text.."""Provid
0290: 65 20 74 6f 70 6c 6f 67 69 63 61 6c 20 73 6f 72  e toplogical sor
02a0: 74 69 6e 67 20 28 69 2e 65 2e 20 64 65 70 65 6e  ting (i.e. depen
02b0: 64 65 6e 63 79 20 73 6f 72 74 69 6e 67 29 20 66  dency sorting) f
02c0: 75 6e 63 74 69 6f 6e 73 2e 0a 0a 54 68 65 20 74  unctions...The t
02d0: 6f 70 73 6f 72 74 20 66 75 6e 63 74 69 6f 6e 20  opsort function 
02e0: 69 73 20 62 61 73 65 64 20 6f 6e 20 63 6f 64 65  is based on code
02f0: 20 70 6f 73 74 65 64 20 6f 6e 20 55 73 65 6e 65   posted on Usene
0300: 74 20 62 79 20 54 69 6d 20 50 65 74 65 72 73 2e  t by Tim Peters.
0310: 0a 0a 4d 6f 64 69 66 69 63 61 74 69 6f 6e 73 3a  ..Modifications:
0320: 0a 2d 20 61 64 64 65 64 20 64 6f 63 74 65 73 74  .- added doctest
0330: 73 0a 2d 20 63 68 61 6e 67 65 64 20 73 6f 6d 65  s.- changed some
0340: 20 62 69 74 73 20 74 6f 20 75 73 65 20 63 75 72   bits to use cur
0350: 72 65 6e 74 20 50 79 74 68 6f 6e 20 69 64 69 6f  rent Python idio
0360: 6d 73 0a 20 20 28 6c 69 73 74 63 6f 6d 70 20 69  ms.  (listcomp i
0370: 6e 73 74 65 61 64 20 6f 66 20 66 69 6c 74 65 72  nstead of filter
0380: 2c 20 2b 3d 2f 2d 3d 2c 20 69 6e 68 65 72 69 74  , +=/-=, inherit
0390: 20 66 72 6f 6d 20 45 78 63 65 70 74 69 6f 6e 29   from Exception)
03a0: 0a 2d 20 61 64 64 65 64 20 61 20 74 6f 70 73 6f  .- added a topso
03b0: 72 74 5f 6c 65 76 65 6c 73 20 76 65 72 73 69 6f  rt_levels versio
03c0: 6e 20 74 68 61 74 20 70 6f 72 74 73 20 69 74 65  n that ports ite
03d0: 6d 73 20 69 6e 20 65 61 63 68 20 64 65 70 65 6e  ms in each depen
03e0: 64 65 6e 63 79 20 6c 65 76 65 6c 0a 20 20 69 6e  dency level.  in
03f0: 74 6f 20 61 20 73 75 62 2d 6c 69 73 74 0a 2d 20  to a sub-list.- 
0400: 61 64 64 65 64 20 66 69 6e 64 5f 63 79 63 6c 65  added find_cycle
0410: 73 20 74 6f 20 61 69 64 20 69 6e 20 63 79 63 6c  s to aid in cycl
0420: 65 20 64 65 62 75 67 67 69 6e 67 0a 0a 52 75 6e  e debugging..Run
0430: 20 74 68 69 73 20 6d 6f 64 75 6c 65 20 64 69 72   this module dir
0440: 65 63 74 6c 79 20 74 6f 20 72 75 6e 20 74 68 65  ectly to run the
0450: 20 64 6f 63 74 65 73 74 73 20 28 75 6e 69 74 74   doctests (unitt
0460: 65 73 74 73 29 2e 0a 4d 61 6b 65 20 73 75 72 65  ests)..Make sure
0470: 20 74 68 65 79 20 61 6c 6c 20 70 61 73 73 20 62   they all pass b
0480: 65 66 6f 72 65 20 63 68 65 63 6b 69 6e 67 20 69  efore checking i
0490: 6e 20 61 6e 79 20 6d 6f 64 69 66 69 63 61 74 69  n any modificati
04a0: 6f 6e 73 2e 0a 0a 52 65 71 75 69 72 65 73 20 50  ons...Requires P
04b0: 79 74 68 6f 6e 20 3e 3d 20 32 2e 32 0a 28 46 6f  ython >= 2.2.(Fo
04c0: 72 20 50 79 74 68 6f 6e 20 32 2e 32 20 61 6c 73  r Python 2.2 als
04d0: 6f 20 72 65 71 75 69 72 65 73 20 73 65 70 61 72  o requires separ
04e0: 61 74 65 20 73 65 74 73 2e 70 79 20 6d 6f 64 75  ate sets.py modu
04f0: 6c 65 29 0a 0a 54 68 69 73 20 72 65 71 75 69 72  le)..This requir
0500: 65 73 20 74 68 65 20 72 61 64 5f 75 74 69 6c 2e  es the rad_util.
0510: 70 79 20 6d 6f 64 75 6c 65 2e 0a 0a 22 22 22 0a  py module...""".
0520: 0a 23 20 50 72 6f 76 69 64 65 20 73 75 70 70 6f  .# Provide suppo
0530: 72 74 20 66 6f 72 20 50 79 74 68 6f 6e 20 32 2e  rt for Python 2.
0540: 32 2a 0a 66 72 6f 6d 20 5f 5f 66 75 74 75 72 65  2*.from __future
0550: 5f 5f 20 69 6d 70 6f 72 74 20 67 65 6e 65 72 61  __ import genera
0560: 74 6f 72 73 0a 0a 5f 5f 76 65 72 73 69 6f 6e 5f  tors..__version_
0570: 5f 20 3d 20 27 24 52 65 76 69 73 69 6f 6e 3a 20  _ = '$Revision: 
0580: 30 2e 39 20 24 27 0a 5f 5f 64 61 74 65 5f 5f 20  0.9 $'.__date__ 
0590: 3d 20 27 24 44 61 74 65 3a 20 32 30 30 37 2f 30  = '$Date: 2007/0
05a0: 33 2f 32 37 20 30 34 3a 31 35 3a 32 36 20 24 27  3/27 04:15:26 $'
05b0: 0a 5f 5f 63 72 65 64 69 74 73 5f 5f 20 3d 20 27  .__credits__ = '
05c0: 27 27 54 69 6d 20 50 65 74 65 72 73 20 2d 2d 20  ''Tim Peters -- 
05d0: 6f 72 69 67 69 6e 61 6c 20 74 6f 70 73 6f 72 74  original topsort
05e0: 20 63 6f 64 65 0a 54 69 6d 20 57 65 67 65 6e 65   code.Tim Wegene
05f0: 72 20 2d 2d 20 64 6f 63 74 65 73 74 69 6e 67 2c  r -- doctesting,
0600: 20 75 70 64 61 74 69 6e 67 20 74 6f 20 63 75 72   updating to cur
0610: 72 65 6e 74 20 69 64 69 6f 6d 73 2c 20 74 6f 70  rent idioms, top
0620: 73 6f 72 74 5f 6c 65 76 65 6c 73 2c 0a 20 20 20  sort_levels,.   
0630: 20 20 20 20 20 20 20 20 20 20 20 20 66 69 6e 64              find
0640: 5f 63 79 63 6c 65 73 0a 27 27 27 0a 0a 23 20 4d  _cycles.'''..# M
0650: 61 6b 65 20 50 79 74 68 6f 6e 20 32 2e 33 20 73  ake Python 2.3 s
0660: 65 74 73 20 6c 6f 6f 6b 20 6c 69 6b 65 20 50 79  ets look like Py
0670: 74 68 6f 6e 20 32 2e 34 20 73 65 74 73 2e 0a 74  thon 2.4 sets..t
0680: 72 79 3a 0a 20 20 20 20 73 65 74 0a 65 78 63 65  ry:.    set.exce
0690: 70 74 20 4e 61 6d 65 45 72 72 6f 72 3a 0a 20 20  pt NameError:.  
06a0: 20 20 66 72 6f 6d 20 73 65 74 73 20 69 6d 70 6f    from sets impo
06b0: 72 74 20 53 65 74 20 61 73 20 73 65 74 0a 0a 66  rt Set as set..f
06c0: 72 6f 6d 20 72 61 64 5f 75 74 69 6c 20 69 6d 70  rom rad_util imp
06d0: 6f 72 74 20 69 73 5f 72 6f 74 61 74 65 64 0a 0a  ort is_rotated..
06e0: 0a 63 6c 61 73 73 20 43 79 63 6c 65 45 72 72 6f  .class CycleErro
06f0: 72 28 45 78 63 65 70 74 69 6f 6e 29 3a 0a 20 20  r(Exception):.  
0700: 20 20 22 22 22 43 79 63 6c 65 20 45 72 72 6f 72    """Cycle Error
0710: 22 22 22 0a 20 20 20 20 70 61 73 73 0a 0a 0a 64  """.    pass...d
0720: 65 66 20 74 6f 70 73 6f 72 74 28 70 61 69 72 6c  ef topsort(pairl
0730: 69 73 74 29 3a 0a 20 20 20 20 22 22 22 54 6f 70  ist):.    """Top
0740: 6f 6c 6f 67 69 63 61 6c 6c 79 20 73 6f 72 74 20  ologically sort 
0750: 61 20 6c 69 73 74 20 6f 66 20 28 70 61 72 65 6e  a list of (paren
0760: 74 2c 20 63 68 69 6c 64 29 20 70 61 69 72 73 2e  t, child) pairs.
0770: 0a 0a 20 20 20 20 52 65 74 75 72 6e 20 61 20 6c  ..    Return a l
0780: 69 73 74 20 6f 66 20 74 68 65 20 65 6c 65 6d 65  ist of the eleme
0790: 6e 74 73 20 69 6e 20 64 65 70 65 6e 64 65 6e 63  nts in dependenc
07a0: 79 20 6f 72 64 65 72 20 28 70 61 72 65 6e 74 20  y order (parent 
07b0: 74 6f 20 63 68 69 6c 64 20 6f 72 64 65 72 29 2e  to child order).
07c0: 0a 0a 20 20 20 20 3e 3e 3e 20 70 72 69 6e 74 20  ..    >>> print 
07d0: 74 6f 70 73 6f 72 74 28 20 5b 28 31 2c 32 29 2c  topsort( [(1,2),
07e0: 20 28 33 2c 34 29 2c 20 28 35 2c 36 29 2c 20 28   (3,4), (5,6), (
07f0: 31 2c 33 29 2c 20 28 31 2c 35 29 2c 20 28 31 2c  1,3), (1,5), (1,
0800: 36 29 2c 20 28 32 2c 35 29 5d 20 29 20 0a 20 20  6), (2,5)] ) .  
0810: 20 20 5b 31 2c 20 32 2c 20 33 2c 20 35 2c 20 34    [1, 2, 3, 5, 4
0820: 2c 20 36 5d 0a 0a 20 20 20 20 3e 3e 3e 20 70 72  , 6]..    >>> pr
0830: 69 6e 74 20 74 6f 70 73 6f 72 74 28 20 5b 28 31  int topsort( [(1
0840: 2c 32 29 2c 20 28 31 2c 33 29 2c 20 28 32 2c 34  ,2), (1,3), (2,4
0850: 29 2c 20 28 33 2c 34 29 2c 20 28 35 2c 36 29 2c  ), (3,4), (5,6),
0860: 20 28 34 2c 35 29 5d 20 29 0a 20 20 20 20 5b 31   (4,5)] ).    [1
0870: 2c 20 32 2c 20 33 2c 20 34 2c 20 35 2c 20 36 5d  , 2, 3, 4, 5, 6]
0880: 0a 0a 20 20 20 20 3e 3e 3e 20 70 72 69 6e 74 20  ..    >>> print 
0890: 74 6f 70 73 6f 72 74 28 20 5b 28 31 2c 32 29 2c  topsort( [(1,2),
08a0: 20 28 32 2c 33 29 2c 20 28 33 2c 32 29 5d 20 29   (2,3), (3,2)] )
08b0: 0a 20 20 20 20 54 72 61 63 65 62 61 63 6b 20 28  .    Traceback (
08c0: 6d 6f 73 74 20 72 65 63 65 6e 74 20 63 61 6c 6c  most recent call
08d0: 20 6c 61 73 74 29 3a 0a 20 20 20 20 43 79 63 6c   last):.    Cycl
08e0: 65 45 72 72 6f 72 3a 20 28 5b 31 5d 2c 20 7b 32  eError: ([1], {2
08f0: 3a 20 31 2c 20 33 3a 20 31 7d 2c 20 7b 32 3a 20  : 1, 3: 1}, {2: 
0900: 5b 33 5d 2c 20 33 3a 20 5b 32 5d 7d 29 0a 20 20  [3], 3: [2]}).  
0910: 20 20 0a 20 20 20 20 22 22 22 0a 20 20 20 20 6e    .    """.    n
0920: 75 6d 5f 70 61 72 65 6e 74 73 20 3d 20 7b 7d 20  um_parents = {} 
0930: 20 23 20 65 6c 65 6d 65 6e 74 20 2d 3e 20 23 20   # element -> # 
0940: 6f 66 20 70 72 65 64 65 63 65 73 73 6f 72 73 20  of predecessors 
0950: 0a 20 20 20 20 63 68 69 6c 64 72 65 6e 20 3d 20  .    children = 
0960: 7b 7d 20 20 23 20 65 6c 65 6d 65 6e 74 20 2d 3e  {}  # element ->
0970: 20 6c 69 73 74 20 6f 66 20 73 75 63 63 65 73 73   list of success
0980: 6f 72 73 20 0a 20 20 20 20 66 6f 72 20 70 61 72  ors .    for par
0990: 65 6e 74 2c 20 63 68 69 6c 64 20 69 6e 20 70 61  ent, child in pa
09a0: 69 72 6c 69 73 74 3a 20 0a 20 20 20 20 20 20 20  irlist: .       
09b0: 20 23 20 4d 61 6b 65 20 73 75 72 65 20 65 76 65   # Make sure eve
09c0: 72 79 20 65 6c 65 6d 65 6e 74 20 69 73 20 61 20  ry element is a 
09d0: 6b 65 79 20 69 6e 20 6e 75 6d 5f 70 61 72 65 6e  key in num_paren
09e0: 74 73 2e 0a 20 20 20 20 20 20 20 20 69 66 20 6e  ts..        if n
09f0: 6f 74 20 6e 75 6d 5f 70 61 72 65 6e 74 73 2e 68  ot num_parents.h
0a00: 61 73 5f 6b 65 79 28 20 70 61 72 65 6e 74 20 29  as_key( parent )
0a10: 3a 20 0a 20 20 20 20 20 20 20 20 20 20 20 20 6e  : .            n
0a20: 75 6d 5f 70 61 72 65 6e 74 73 5b 70 61 72 65 6e  um_parents[paren
0a30: 74 5d 20 3d 20 30 20 0a 20 20 20 20 20 20 20 20  t] = 0 .        
0a40: 69 66 20 6e 6f 74 20 6e 75 6d 5f 70 61 72 65 6e  if not num_paren
0a50: 74 73 2e 68 61 73 5f 6b 65 79 28 20 63 68 69 6c  ts.has_key( chil
0a60: 64 20 29 3a 20 0a 20 20 20 20 20 20 20 20 20 20  d ): .          
0a70: 20 20 6e 75 6d 5f 70 61 72 65 6e 74 73 5b 63 68    num_parents[ch
0a80: 69 6c 64 5d 20 3d 20 30 20 0a 0a 20 20 20 20 20  ild] = 0 ..     
0a90: 20 20 20 23 20 53 69 6e 63 65 20 63 68 69 6c 64     # Since child
0aa0: 20 68 61 73 20 61 20 70 61 72 65 6e 74 2c 20 69   has a parent, i
0ab0: 6e 63 72 65 6d 65 6e 74 20 63 68 69 6c 64 27 73  ncrement child's
0ac0: 20 6e 75 6d 5f 70 61 72 65 6e 74 73 20 63 6f 75   num_parents cou
0ad0: 6e 74 2e 0a 20 20 20 20 20 20 20 20 6e 75 6d 5f  nt..        num_
0ae0: 70 61 72 65 6e 74 73 5b 63 68 69 6c 64 5d 20 2b  parents[child] +
0af0: 3d 20 31 0a 0a 20 20 20 20 20 20 20 20 23 20 2e  = 1..        # .
0b00: 2e 2e 20 61 6e 64 20 70 61 72 65 6e 74 20 67 61  .. and parent ga
0b10: 69 6e 73 20 61 20 63 68 69 6c 64 2e 0a 20 20 20  ins a child..   
0b20: 20 20 20 20 20 63 68 69 6c 64 72 65 6e 2e 73 65       children.se
0b30: 74 64 65 66 61 75 6c 74 28 70 61 72 65 6e 74 2c  tdefault(parent,
0b40: 20 5b 5d 29 2e 61 70 70 65 6e 64 28 63 68 69 6c   []).append(chil
0b50: 64 29 0a 0a 20 20 20 20 23 20 53 75 63 6b 20 75  d)..    # Suck u
0b60: 70 20 65 76 65 72 79 74 68 69 6e 67 20 77 69 74  p everything wit
0b70: 68 6f 75 74 20 61 20 70 61 72 65 6e 74 2e 0a 20  hout a parent.. 
0b80: 20 20 20 61 6e 73 77 65 72 20 3d 20 5b 78 20 66     answer = [x f
0b90: 6f 72 20 78 20 69 6e 20 6e 75 6d 5f 70 61 72 65  or x in num_pare
0ba0: 6e 74 73 2e 6b 65 79 73 28 29 20 69 66 20 6e 75  nts.keys() if nu
0bb0: 6d 5f 70 61 72 65 6e 74 73 5b 78 5d 20 3d 3d 20  m_parents[x] == 
0bc0: 30 5d 0a 0a 20 20 20 20 23 20 46 6f 72 20 65 76  0]..    # For ev
0bd0: 65 72 79 74 68 69 6e 67 20 69 6e 20 61 6e 73 77  erything in answ
0be0: 65 72 2c 20 6b 6e 6f 63 6b 20 64 6f 77 6e 20 74  er, knock down t
0bf0: 68 65 20 70 61 72 65 6e 74 20 63 6f 75 6e 74 20  he parent count 
0c00: 6f 6e 20 69 74 73 20 63 68 69 6c 64 72 65 6e 2e  on its children.
0c10: 0a 20 20 20 20 23 20 4e 6f 74 65 20 74 68 61 74  .    # Note that
0c20: 20 61 6e 73 77 65 72 20 67 72 6f 77 73 20 2a 69   answer grows *i
0c30: 6e 2a 20 74 68 65 20 6c 6f 6f 70 2e 0a 20 20 20  n* the loop..   
0c40: 20 66 6f 72 20 70 61 72 65 6e 74 20 69 6e 20 61   for parent in a
0c50: 6e 73 77 65 72 3a 20 0a 20 20 20 20 20 20 20 20  nswer: .        
0c60: 64 65 6c 20 6e 75 6d 5f 70 61 72 65 6e 74 73 5b  del num_parents[
0c70: 70 61 72 65 6e 74 5d 0a 20 20 20 20 20 20 20 20  parent].        
0c80: 69 66 20 63 68 69 6c 64 72 65 6e 2e 68 61 73 5f  if children.has_
0c90: 6b 65 79 28 20 70 61 72 65 6e 74 20 29 3a 20 0a  key( parent ): .
0ca0: 20 20 20 20 20 20 20 20 20 20 20 20 66 6f 72 20              for 
0cb0: 63 68 69 6c 64 20 69 6e 20 63 68 69 6c 64 72 65  child in childre
0cc0: 6e 5b 70 61 72 65 6e 74 5d 3a 20 0a 20 20 20 20  n[parent]: .    
0cd0: 20 20 20 20 20 20 20 20 20 20 20 20 6e 75 6d 5f              num_
0ce0: 70 61 72 65 6e 74 73 5b 63 68 69 6c 64 5d 20 2d  parents[child] -
0cf0: 3d 20 31 0a 20 20 20 20 20 20 20 20 20 20 20 20  = 1.            
0d00: 20 20 20 20 69 66 20 6e 75 6d 5f 70 61 72 65 6e      if num_paren
0d10: 74 73 5b 63 68 69 6c 64 5d 20 3d 3d 20 30 3a 20  ts[child] == 0: 
0d20: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
0d30: 20 20 20 20 20 61 6e 73 77 65 72 2e 61 70 70 65       answer.appe
0d40: 6e 64 28 20 63 68 69 6c 64 20 29 20 0a 20 20 20  nd( child ) .   
0d50: 20 20 20 20 20 20 20 20 20 23 20 46 6f 6c 6c 6f           # Follo
0d60: 77 69 6e 67 20 22 64 65 6c 22 20 69 73 6e 27 74  wing "del" isn't
0d70: 20 6e 65 65 64 65 64 3b 20 6a 75 73 74 20 6d 61   needed; just ma
0d80: 6b 65 73 20 0a 20 20 20 20 20 20 20 20 20 20 20  kes .           
0d90: 20 23 20 43 79 63 6c 65 45 72 72 6f 72 20 64 65   # CycleError de
0da0: 74 61 69 6c 73 20 65 61 73 69 65 72 20 74 6f 20  tails easier to 
0db0: 67 72 61 73 70 2e 0a 20 20 20 20 20 20 20 20 20  grasp..         
0dc0: 20 20 20 64 65 6c 20 63 68 69 6c 64 72 65 6e 5b     del children[
0dd0: 70 61 72 65 6e 74 5d 0a 0a 20 20 20 20 69 66 20  parent]..    if 
0de0: 6e 75 6d 5f 70 61 72 65 6e 74 73 3a 20 0a 20 20  num_parents: .  
0df0: 20 20 20 20 20 20 23 20 45 76 65 72 79 74 68 69        # Everythi
0e00: 6e 67 20 69 6e 20 6e 75 6d 5f 70 61 72 65 6e 74  ng in num_parent
0e10: 73 20 68 61 73 20 61 74 20 6c 65 61 73 74 20 6f  s has at least o
0e20: 6e 65 20 63 68 69 6c 64 20 2d 3e 20 0a 20 20 20  ne child -> .   
0e30: 20 20 20 20 20 23 20 74 68 65 72 65 27 73 20 61       # there's a
0e40: 20 63 79 63 6c 65 2e 0a 20 20 20 20 20 20 20 20   cycle..        
0e50: 72 61 69 73 65 20 43 79 63 6c 65 45 72 72 6f 72  raise CycleError
0e60: 28 61 6e 73 77 65 72 2c 20 6e 75 6d 5f 70 61 72  (answer, num_par
0e70: 65 6e 74 73 2c 20 63 68 69 6c 64 72 65 6e 29 0a  ents, children).
0e80: 20 20 20 20 72 65 74 75 72 6e 20 61 6e 73 77 65      return answe
0e90: 72 20 0a 0a 64 65 66 20 74 6f 70 73 6f 72 74 5f  r ..def topsort_
0ea0: 6c 65 76 65 6c 73 28 70 61 69 72 6c 69 73 74 29  levels(pairlist)
0eb0: 3a 0a 20 20 20 20 22 22 22 54 6f 70 6f 6c 6f 67  :.    """Topolog
0ec0: 69 63 61 6c 6c 79 20 73 6f 72 74 20 61 20 6c 69  ically sort a li
0ed0: 73 74 20 6f 66 20 28 70 61 72 65 6e 74 2c 20 63  st of (parent, c
0ee0: 68 69 6c 64 29 20 70 61 69 72 73 20 69 6e 74 6f  hild) pairs into
0ef0: 20 64 65 70 74 68 20 6c 65 76 65 6c 73 2e 0a 0a   depth levels...
0f00: 20 20 20 20 54 68 69 73 20 72 65 74 75 72 6e 73      This returns
0f10: 20 61 20 67 65 6e 65 72 61 74 6f 72 2e 20 0a 20   a generator. . 
0f20: 20 20 20 54 75 72 6e 20 74 68 69 73 20 69 6e 74     Turn this int
0f30: 6f 20 61 20 61 6e 20 69 74 65 72 61 74 6f 72 20  o a an iterator 
0f40: 75 73 69 6e 67 20 74 68 65 20 69 74 65 72 20 62  using the iter b
0f50: 75 69 6c 74 2d 69 6e 20 66 75 6e 63 74 69 6f 6e  uilt-in function
0f60: 2e 0a 20 20 20 20 28 69 66 20 79 6f 75 20 69 74  ..    (if you it
0f70: 65 72 61 74 65 20 6f 76 65 72 20 74 68 65 20 69  erate over the i
0f80: 74 65 72 61 74 6f 72 2c 20 65 61 63 68 20 65 6c  terator, each el
0f90: 65 6d 65 6e 74 20 67 65 74 73 20 67 65 6e 65 72  ement gets gener
0fa0: 61 74 65 64 20 77 68 65 6e 0a 20 20 20 20 69 74  ated when.    it
0fb0: 20 69 73 20 61 73 6b 65 64 20 66 6f 72 2c 20 72   is asked for, r
0fc0: 61 74 68 65 72 20 74 68 61 6e 20 67 65 6e 65 72  ather than gener
0fd0: 61 74 69 6e 67 20 74 68 65 20 77 68 6f 6c 65 20  ating the whole 
0fe0: 6c 69 73 74 20 75 70 2d 66 72 6f 6e 74 2e 29 0a  list up-front.).
0ff0: 0a 20 20 20 20 45 61 63 68 20 67 65 6e 65 72 61  .    Each genera
1000: 74 65 64 20 65 6c 65 6d 65 6e 74 20 69 73 20 61  ted element is a
1010: 20 6c 69 73 74 20 6f 66 20 69 74 65 6d 73 20 61   list of items a
1020: 74 20 74 68 61 74 20 64 65 70 65 6e 64 65 6e 63  t that dependenc
1030: 79 20 6c 65 76 65 6c 2e 0a 0a 20 20 20 20 3e 3e  y level...    >>
1040: 3e 20 64 65 70 65 6e 64 65 6e 63 79 5f 70 61 69  > dependency_pai
1050: 72 73 20 3d 20 5b 28 31 2c 32 29 2c 20 28 33 2c  rs = [(1,2), (3,
1060: 34 29 2c 20 28 35 2c 36 29 2c 20 28 31 2c 33 29  4), (5,6), (1,3)
1070: 2c 20 28 31 2c 35 29 2c 20 28 31 2c 36 29 2c 20  , (1,5), (1,6), 
1080: 28 32 2c 35 29 5d 0a 20 20 20 20 3e 3e 3e 20 66  (2,5)].    >>> f
1090: 6f 72 20 6c 65 76 65 6c 20 69 6e 20 69 74 65 72  or level in iter
10a0: 28 74 6f 70 73 6f 72 74 5f 6c 65 76 65 6c 73 28  (topsort_levels(
10b0: 20 64 65 70 65 6e 64 65 6e 63 79 5f 70 61 69 72   dependency_pair
10c0: 73 20 29 29 3a 0a 20 20 20 20 2e 2e 2e 20 20 20  s )):.    ...   
10d0: 20 70 72 69 6e 74 20 6c 65 76 65 6c 0a 20 20 20   print level.   
10e0: 20 5b 31 5d 0a 20 20 20 20 5b 32 2c 20 33 5d 0a   [1].    [2, 3].
10f0: 20 20 20 20 5b 34 2c 20 35 5d 0a 20 20 20 20 5b      [4, 5].    [
1100: 36 5d 0a 0a 20 20 20 20 3e 3e 3e 20 64 65 70 65  6]..    >>> depe
1110: 6e 64 65 6e 63 79 5f 70 61 69 72 73 20 3d 20 5b  ndency_pairs = [
1120: 28 31 2c 32 29 2c 20 28 31 2c 33 29 2c 20 28 32  (1,2), (1,3), (2
1130: 2c 34 29 2c 20 28 33 2c 34 29 2c 20 28 35 2c 36  ,4), (3,4), (5,6
1140: 29 2c 20 28 34 2c 35 29 5d 0a 20 20 20 20 3e 3e  ), (4,5)].    >>
1150: 3e 20 66 6f 72 20 6c 65 76 65 6c 20 69 6e 20 69  > for level in i
1160: 74 65 72 28 74 6f 70 73 6f 72 74 5f 6c 65 76 65  ter(topsort_leve
1170: 6c 73 28 20 64 65 70 65 6e 64 65 6e 63 79 5f 70  ls( dependency_p
1180: 61 69 72 73 20 29 29 3a 0a 20 20 20 20 2e 2e 2e  airs )):.    ...
1190: 20 20 20 20 70 72 69 6e 74 20 6c 65 76 65 6c 0a      print level.
11a0: 20 20 20 20 5b 31 5d 0a 20 20 20 20 5b 32 2c 20      [1].    [2, 
11b0: 33 5d 0a 20 20 20 20 5b 34 5d 0a 20 20 20 20 5b  3].    [4].    [
11c0: 35 5d 0a 20 20 20 20 5b 36 5d 0a 0a 20 20 20 20  5].    [6]..    
11d0: 3e 3e 3e 20 64 65 70 65 6e 64 65 6e 63 79 5f 70  >>> dependency_p
11e0: 61 69 72 73 20 3d 20 5b 28 31 2c 32 29 2c 20 28  airs = [(1,2), (
11f0: 32 2c 33 29 2c 20 28 33 2c 34 29 2c 20 28 34 2c  2,3), (3,4), (4,
1200: 20 33 29 5d 0a 20 20 20 20 3e 3e 3e 20 74 72 79   3)].    >>> try
1210: 3a 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20 66 6f  :.    ...     fo
1220: 72 20 6c 65 76 65 6c 20 69 6e 20 69 74 65 72 28  r level in iter(
1230: 74 6f 70 73 6f 72 74 5f 6c 65 76 65 6c 73 28 20  topsort_levels( 
1240: 64 65 70 65 6e 64 65 6e 63 79 5f 70 61 69 72 73  dependency_pairs
1250: 20 29 29 3a 0a 20 20 20 20 2e 2e 2e 20 20 20 20   )):.    ...    
1260: 20 20 20 20 20 70 72 69 6e 74 20 6c 65 76 65 6c       print level
1270: 0a 20 20 20 20 2e 2e 2e 20 65 78 63 65 70 74 20  .    ... except 
1280: 43 79 63 6c 65 45 72 72 6f 72 2c 20 65 78 63 3a  CycleError, exc:
1290: 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20 70 72 69  .    ...     pri
12a0: 6e 74 20 27 43 79 63 6c 65 45 72 72 6f 72 3a 27  nt 'CycleError:'
12b0: 2c 20 65 78 63 0a 20 20 20 20 5b 31 5d 0a 20 20  , exc.    [1].  
12c0: 20 20 5b 32 5d 0a 20 20 20 20 43 79 63 6c 65 45    [2].    CycleE
12d0: 72 72 6f 72 3a 20 28 7b 33 3a 20 31 2c 20 34 3a  rror: ({3: 1, 4:
12e0: 20 31 7d 2c 20 7b 33 3a 20 5b 34 5d 2c 20 34 3a   1}, {3: [4], 4:
12f0: 20 5b 33 5d 7d 29 0a 0a 0a 20 20 20 20 54 68 65   [3]})...    The
1300: 20 63 79 63 6c 65 20 65 72 72 6f 72 20 73 68 6f   cycle error sho
1310: 75 6c 64 20 6c 6f 6f 6b 20 6c 69 6b 65 2e 0a 20  uld look like.. 
1320: 20 20 20 43 79 63 6c 65 45 72 72 6f 72 3a 20 28     CycleError: (
1330: 7b 33 3a 20 31 2c 20 34 3a 20 31 7d 2c 20 7b 33  {3: 1, 4: 1}, {3
1340: 3a 20 5b 34 5d 2c 20 34 3a 20 5b 33 5d 7d 29 0a  : [4], 4: [3]}).
1350: 20 20 20 20 23 20 74 6f 64 6f 3a 20 4d 61 6b 65      # todo: Make
1360: 20 74 68 65 20 64 6f 63 74 65 73 74 20 6d 6f 72   the doctest mor
1370: 65 20 72 6f 62 75 73 74 20 28 69 2e 65 2e 20 68  e robust (i.e. h
1380: 61 6e 64 6c 65 20 61 72 62 69 74 72 61 72 79 20  andle arbitrary 
1390: 64 69 63 74 20 6f 72 64 65 72 29 2e 0a 0a 20 20  dict order)...  
13a0: 20 20 22 22 22 0a 20 20 20 20 6e 75 6d 5f 70 61    """.    num_pa
13b0: 72 65 6e 74 73 20 3d 20 7b 7d 20 20 23 20 65 6c  rents = {}  # el
13c0: 65 6d 65 6e 74 20 2d 3e 20 23 20 6f 66 20 70 72  ement -> # of pr
13d0: 65 64 65 63 65 73 73 6f 72 73 20 0a 20 20 20 20  edecessors .    
13e0: 63 68 69 6c 64 72 65 6e 20 3d 20 7b 7d 20 20 23  children = {}  #
13f0: 20 65 6c 65 6d 65 6e 74 20 2d 3e 20 6c 69 73 74   element -> list
1400: 20 6f 66 20 73 75 63 63 65 73 73 6f 72 73 20 0a   of successors .
1410: 20 20 20 20 66 6f 72 20 70 61 72 65 6e 74 2c 20      for parent, 
1420: 63 68 69 6c 64 20 69 6e 20 70 61 69 72 6c 69 73  child in pairlis
1430: 74 3a 20 0a 20 20 20 20 20 20 20 20 23 20 4d 61  t: .        # Ma
1440: 6b 65 20 73 75 72 65 20 65 76 65 72 79 20 65 6c  ke sure every el
1450: 65 6d 65 6e 74 20 69 73 20 61 20 6b 65 79 20 69  ement is a key i
1460: 6e 20 6e 75 6d 5f 70 61 72 65 6e 74 73 2e 0a 20  n num_parents.. 
1470: 20 20 20 20 20 20 20 69 66 20 6e 6f 74 20 6e 75         if not nu
1480: 6d 5f 70 61 72 65 6e 74 73 2e 68 61 73 5f 6b 65  m_parents.has_ke
1490: 79 28 20 70 61 72 65 6e 74 20 29 3a 20 0a 20 20  y( parent ): .  
14a0: 20 20 20 20 20 20 20 20 20 20 6e 75 6d 5f 70 61            num_pa
14b0: 72 65 6e 74 73 5b 70 61 72 65 6e 74 5d 20 3d 20  rents[parent] = 
14c0: 30 20 0a 20 20 20 20 20 20 20 20 69 66 20 6e 6f  0 .        if no
14d0: 74 20 6e 75 6d 5f 70 61 72 65 6e 74 73 2e 68 61  t num_parents.ha
14e0: 73 5f 6b 65 79 28 20 63 68 69 6c 64 20 29 3a 20  s_key( child ): 
14f0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 6e 75 6d  .            num
1500: 5f 70 61 72 65 6e 74 73 5b 63 68 69 6c 64 5d 20  _parents[child] 
1510: 3d 20 30 20 0a 0a 20 20 20 20 20 20 20 20 23 20  = 0 ..        # 
1520: 53 69 6e 63 65 20 63 68 69 6c 64 20 68 61 73 20  Since child has 
1530: 61 20 70 61 72 65 6e 74 2c 20 69 6e 63 72 65 6d  a parent, increm
1540: 65 6e 74 20 63 68 69 6c 64 27 73 20 6e 75 6d 5f  ent child's num_
1550: 70 61 72 65 6e 74 73 20 63 6f 75 6e 74 2e 0a 20  parents count.. 
1560: 20 20 20 20 20 20 20 6e 75 6d 5f 70 61 72 65 6e         num_paren
1570: 74 73 5b 63 68 69 6c 64 5d 20 2b 3d 20 31 0a 0a  ts[child] += 1..
1580: 20 20 20 20 20 20 20 20 23 20 2e 2e 2e 20 61 6e          # ... an
1590: 64 20 70 61 72 65 6e 74 20 67 61 69 6e 73 20 61  d parent gains a
15a0: 20 63 68 69 6c 64 2e 0a 20 20 20 20 20 20 20 20   child..        
15b0: 63 68 69 6c 64 72 65 6e 2e 73 65 74 64 65 66 61  children.setdefa
15c0: 75 6c 74 28 70 61 72 65 6e 74 2c 20 5b 5d 29 2e  ult(parent, []).
15d0: 61 70 70 65 6e 64 28 63 68 69 6c 64 29 0a 0a 20  append(child).. 
15e0: 20 20 20 72 65 74 75 72 6e 20 74 6f 70 73 6f 72     return topsor
15f0: 74 5f 6c 65 76 65 6c 73 5f 63 6f 72 65 28 6e 75  t_levels_core(nu
1600: 6d 5f 70 61 72 65 6e 74 73 2c 20 63 68 69 6c 64  m_parents, child
1610: 72 65 6e 29 0a 0a 64 65 66 20 74 6f 70 73 6f 72  ren)..def topsor
1620: 74 5f 6c 65 76 65 6c 73 5f 63 6f 72 65 28 6e 75  t_levels_core(nu
1630: 6d 5f 70 61 72 65 6e 74 73 2c 20 63 68 69 6c 64  m_parents, child
1640: 72 65 6e 29 3a 0a 20 20 20 20 22 22 22 54 6f 70  ren):.    """Top
1650: 6f 6c 6f 67 69 63 61 6c 6c 79 20 73 6f 72 74 20  ologically sort 
1660: 61 20 62 75 6e 63 68 20 6f 66 20 69 6e 74 65 72  a bunch of inter
1670: 64 65 70 65 6e 64 65 6e 74 20 69 74 65 6d 73 20  dependent items 
1680: 62 61 73 65 64 20 6f 6e 20 64 65 70 65 6e 64 65  based on depende
1690: 6e 63 79 2e 0a 0a 20 20 20 20 54 68 69 73 20 72  ncy...    This r
16a0: 65 74 75 72 6e 73 20 61 20 67 65 6e 65 72 61 74  eturns a generat
16b0: 6f 72 2e 0a 20 20 20 20 54 75 72 6e 20 74 68 69  or..    Turn thi
16c0: 73 20 69 6e 74 6f 20 61 20 61 6e 20 69 74 65 72  s into a an iter
16d0: 61 74 6f 72 20 75 73 69 6e 67 20 74 68 65 20 69  ator using the i
16e0: 74 65 72 20 62 75 69 6c 74 2d 69 6e 20 66 75 6e  ter built-in fun
16f0: 63 74 69 6f 6e 2e 0a 20 20 20 20 28 69 66 20 79  ction..    (if y
1700: 6f 75 20 69 74 65 72 61 74 65 20 6f 76 65 72 20  ou iterate over 
1710: 74 68 65 20 69 74 65 72 61 74 6f 72 2c 20 65 61  the iterator, ea
1720: 63 68 20 65 6c 65 6d 65 6e 74 20 67 65 74 73 20  ch element gets 
1730: 67 65 6e 65 72 61 74 65 64 20 77 68 65 6e 0a 20  generated when. 
1740: 20 20 20 69 74 20 69 73 20 61 73 6b 65 64 20 66     it is asked f
1750: 6f 72 2c 20 72 61 74 68 65 72 20 74 68 61 6e 20  or, rather than 
1760: 67 65 6e 65 72 61 74 69 6e 67 20 74 68 65 20 77  generating the w
1770: 68 6f 6c 65 20 6c 69 73 74 20 75 70 2d 66 72 6f  hole list up-fro
1780: 6e 74 2e 29 0a 0a 20 20 20 20 45 61 63 68 20 67  nt.)..    Each g
1790: 65 6e 65 72 61 74 65 64 20 65 6c 65 6d 65 6e 74  enerated element
17a0: 20 69 73 20 61 20 6c 69 73 74 20 6f 66 20 69 74   is a list of it
17b0: 65 6d 73 20 61 74 20 74 68 61 74 20 64 65 70 65  ems at that depe
17c0: 6e 64 65 6e 63 79 20 6c 65 76 65 6c 2e 0a 0a 20  ndency level... 
17d0: 20 20 20 3e 3e 3e 20 6c 69 73 74 28 74 6f 70 73     >>> list(tops
17e0: 6f 72 74 5f 6c 65 76 65 6c 73 5f 63 6f 72 65 28  ort_levels_core(
17f0: 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20 20 20 20  .    ...        
1800: 20 20 7b 31 3a 20 30 2c 20 32 3a 20 31 2c 20 33    {1: 0, 2: 1, 3
1810: 3a 20 31 2c 20 34 3a 20 31 2c 20 35 3a 20 32 2c  : 1, 4: 1, 5: 2,
1820: 20 36 3a 20 32 7d 2c 0a 20 20 20 20 2e 2e 2e 20   6: 2},.    ... 
1830: 20 20 20 20 20 20 20 20 20 7b 31 3a 20 5b 32 2c           {1: [2,
1840: 20 33 2c 20 35 2c 20 36 5d 2c 20 32 3a 20 5b 35   3, 5, 6], 2: [5
1850: 5d 2c 20 33 3a 20 5b 34 5d 2c 20 34 3a 20 5b 5d  ], 3: [4], 4: []
1860: 2c 20 35 3a 20 5b 36 5d 7d 29 29 0a 20 20 20 20  , 5: [6]})).    
1870: 5b 5b 31 5d 2c 20 5b 32 2c 20 33 5d 2c 20 5b 34  [[1], [2, 3], [4
1880: 2c 20 35 5d 2c 20 5b 36 5d 5d 0a 0a 20 20 20 20  , 5], [6]]..    
1890: 3e 3e 3e 20 6c 69 73 74 28 74 6f 70 73 6f 72 74  >>> list(topsort
18a0: 5f 6c 65 76 65 6c 73 5f 63 6f 72 65 28 0a 20 20  _levels_core(.  
18b0: 20 20 2e 2e 2e 20 20 20 20 20 20 20 20 20 20 7b    ...          {
18c0: 31 3a 20 30 2c 20 32 3a 20 32 2c 20 33 3a 20 31  1: 0, 2: 2, 3: 1
18d0: 7d 2c 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20 20  },.    ...      
18e0: 20 20 20 20 7b 31 3a 20 5b 32 5d 2c 20 32 3a 20      {1: [2], 2: 
18f0: 5b 33 5d 2c 20 33 3a 20 5b 32 5d 7d 29 29 0a 20  [3], 3: [2]})). 
1900: 20 20 20 54 72 61 63 65 62 61 63 6b 20 28 6d 6f     Traceback (mo
1910: 73 74 20 72 65 63 65 6e 74 20 63 61 6c 6c 20 6c  st recent call l
1920: 61 73 74 29 3a 0a 20 20 20 20 43 79 63 6c 65 45  ast):.    CycleE
1930: 72 72 6f 72 3a 20 28 7b 32 3a 20 31 2c 20 33 3a  rror: ({2: 1, 3:
1940: 20 31 7d 2c 20 7b 32 3a 20 5b 33 5d 2c 20 33 3a   1}, {2: [3], 3:
1950: 20 5b 32 5d 7d 29 0a 0a 20 20 20 20 54 68 69 73   [2]})..    This
1960: 20 66 75 6e 63 74 69 6f 6e 20 68 61 73 20 61 20   function has a 
1970: 6d 6f 72 65 20 63 6f 6d 70 6c 69 63 61 74 65 64  more complicated
1980: 20 69 6e 74 65 72 66 61 63 65 20 74 68 61 6e 20   interface than 
1990: 74 6f 70 73 6f 72 74 5f 6c 65 76 65 6c 73 2c 0a  topsort_levels,.
19a0: 20 20 20 20 62 75 74 20 69 73 20 75 73 65 66 75      but is usefu
19b0: 6c 20 69 66 20 74 68 65 20 64 61 74 61 20 69 73  l if the data is
19c0: 20 65 61 73 69 65 72 20 74 6f 20 67 65 6e 65 72   easier to gener
19d0: 61 74 65 20 69 6e 20 74 68 69 73 20 66 6f 72 6d  ate in this form
19e0: 2e 0a 0a 20 20 20 20 41 72 67 75 6d 65 6e 74 73  ...    Arguments
19f0: 3a 0a 20 20 20 20 6e 75 6d 5f 70 61 72 65 6e 74  :.    num_parent
1a00: 73 20 2d 2d 20 6b 65 79 3a 20 69 74 65 6d 2c 20  s -- key: item, 
1a10: 76 61 6c 75 65 3a 20 6e 75 6d 62 65 72 20 6f 66  value: number of
1a20: 20 70 61 72 65 6e 74 73 20 28 70 72 65 64 65 63   parents (predec
1a30: 65 73 73 6f 72 73 29 0a 20 20 20 20 63 68 69 6c  essors).    chil
1a40: 64 72 65 6e 20 2d 2d 20 6b 65 79 3a 20 69 74 65  dren -- key: ite
1a50: 6d 2c 20 76 61 6c 75 65 3a 20 6c 69 73 74 20 6f  m, value: list o
1a60: 66 20 63 68 69 6c 64 72 65 6e 20 28 73 75 63 63  f children (succ
1a70: 65 73 73 6f 72 73 29 0a 0a 20 20 20 20 22 22 22  essors)..    """
1a80: 0a 20 20 20 20 77 68 69 6c 65 20 31 3a 0a 20 20  .    while 1:.  
1a90: 20 20 20 20 20 20 23 20 53 75 63 6b 20 75 70 20        # Suck up 
1aa0: 65 76 65 72 79 74 68 69 6e 67 20 77 69 74 68 6f  everything witho
1ab0: 75 74 20 61 20 70 72 65 64 65 63 65 73 73 6f 72  ut a predecessor
1ac0: 2e 0a 20 20 20 20 20 20 20 20 6c 65 76 65 6c 5f  ..        level_
1ad0: 70 61 72 65 6e 74 73 20 3d 20 5b 78 20 66 6f 72  parents = [x for
1ae0: 20 78 20 69 6e 20 6e 75 6d 5f 70 61 72 65 6e 74   x in num_parent
1af0: 73 2e 6b 65 79 73 28 29 20 69 66 20 6e 75 6d 5f  s.keys() if num_
1b00: 70 61 72 65 6e 74 73 5b 78 5d 20 3d 3d 20 30 5d  parents[x] == 0]
1b10: 0a 0a 20 20 20 20 20 20 20 20 69 66 20 6e 6f 74  ..        if not
1b20: 20 6c 65 76 65 6c 5f 70 61 72 65 6e 74 73 3a 0a   level_parents:.
1b30: 20 20 20 20 20 20 20 20 20 20 20 20 62 72 65 61              brea
1b40: 6b 0a 0a 20 20 20 20 20 20 20 20 23 20 4f 66 66  k..        # Off
1b50: 65 72 20 74 68 65 20 6e 65 78 74 20 67 65 6e 65  er the next gene
1b60: 72 61 74 65 64 20 69 74 65 6d 2c 0a 20 20 20 20  rated item,.    
1b70: 20 20 20 20 23 20 77 68 69 63 68 20 69 73 20 61      # which is a
1b80: 20 6c 69 73 74 20 6f 66 20 74 68 65 20 69 74 65   list of the ite
1b90: 6d 73 20 61 74 20 74 68 69 73 20 64 65 70 65 6e  ms at this depen
1ba0: 64 65 6e 63 79 20 6c 65 76 65 6c 2e 0a 20 20 20  dency level..   
1bb0: 20 20 20 20 20 79 69 65 6c 64 20 6c 65 76 65 6c       yield level
1bc0: 5f 70 61 72 65 6e 74 73 0a 0a 20 20 20 20 20 20  _parents..      
1bd0: 20 20 23 20 46 6f 72 20 65 76 65 72 79 74 68 69    # For everythi
1be0: 6e 67 20 69 74 65 6d 20 69 6e 20 74 68 69 73 20  ng item in this 
1bf0: 6c 65 76 65 6c 2c 0a 20 20 20 20 20 20 20 20 23  level,.        #
1c00: 20 64 65 63 72 65 6d 65 6e 74 20 74 68 65 20 70   decrement the p
1c10: 61 72 65 6e 74 20 63 6f 75 6e 74 2c 0a 20 20 20  arent count,.   
1c20: 20 20 20 20 20 23 20 73 69 6e 63 65 20 77 65 20       # since we 
1c30: 68 61 76 65 20 61 63 63 6f 75 6e 74 65 64 20 66  have accounted f
1c40: 6f 72 20 69 74 73 20 70 61 72 65 6e 74 2e 0a 20  or its parent.. 
1c50: 20 20 20 20 20 20 20 66 6f 72 20 6c 65 76 65 6c         for level
1c60: 5f 70 61 72 65 6e 74 20 69 6e 20 6c 65 76 65 6c  _parent in level
1c70: 5f 70 61 72 65 6e 74 73 3a 0a 0a 20 20 20 20 20  _parents:..     
1c80: 20 20 20 20 20 20 20 64 65 6c 20 6e 75 6d 5f 70         del num_p
1c90: 61 72 65 6e 74 73 5b 6c 65 76 65 6c 5f 70 61 72  arents[level_par
1ca0: 65 6e 74 5d 0a 0a 20 20 20 20 20 20 20 20 20 20  ent]..          
1cb0: 20 20 69 66 20 63 68 69 6c 64 72 65 6e 2e 68 61    if children.ha
1cc0: 73 5f 6b 65 79 28 6c 65 76 65 6c 5f 70 61 72 65  s_key(level_pare
1cd0: 6e 74 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20  nt):.           
1ce0: 20 20 20 20 20 66 6f 72 20 6c 65 76 65 6c 5f 70       for level_p
1cf0: 61 72 65 6e 74 5f 63 68 69 6c 64 20 69 6e 20 63  arent_child in c
1d00: 68 69 6c 64 72 65 6e 5b 6c 65 76 65 6c 5f 70 61  hildren[level_pa
1d10: 72 65 6e 74 5d 3a 0a 20 20 20 20 20 20 20 20 20  rent]:.         
1d20: 20 20 20 20 20 20 20 20 20 20 20 6e 75 6d 5f 70             num_p
1d30: 61 72 65 6e 74 73 5b 6c 65 76 65 6c 5f 70 61 72  arents[level_par
1d40: 65 6e 74 5f 63 68 69 6c 64 5d 20 2d 3d 20 31 0a  ent_child] -= 1.
1d50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1d60: 64 65 6c 20 63 68 69 6c 64 72 65 6e 5b 6c 65 76  del children[lev
1d70: 65 6c 5f 70 61 72 65 6e 74 5d 0a 20 20 20 20 20  el_parent].     
1d80: 20 20 20 0a 20 20 20 20 69 66 20 6e 75 6d 5f 70     .    if num_p
1d90: 61 72 65 6e 74 73 3a 20 0a 20 20 20 20 20 20 20  arents: .       
1da0: 20 23 20 45 76 65 72 79 74 68 69 6e 67 20 69 6e   # Everything in
1db0: 20 6e 75 6d 5f 70 61 72 65 6e 74 73 20 68 61 73   num_parents has
1dc0: 20 61 74 20 6c 65 61 73 74 20 6f 6e 65 20 63 68   at least one ch
1dd0: 69 6c 64 20 2d 3e 20 0a 20 20 20 20 20 20 20 20  ild -> .        
1de0: 23 20 74 68 65 72 65 27 73 20 61 20 63 79 63 6c  # there's a cycl
1df0: 65 2e 0a 20 20 20 20 20 20 20 20 72 61 69 73 65  e..        raise
1e00: 20 43 79 63 6c 65 45 72 72 6f 72 28 6e 75 6d 5f   CycleError(num_
1e10: 70 61 72 65 6e 74 73 2c 20 63 68 69 6c 64 72 65  parents, childre
1e20: 6e 29 0a 20 20 20 20 65 6c 73 65 3a 0a 20 20 20  n).    else:.   
1e30: 20 20 20 20 20 23 20 54 68 69 73 20 69 73 20 74       # This is t
1e40: 68 65 20 65 6e 64 20 6f 66 20 74 68 65 20 67 65  he end of the ge
1e50: 6e 65 72 61 74 6f 72 2e 0a 20 20 20 20 20 20 20  nerator..       
1e60: 20 72 61 69 73 65 20 53 74 6f 70 49 74 65 72 61   raise StopItera
1e70: 74 69 6f 6e 0a 0a 0a 64 65 66 20 66 69 6e 64 5f  tion...def find_
1e80: 63 79 63 6c 65 73 28 70 61 72 65 6e 74 5f 63 68  cycles(parent_ch
1e90: 69 6c 64 72 65 6e 29 3a 0a 20 20 20 20 22 22 22  ildren):.    """
1ea0: 59 69 65 6c 64 20 63 79 63 6c 65 73 2e 20 45 61  Yield cycles. Ea
1eb0: 63 68 20 72 65 73 75 6c 74 20 69 73 20 61 20 6c  ch result is a l
1ec0: 69 73 74 20 6f 66 20 69 74 65 6d 73 20 63 6f 6d  ist of items com
1ed0: 70 72 69 73 69 6e 67 20 61 20 63 79 63 6c 65 2e  prising a cycle.
1ee0: 0a 0a 20 20 20 20 55 73 65 20 61 20 27 73 74 61  ..    Use a 'sta
1ef0: 63 6b 27 20 62 61 73 65 64 20 61 70 70 72 6f 61  ck' based approa
1f00: 63 68 20 74 6f 20 66 69 6e 64 20 61 6c 6c 20 74  ch to find all t
1f10: 68 65 20 63 79 63 6c 65 73 2e 0a 20 20 20 20 54  he cycles..    T
1f20: 68 69 73 20 69 73 20 61 20 67 65 6e 65 72 61 74  his is a generat
1f30: 6f 72 2c 20 73 6f 20 79 69 65 6c 64 73 20 65 61  or, so yields ea
1f40: 63 68 20 63 79 63 6c 65 20 61 73 20 69 74 20 66  ch cycle as it f
1f50: 69 6e 64 73 20 69 74 2e 0a 0a 20 20 20 20 49 74  inds it...    It
1f60: 20 69 73 20 69 6d 70 6c 69 63 69 74 20 74 68 61   is implicit tha
1f70: 74 20 74 68 65 20 6c 61 73 74 20 69 74 65 6d 20  t the last item 
1f80: 69 6e 20 65 61 63 68 20 63 79 63 6c 65 20 6c 69  in each cycle li
1f90: 73 74 20 69 73 20 61 20 70 61 72 65 6e 74 20 6f  st is a parent o
1fa0: 66 20 74 68 65 0a 20 20 20 20 66 69 72 73 74 20  f the.    first 
1fb0: 69 74 65 6d 20 28 74 68 65 72 65 62 79 20 66 6f  item (thereby fo
1fc0: 72 6d 69 6e 67 20 61 20 63 79 63 6c 65 29 2e 0a  rming a cycle)..
1fd0: 0a 20 20 20 20 41 72 67 75 6d 65 6e 74 73 3a 0a  .    Arguments:.
1fe0: 20 20 20 20 70 61 72 65 6e 74 5f 63 68 69 6c 64      parent_child
1ff0: 72 65 6e 20 2d 2d 20 70 61 72 65 6e 74 20 2d 3e  ren -- parent ->
2000: 20 63 6f 6c 6c 65 63 74 69 6f 6e 20 6f 66 20 63   collection of c
2010: 68 69 6c 64 72 65 6e 0a 0a 20 20 20 20 53 69 6d  hildren..    Sim
2020: 70 6c 65 73 74 20 63 79 63 6c 65 3a 0a 20 20 20  plest cycle:.   
2030: 20 3e 3e 3e 20 63 79 63 6c 65 73 20 3d 20 6c 69   >>> cycles = li
2040: 73 74 28 66 69 6e 64 5f 63 79 63 6c 65 73 28 7b  st(find_cycles({
2050: 27 41 27 3a 20 5b 27 42 27 5d 2c 20 27 42 27 3a  'A': ['B'], 'B':
2060: 20 5b 27 41 27 5d 7d 29 29 0a 20 20 20 20 3e 3e   ['A']})).    >>
2070: 3e 20 6c 65 6e 28 63 79 63 6c 65 73 29 0a 20 20  > len(cycles).  
2080: 20 20 31 0a 20 20 20 20 3e 3e 3e 20 63 79 63 6c    1.    >>> cycl
2090: 65 20 3d 20 63 79 63 6c 65 73 5b 30 5d 0a 20 20  e = cycles[0].  
20a0: 20 20 3e 3e 3e 20 63 79 63 6c 65 2e 73 6f 72 74    >>> cycle.sort
20b0: 28 29 0a 20 20 20 20 3e 3e 3e 20 70 72 69 6e 74  ().    >>> print
20c0: 20 63 79 63 6c 65 0a 20 20 20 20 5b 27 41 27 2c   cycle.    ['A',
20d0: 20 27 42 27 5d 0a 0a 20 20 20 20 53 69 6d 70 6c   'B']..    Simpl
20e0: 65 73 74 20 63 79 63 6c 65 20 77 69 74 68 20 65  est cycle with e
20f0: 78 74 72 61 20 62 61 67 67 61 67 65 20 61 74 20  xtra baggage at 
2100: 74 68 65 20 73 74 61 72 74 20 61 6e 64 20 74 68  the start and th
2110: 65 20 65 6e 64 3a 0a 20 20 20 20 3e 3e 3e 20 63  e end:.    >>> c
2120: 79 63 6c 65 73 20 3d 20 6c 69 73 74 28 66 69 6e  ycles = list(fin
2130: 64 5f 63 79 63 6c 65 73 28 70 61 72 65 6e 74 5f  d_cycles(parent_
2140: 63 68 69 6c 64 72 65 6e 3d 7b 27 41 27 3a 20 5b  children={'A': [
2150: 27 42 27 5d 2c 0a 20 20 20 20 2e 2e 2e 20 20 20  'B'],.    ...   
2160: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2170: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2180: 20 20 20 20 20 20 20 20 20 27 42 27 3a 20 5b 27           'B': ['
2190: 43 27 5d 2c 0a 20 20 20 20 2e 2e 2e 20 20 20 20  C'],.    ...    
21a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
21b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
21c0: 20 20 20 20 20 20 20 20 27 43 27 3a 20 5b 27 42          'C': ['B
21d0: 27 2c 20 27 44 27 5d 2c 0a 20 20 20 20 2e 2e 2e  ', 'D'],.    ...
21e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
21f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2200: 20 20 20 20 20 20 20 20 20 20 20 20 27 44 27 3a              'D':
2210: 20 5b 5d 2c 0a 20 20 20 20 2e 2e 2e 20 20 20 20   [],.    ...    
2220: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2230: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2240: 20 20 20 20 20 20 20 20 7d 29 29 0a 20 20 20 20          })).    
2250: 3e 3e 3e 20 6c 65 6e 28 63 79 63 6c 65 73 29 0a  >>> len(cycles).
2260: 20 20 20 20 31 0a 20 20 20 20 3e 3e 3e 20 63 79      1.    >>> cy
2270: 63 6c 65 20 3d 20 63 79 63 6c 65 73 5b 30 5d 0a  cle = cycles[0].
2280: 20 20 20 20 3e 3e 3e 20 63 79 63 6c 65 2e 73 6f      >>> cycle.so
2290: 72 74 28 29 0a 20 20 20 20 3e 3e 3e 20 70 72 69  rt().    >>> pri
22a0: 6e 74 20 63 79 63 6c 65 0a 20 20 20 20 5b 27 42  nt cycle.    ['B
22b0: 27 2c 20 27 43 27 5d 0a 0a 20 20 20 20 44 6f 75  ', 'C']..    Dou
22c0: 62 6c 65 20 63 79 63 6c 65 3a 0a 20 20 20 20 3e  ble cycle:.    >
22d0: 3e 3e 20 63 79 63 6c 65 73 20 3d 20 6c 69 73 74  >> cycles = list
22e0: 28 66 69 6e 64 5f 63 79 63 6c 65 73 28 70 61 72  (find_cycles(par
22f0: 65 6e 74 5f 63 68 69 6c 64 72 65 6e 3d 7b 27 41  ent_children={'A
2300: 27 3a 20 5b 27 42 27 5d 2c 0a 20 20 20 20 2e 2e  ': ['B'],.    ..
2310: 2e 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
2320: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2330: 20 20 20 20 20 20 20 20 20 20 20 20 20 27 42 27               'B'
2340: 3a 20 5b 27 43 31 27 2c 20 27 43 32 27 5d 2c 0a  : ['C1', 'C2'],.
2350: 20 20 20 20 2e 2e 2e 20 20 20 20 20 20 20 20 20      ...         
2360: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2370: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2380: 20 20 20 27 43 31 27 3a 20 5b 27 44 31 27 5d 2c     'C1': ['D1'],
2390: 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20 20 20 20  .    ...        
23a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
23b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
23c0: 20 20 20 20 27 44 31 27 3a 20 5b 27 45 31 27 5d      'D1': ['E1']
23d0: 2c 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20 20 20  ,.    ...       
23e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
23f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2400: 20 20 20 20 20 27 45 31 27 3a 20 5b 27 44 31 27       'E1': ['D1'
2410: 5d 2c 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20 20  ],.    ...      
2420: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2430: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2440: 20 20 20 20 20 20 27 43 32 27 3a 20 5b 27 44 32        'C2': ['D2
2450: 27 5d 2c 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20  '],.    ...     
2460: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2470: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2480: 20 20 20 20 20 20 20 27 44 32 27 3a 20 5b 27 45         'D2': ['E
2490: 32 27 5d 2c 0a 20 20 20 20 2e 2e 2e 20 20 20 20  2'],.    ...    
24a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
24b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
24c0: 20 20 20 20 20 20 20 20 27 45 32 27 3a 20 5b 27          'E2': ['
24d0: 44 32 27 5d 2c 0a 20 20 20 20 2e 2e 2e 20 20 20  D2'],.    ...   
24e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
24f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2500: 20 20 20 20 20 20 20 20 20 7d 29 29 0a 20 20 20           })).   
2510: 20 3e 3e 3e 20 6c 65 6e 28 63 79 63 6c 65 73 29   >>> len(cycles)
2520: 0a 20 20 20 20 32 0a 20 20 20 20 3e 3e 3e 20 66  .    2.    >>> f
2530: 6f 72 20 63 79 63 6c 65 20 69 6e 20 63 79 63 6c  or cycle in cycl
2540: 65 73 3a 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20  es:.    ...     
2550: 63 79 63 6c 65 2e 73 6f 72 74 28 29 0a 20 20 20  cycle.sort().   
2560: 20 3e 3e 3e 20 63 79 63 6c 65 73 2e 73 6f 72 74   >>> cycles.sort
2570: 28 29 0a 20 20 20 20 3e 3e 3e 20 63 79 63 6c 65  ().    >>> cycle
2580: 31 20 3d 20 63 79 63 6c 65 73 5b 30 5d 0a 20 20  1 = cycles[0].  
2590: 20 20 3e 3e 3e 20 63 79 63 6c 65 31 2e 73 6f 72    >>> cycle1.sor
25a0: 74 28 29 0a 20 20 20 20 3e 3e 3e 20 70 72 69 6e  t().    >>> prin
25b0: 74 20 63 79 63 6c 65 31 0a 20 20 20 20 5b 27 44  t cycle1.    ['D
25c0: 31 27 2c 20 27 45 31 27 5d 0a 20 20 20 20 3e 3e  1', 'E1'].    >>
25d0: 3e 20 63 79 63 6c 65 32 20 3d 20 63 79 63 6c 65  > cycle2 = cycle
25e0: 73 5b 31 5d 0a 20 20 20 20 3e 3e 3e 20 63 79 63  s[1].    >>> cyc
25f0: 6c 65 32 2e 73 6f 72 74 28 29 0a 20 20 20 20 3e  le2.sort().    >
2600: 3e 3e 20 70 72 69 6e 74 20 63 79 63 6c 65 32 0a  >> print cycle2.
2610: 20 20 20 20 5b 27 44 32 27 2c 20 27 45 32 27 5d      ['D2', 'E2']
2620: 0a 0a 20 20 20 20 53 69 6d 70 6c 65 20 63 79 63  ..    Simple cyc
2630: 6c 65 20 77 69 74 68 20 63 68 69 6c 64 72 65 6e  le with children
2640: 20 6e 6f 74 20 73 70 65 63 69 66 69 65 64 20 66   not specified f
2650: 6f 72 20 6f 6e 65 20 69 74 65 6d 3a 0a 20 20 20  or one item:.   
2660: 20 23 20 74 6f 64 6f 3a 20 53 68 6f 75 6c 64 20   # todo: Should 
2670: 74 68 69 73 20 62 61 72 66 20 69 6e 73 74 65 61  this barf instea
2680: 64 3f 0a 20 20 20 20 3e 3e 3e 20 63 79 63 6c 65  d?.    >>> cycle
2690: 73 20 3d 20 6c 69 73 74 28 66 69 6e 64 5f 63 79  s = list(find_cy
26a0: 63 6c 65 73 28 70 61 72 65 6e 74 5f 63 68 69 6c  cles(parent_chil
26b0: 64 72 65 6e 3d 7b 27 41 27 3a 20 5b 27 42 27 5d  dren={'A': ['B']
26c0: 2c 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20 20 20  ,.    ...       
26d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
26e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
26f0: 20 20 20 20 20 27 42 27 3a 20 5b 27 41 27 5d 2c       'B': ['A'],
2700: 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20 20 20 20  .    ...        
2710: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2720: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2730: 20 20 20 20 27 43 27 3a 20 5b 27 44 27 5d 7d 29      'C': ['D']})
2740: 29 0a 20 20 20 20 3e 3e 3e 20 6c 65 6e 28 63 79  ).    >>> len(cy
2750: 63 6c 65 73 29 0a 20 20 20 20 31 0a 20 20 20 20  cles).    1.    
2760: 3e 3e 3e 20 63 79 63 6c 65 20 3d 20 63 79 63 6c  >>> cycle = cycl
2770: 65 73 5b 30 5d 0a 20 20 20 20 3e 3e 3e 20 63 79  es[0].    >>> cy
2780: 63 6c 65 2e 73 6f 72 74 28 29 0a 20 20 20 20 3e  cle.sort().    >
2790: 3e 3e 20 70 72 69 6e 74 20 63 79 63 6c 65 0a 20  >> print cycle. 
27a0: 20 20 20 5b 27 41 27 2c 20 27 42 27 5d 0a 0a 20     ['A', 'B'].. 
27b0: 20 20 20 44 69 61 6d 6f 6e 64 20 63 79 63 6c 65     Diamond cycle
27c0: 0a 20 20 20 20 3e 3e 3e 20 63 79 63 6c 65 73 20  .    >>> cycles 
27d0: 3d 20 6c 69 73 74 28 66 69 6e 64 5f 63 79 63 6c  = list(find_cycl
27e0: 65 73 28 70 61 72 65 6e 74 5f 63 68 69 6c 64 72  es(parent_childr
27f0: 65 6e 3d 7b 27 41 27 3a 20 5b 27 42 31 27 2c 20  en={'A': ['B1', 
2800: 27 42 32 27 5d 2c 0a 20 20 20 20 2e 2e 2e 20 20  'B2'],.    ...  
2810: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2820: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2830: 20 20 20 20 20 20 20 20 20 20 27 42 31 27 3a 20            'B1': 
2840: 5b 27 43 27 5d 2c 0a 20 20 20 20 2e 2e 2e 20 20  ['C'],.    ...  
2850: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2860: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2870: 20 20 20 20 20 20 20 20 20 20 27 42 32 27 3a 20            'B2': 
2880: 5b 27 43 27 5d 2c 0a 20 20 20 20 2e 2e 2e 20 20  ['C'],.    ...  
2890: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
28a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
28b0: 20 20 20 20 20 20 20 20 20 20 27 43 27 3a 20 5b            'C': [
28c0: 27 41 27 2c 20 27 42 31 27 5d 7d 29 29 0a 20 20  'A', 'B1']})).  
28d0: 20 20 3e 3e 3e 20 6c 65 6e 28 63 79 63 6c 65 73    >>> len(cycles
28e0: 29 0a 20 20 20 20 33 0a 20 20 20 20 3e 3e 3e 20  ).    3.    >>> 
28f0: 73 6f 72 74 65 64 5f 63 79 63 6c 65 73 20 3d 20  sorted_cycles = 
2900: 5b 5d 0a 20 20 20 20 3e 3e 3e 20 66 6f 72 20 63  [].    >>> for c
2910: 79 63 6c 65 20 69 6e 20 63 79 63 6c 65 73 3a 0a  ycle in cycles:.
2920: 20 20 20 20 2e 2e 2e 20 20 20 20 20 63 79 63 6c      ...     cycl
2930: 65 20 3d 20 6c 69 73 74 28 63 79 63 6c 65 29 0a  e = list(cycle).
2940: 20 20 20 20 2e 2e 2e 20 20 20 20 20 63 79 63 6c      ...     cycl
2950: 65 2e 73 6f 72 74 28 29 0a 20 20 20 20 2e 2e 2e  e.sort().    ...
2960: 20 20 20 20 20 73 6f 72 74 65 64 5f 63 79 63 6c       sorted_cycl
2970: 65 73 2e 61 70 70 65 6e 64 28 63 79 63 6c 65 29  es.append(cycle)
2980: 0a 20 20 20 20 3e 3e 3e 20 73 6f 72 74 65 64 5f  .    >>> sorted_
2990: 63 79 63 6c 65 73 2e 73 6f 72 74 28 29 0a 20 20  cycles.sort().  
29a0: 20 20 3e 3e 3e 20 66 6f 72 20 63 79 63 6c 65 20    >>> for cycle 
29b0: 69 6e 20 73 6f 72 74 65 64 5f 63 79 63 6c 65 73  in sorted_cycles
29c0: 3a 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20 70 72  :.    ...     pr
29d0: 69 6e 74 20 63 79 63 6c 65 0a 20 20 20 20 5b 27  int cycle.    ['
29e0: 41 27 2c 20 27 42 31 27 2c 20 27 43 27 5d 0a 20  A', 'B1', 'C']. 
29f0: 20 20 20 5b 27 41 27 2c 20 27 42 32 27 2c 20 27     ['A', 'B2', '
2a00: 43 27 5d 0a 20 20 20 20 5b 27 42 31 27 2c 20 27  C'].    ['B1', '
2a10: 43 27 5d 0a 0a 20 20 20 20 48 61 69 72 79 20 63  C']..    Hairy c
2a20: 61 73 65 20 28 6f 72 64 65 72 20 63 61 6e 20 6d  ase (order can m
2a30: 61 74 74 65 72 20 69 66 20 73 6f 6d 65 74 68 69  atter if somethi
2a40: 6e 67 20 69 73 20 77 72 6f 6e 67 29 3a 0a 20 20  ng is wrong):.  
2a50: 20 20 28 4e 6f 74 65 20 6f 72 64 65 72 20 6f 66    (Note order of
2a60: 20 42 20 61 6e 64 20 43 20 69 6e 20 74 68 65 20   B and C in the 
2a70: 6c 69 73 74 2e 29 0a 20 20 20 20 3e 3e 3e 20 63  list.).    >>> c
2a80: 79 63 6c 65 73 20 3d 20 6c 69 73 74 28 66 69 6e  ycles = list(fin
2a90: 64 5f 63 79 63 6c 65 73 28 70 61 72 65 6e 74 5f  d_cycles(parent_
2aa0: 63 68 69 6c 64 72 65 6e 3d 7b 0a 20 20 20 20 2e  children={.    .
2ab0: 2e 2e 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ..              
2ac0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2ad0: 20 20 20 20 20 20 20 20 20 20 20 20 20 27 54 44               'TD
2ae0: 27 3a 20 5b 27 44 44 27 5d 2c 0a 20 20 20 20 2e  ': ['DD'],.    .
2af0: 2e 2e 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ..              
2b00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2b10: 20 20 20 20 20 20 20 20 20 20 20 20 20 27 54 43               'TC
2b20: 27 3a 20 5b 27 44 43 27 5d 2c 0a 20 20 20 20 2e  ': ['DC'],.    .
2b30: 2e 2e 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ..              
2b40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2b50: 20 20 20 20 20 20 20 20 20 20 20 20 20 27 44 43               'DC
2b60: 27 3a 20 5b 27 44 51 27 5d 2c 0a 20 20 20 20 2e  ': ['DQ'],.    .
2b70: 2e 2e 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ..              
2b80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2b90: 20 20 20 20 20 20 20 20 20 20 20 20 20 27 43 27               'C'
2ba0: 3a 20 5b 27 44 51 27 5d 2c 0a 20 20 20 20 2e 2e  : ['DQ'],.    ..
2bb0: 2e 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
2bc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2bd0: 20 20 20 20 20 20 20 20 20 20 20 20 27 44 51 27              'DQ'
2be0: 3a 20 5b 27 49 41 27 2c 20 27 54 4f 27 5d 2c 0a  : ['IA', 'TO'],.
2bf0: 20 20 20 20 2e 2e 2e 20 20 20 20 20 20 20 20 20      ...         
2c00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2c10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2c20: 20 20 27 49 41 27 3a 20 5b 27 41 27 5d 2c 0a 20    'IA': ['A'],. 
2c30: 20 20 20 2e 2e 2e 20 20 20 20 20 20 20 20 20 20     ...          
2c40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2c50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2c60: 20 27 41 27 3a 20 5b 27 42 27 2c 20 27 43 27 5d   'A': ['B', 'C']
2c70: 2c 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20 20 20  ,.    ...       
2c80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2c90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2ca0: 20 20 20 20 7d 29 29 0a 20 20 20 20 3e 3e 3e 20      })).    >>> 
2cb0: 6c 65 6e 28 63 79 63 6c 65 73 29 0a 20 20 20 20  len(cycles).    
2cc0: 31 0a 20 20 20 20 3e 3e 3e 20 63 79 63 6c 65 20  1.    >>> cycle 
2cd0: 3d 20 63 79 63 6c 65 73 5b 30 5d 0a 20 20 20 20  = cycles[0].    
2ce0: 3e 3e 3e 20 63 79 63 6c 65 2e 73 6f 72 74 28 29  >>> cycle.sort()
2cf0: 0a 20 20 20 20 3e 3e 3e 20 70 72 69 6e 74 20 63  .    >>> print c
2d00: 79 63 6c 65 0a 20 20 20 20 5b 27 41 27 2c 20 27  ycle.    ['A', '
2d10: 43 27 2c 20 27 44 51 27 2c 20 27 49 41 27 5d 0a  C', 'DQ', 'IA'].
2d20: 0a 20 20 20 20 22 22 22 0a 20 20 20 20 63 79 63  .    """.    cyc
2d30: 6c 65 73 20 3d 20 5b 5d 0a 20 20 20 20 76 69 73  les = [].    vis
2d40: 69 74 65 64 5f 6e 6f 64 65 73 20 3d 20 73 65 74  ited_nodes = set
2d50: 28 29 0a 0a 20 20 20 20 66 6f 72 20 70 61 72 65  ()..    for pare
2d60: 6e 74 20 69 6e 20 70 61 72 65 6e 74 5f 63 68 69  nt in parent_chi
2d70: 6c 64 72 65 6e 3a 0a 20 20 20 20 20 20 20 20 69  ldren:.        i
2d80: 66 20 70 61 72 65 6e 74 20 69 6e 20 76 69 73 69  f parent in visi
2d90: 74 65 64 5f 6e 6f 64 65 73 3a 0a 20 20 20 20 20  ted_nodes:.     
2da0: 20 20 20 20 20 20 20 23 20 54 68 69 73 20 6e 6f         # This no
2db0: 64 65 20 69 73 20 70 61 72 74 20 6f 66 20 61 20  de is part of a 
2dc0: 70 61 74 68 20 74 68 61 74 20 68 61 73 20 61 6c  path that has al
2dd0: 72 65 61 64 79 20 62 65 65 6e 20 74 72 61 76 65  ready been trave
2de0: 72 73 65 64 2e 0a 20 20 20 20 20 20 20 20 20 20  rsed..          
2df0: 20 20 63 6f 6e 74 69 6e 75 65 0a 0a 20 20 20 20    continue..    
2e00: 20 20 20 20 70 61 74 68 73 20 3d 20 5b 5b 70 61      paths = [[pa
2e10: 72 65 6e 74 5d 5d 0a 20 20 20 20 20 20 20 20 77  rent]].        w
2e20: 68 69 6c 65 20 70 61 74 68 73 3a 0a 20 20 20 20  hile paths:.    
2e30: 20 20 20 20 20 20 20 20 70 61 74 68 20 3d 20 70          path = p
2e40: 61 74 68 73 2e 70 6f 70 28 29 0a 0a 20 20 20 20  aths.pop()..    
2e50: 20 20 20 20 20 20 20 20 70 61 72 65 6e 74 20 3d          parent =
2e60: 20 70 61 74 68 5b 2d 31 5d 0a 20 20 20 20 20 20   path[-1].      
2e70: 20 20 20 20 20 20 0a 20 20 20 20 20 20 20 20 20        .         
2e80: 20 20 20 74 72 79 3a 0a 20 20 20 20 20 20 20 20     try:.        
2e90: 20 20 20 20 20 20 20 20 63 68 69 6c 64 72 65 6e          children
2ea0: 20 3d 20 70 61 72 65 6e 74 5f 63 68 69 6c 64 72   = parent_childr
2eb0: 65 6e 5b 70 61 72 65 6e 74 5d 0a 20 20 20 20 20  en[parent].     
2ec0: 20 20 20 20 20 20 20 65 78 63 65 70 74 20 4b 65         except Ke
2ed0: 79 45 72 72 6f 72 3a 0a 20 20 20 20 20 20 20 20  yError:.        
2ee0: 20 20 20 20 20 20 20 20 63 6f 6e 74 69 6e 75 65          continue
2ef0: 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20 66 6f  ..            fo
2f00: 72 20 63 68 69 6c 64 20 69 6e 20 63 68 69 6c 64  r child in child
2f10: 72 65 6e 3a 0a 20 20 20 20 20 20 20 20 20 20 20  ren:.           
2f20: 20 20 20 20 20 23 20 4b 65 65 70 69 6e 67 20 61       # Keeping a
2f30: 20 73 65 74 20 6f 66 20 74 68 65 20 70 61 74 68   set of the path
2f40: 20 6e 6f 64 65 73 2c 20 66 6f 72 20 4f 28 31 29   nodes, for O(1)
2f50: 20 6c 6f 6f 6b 75 70 73 20 61 74 20 74 68 65 0a   lookups at the.
2f60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2f70: 23 20 65 78 70 65 6e 73 65 20 6f 66 20 6d 6f 72  # expense of mor
2f80: 65 20 6d 65 6d 6f 72 79 20 61 6e 64 20 63 6f 6d  e memory and com
2f90: 70 6c 65 78 69 74 79 2c 20 61 63 74 75 61 6c 6c  plexity, actuall
2fa0: 79 20 6d 61 6b 65 73 20 73 70 65 65 64 0a 20 20  y makes speed.  
2fb0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 23 20                # 
2fc0: 77 6f 72 73 65 2e 20 28 44 75 65 20 74 6f 20 63  worse. (Due to c
2fd0: 6f 6e 73 74 72 75 63 74 69 6f 6e 20 6f 66 20 73  onstruction of s
2fe0: 65 74 73 2e 29 0a 20 20 20 20 20 20 20 20 20 20  ets.).          
2ff0: 20 20 20 20 20 20 23 20 54 68 69 73 20 69 73 20        # This is 
3000: 4f 28 4e 29 2e 0a 20 20 20 20 20 20 20 20 20 20  O(N)..          
3010: 20 20 20 20 20 20 69 66 20 63 68 69 6c 64 20 69        if child i
3020: 6e 20 70 61 74 68 3a 0a 20 20 20 20 20 20 20 20  n path:.        
3030: 20 20 20 20 20 20 20 20 20 20 20 20 23 20 54 68              # Th
3040: 69 73 20 69 73 20 61 20 63 79 63 6c 65 2e 0a 20  is is a cycle.. 
3050: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3060: 20 20 20 63 79 63 6c 65 20 3d 20 70 61 74 68 5b     cycle = path[
3070: 70 61 74 68 2e 69 6e 64 65 78 28 63 68 69 6c 64  path.index(child
3080: 29 3a 5d 0a 20 20 20 20 20 20 20 20 20 20 20 20  ):].            
3090: 20 20 20 20 20 20 20 20 23 20 43 68 65 63 6b 20          # Check 
30a0: 74 68 61 74 20 74 68 69 73 20 69 73 20 6e 6f 74  that this is not
30b0: 20 61 20 64 75 70 20 63 79 63 6c 65 2e 0a 20 20   a dup cycle..  
30c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
30d0: 20 20 69 73 5f 64 75 70 20 3d 20 46 61 6c 73 65    is_dup = False
30e0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
30f0: 20 20 20 20 20 66 6f 72 20 6f 74 68 65 72 5f 63       for other_c
3100: 79 63 6c 65 20 69 6e 20 63 79 63 6c 65 73 3a 0a  ycle in cycles:.
3110: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3120: 20 20 20 20 20 20 20 20 69 66 20 69 73 5f 72 6f          if is_ro
3130: 74 61 74 65 64 28 6f 74 68 65 72 5f 63 79 63 6c  tated(other_cycl
3140: 65 2c 20 63 79 63 6c 65 29 3a 0a 20 20 20 20 20  e, cycle):.     
3150: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3160: 20 20 20 20 20 20 20 69 73 5f 64 75 70 20 3d 20         is_dup = 
3170: 54 72 75 65 0a 20 20 20 20 20 20 20 20 20 20 20  True.           
3180: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3190: 20 62 72 65 61 6b 0a 20 20 20 20 20 20 20 20 20   break.         
31a0: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 6e 6f             if no
31b0: 74 20 69 73 5f 64 75 70 3a 0a 20 20 20 20 20 20  t is_dup:.      
31c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
31d0: 20 20 63 79 63 6c 65 73 2e 61 70 70 65 6e 64 28    cycles.append(
31e0: 63 79 63 6c 65 29 0a 20 20 20 20 20 20 20 20 20  cycle).         
31f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 79                 y
3200: 69 65 6c 64 20 63 79 63 6c 65 0a 20 20 20 20 20  ield cycle.     
3210: 20 20 20 20 20 20 20 20 20 20 20 65 6c 73 65 3a             else:
3220: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
3230: 20 20 20 20 20 23 20 50 75 73 68 20 74 68 69 73       # Push this
3240: 20 6e 65 77 20 70 61 74 68 20 6f 6e 74 6f 20 74   new path onto t
3250: 68 65 20 27 73 74 61 63 6b 27 2e 0a 20 20 20 20  he 'stack'..    
3260: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3270: 23 20 54 68 69 73 20 69 73 20 70 72 6f 62 61 62  # This is probab
3280: 6c 79 20 74 68 65 20 6d 6f 73 74 20 65 78 70 65  ly the most expe
3290: 6e 73 69 76 65 20 70 61 72 74 20 6f 66 20 74 68  nsive part of th
32a0: 65 20 61 6c 67 6f 72 69 74 68 6d 0a 20 20 20 20  e algorithm.    
32b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
32c0: 23 20 28 61 20 6c 69 73 74 20 63 6f 70 79 29 2e  # (a list copy).
32d0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
32e0: 20 20 20 20 20 70 61 74 68 73 2e 61 70 70 65 6e       paths.appen
32f0: 64 28 70 61 74 68 20 2b 20 5b 63 68 69 6c 64 5d  d(path + [child]
3300: 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ).              
3310: 20 20 20 20 20 20 23 20 4d 61 72 6b 20 74 68 65        # Mark the
3320: 20 6e 6f 64 65 20 61 73 20 76 69 73 69 74 65 64   node as visited
3330: 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ..              
3340: 20 20 20 20 20 20 76 69 73 69 74 65 64 5f 6e 6f        visited_no
3350: 64 65 73 2e 61 64 64 28 63 68 69 6c 64 29 0a 0a  des.add(child)..
3360: 0a 69 66 20 5f 5f 6e 61 6d 65 5f 5f 20 3d 3d 20  .if __name__ == 
3370: 27 5f 5f 6d 61 69 6e 5f 5f 27 3a 0a 20 20 20 20  '__main__':.    
3380: 23 20 52 75 6e 20 74 68 65 20 64 6f 63 74 65 73  # Run the doctes
3390: 74 20 74 65 73 74 73 2e 0a 20 20 20 20 69 6d 70  t tests..    imp
33a0: 6f 72 74 20 73 79 73 0a 20 20 20 20 69 6d 70 6f  ort sys.    impo
33b0: 72 74 20 64 6f 63 74 65 73 74 0a 20 20 20 20 64  rt doctest.    d
33c0: 6f 63 74 65 73 74 2e 74 65 73 74 6d 6f 64 28 73  octest.testmod(s
33d0: 79 73 2e 6d 6f 64 75 6c 65 73 5b 27 5f 5f 6d 61  ys.modules['__ma
33e0: 69 6e 5f 5f 27 5d 29 0a                          in__']).