<p>下面是一个使用广度优先搜索查找循环的示例。我想知道是否有更有效的方法。即使是中等大的图,或者更长的最大循环长度,这可能会运行很长时间。深度优先搜索也可以做到这一点。首先,我相信您是用<code>R</code>发布了这个问题,所以请在下面找到<code>R</code>版本。由于同样的原因,<code>python</code>版本并不是完全的python,正如我快速从<code>R</code>翻译过来的那样。
有关解释,请参见代码中的注释。在</p>
<pre><code>import igraph
# creating a toy graph
g = igraph.Graph.Erdos_Renyi(n = 100, p = 0.04)
# breadth first search of paths and unique loops
def get_loops(adj, paths, maxlen):
# tracking the actual path length:
maxlen -= 1
nxt_paths = []
# iterating over all paths:
for path in paths['paths']:
# iterating neighbors of the last vertex in the path:
for nxt in adj[path[-1]]:
# attaching the next vertex to the path:
nxt_path = path + [nxt]
if path[0] == nxt and min(path) == nxt:
# the next vertex is the starting vertex, we found a loop
# we keep the loop only if the starting vertex has the
# lowest vertex id, to avoid having the same loops
# more than once
paths['loops'].append(nxt_path)
# if you don't need the starting vertex
# included at the end:
# paths$loops <- c(paths$loops, list(path))
elif nxt not in path:
# keep the path only if we don't create
# an internal loop in the path
nxt_paths.append(nxt_path)
# paths grown by one step:
paths['paths'] = nxt_paths
if maxlen == 0:
# the final return when maximum search length reached
return paths
else:
# recursive return, to grow paths further
return get_loops(adj, paths, maxlen)
adj = []
loops = []
# the maximum length to limit computation time on large graphs
# maximum could be vcount(graph), but that might take for ages
maxlen = 4
# creating an adjacency list
# for directed graphs use the 'mode' argument of neighbors()
# according to your needs ('in', 'out' or 'all')
adj = [[n.index for n in v.neighbors()] for v in g.vs]
# recursive search of loops
# for each vertex as candidate starting point
for start in xrange(g.vcount()):
loops += get_loops(adj,
{'paths': [[start]], 'loops': []}, maxlen)['loops']
</code></pre>
<p>在<code>R</code>中相同:</p>
^{pr2}$