ジョンソンのアルゴリズムを変更してすべてのグラフサイクルをテキストファイルに出力する方法

Question

Johnsonxのアルゴリズムのnetworkxの実装（https://networkx.github.io/documentation/networkx-1.10/_modules/networkx/algorithms/cycles.html#simple_cycles）を変更して、グラフ内のすべての基本サイクルを見つけ出し、ファイル。私は大きなグラフを使用し、私はサイクルを保存するリストが巨大なので、私はメモリエラーを取得するため、この変更を行いたいです。

def simple_cycles(G): 

    def _unblock(thisnode,blocked,B): 
     stack=set([thisnode]) 
     while stack: 
      node=stack.pop() 
      if node in blocked: 
       blocked.remove(node) 
       stack.update(B[node]) 
       B[node].clear() 

    # Johnson's algorithm requires some ordering of the nodes. 
    # We assign the arbitrary ordering given by the strongly connected comps 
    # There is no need to track the ordering as each node removed as processed. 
    subG = type(G)(G.edges_iter()) # save the actual graph so we can mutate it here 
           # We only take the edges because we do not want to 
           # copy edge and node attributes here. 
    sccs = list(nx.strongly_connected_components(subG)) 
    while sccs: 
     scc=sccs.pop() 
     # order of scc determines ordering of nodes 
     startnode = scc.pop() 
     # Processing node runs "circuit" routine from recursive version 
     path=[startnode] 
     blocked = set() # vertex: blocked from search? 
     closed = set() # nodes involved in a cycle 
     blocked.add(startnode) 
     B=defaultdict(set) # graph portions that yield no elementary circuit 
     stack=[ (startnode,list(subG[startnode])) ] # subG gives component nbrs 
     while stack: 
      thisnode,nbrs = stack[-1] 
      if nbrs: 
       nextnode = nbrs.pop() 
#     print thisnode,nbrs,":",nextnode,blocked,B,path,stack,startnode 
#     f=raw_input("pause") 
       if nextnode == startnode: 
        yield path[:] 
        closed.update(path) 
#      print "Found a cycle",path,closed 
       elif nextnode not in blocked: 
        path.append(nextnode) 
        stack.append((nextnode,list(subG[nextnode]))) 
        closed.discard(nextnode) 
        blocked.add(nextnode) 
        continue 
      # done with nextnode... look for more neighbors 
      if not nbrs: # no more nbrs 
       if thisnode in closed: 
        _unblock(thisnode,blocked,B) 
       else: 
        for nbr in subG[thisnode]: 
         if thisnode not in B[nbr]: 
          B[nbr].add(thisnode) 
       stack.pop() 
#    assert path[-1]==thisnode 
       path.pop() 
     # done processing this node 
     subG.remove_node(startnode) 
     H=subG.subgraph(scc) # make smaller to avoid work in SCC routine 
     sccs.extend(list(nx.strongly_connected_components(H))) 

もちろん、私は上記の実装とは異なるが類似した時間に実行される提案も受け入れます。また、私のプロジェクトでnetworkxを使用しているので、そのライブラリの他の関数を自由に使用してください。

Answer 1

networkx.simple_cycles（）関数はすでにジェネレータです。サイクルを繰り返すだけで、このようなファイルに印刷できます。

In [1]: import networkx as nx 

In [2]: G = nx.cycle_graph(5).to_directed() 

In [3]: with open('foo','w') as f: 
    ...:  for c in nx.simple_cycles(G): 
    ...:   print(c, file=f) 
    ...:   

In [4]: cat foo 
[0, 4] 
[0, 4, 3, 2, 1] 
[0, 1, 2, 3, 4] 
[0, 1] 
[1, 2] 
[2, 3] 
[3, 4]