图形分析:识别循环路径
Graph analysis: Identify loop paths
我有一个无向图,如:
import igraph as ig
G = ig.Graph()
G.add_vertices(9)
G.add_edges([(0,1), (1,2),(2,3),(3,0),(0,4),(4,5),(5,6),(6,7),(6,8)])
有一个 "loop path" 从节点 0 通过 1,2,3 回到 0(抱歉,在图片中节点标签以 1 而不是 0 开头)
对于赋值,我需要确定 "loop path" 连接到图的其余部分的节点,即 0
,最重要的是 "loop path" 本身,即 [0,1,2,3,0]
and/or [0,3,2,1,0]
我很努力,但真的没有头绪。如果我使用 中的函数,比如 find_all_paths(G,0,0)
我当然只会得到 [0]
由于题目也打了networkx的标签,所以我用它来举例说明代码。
在图论中"loop paths"通常被称为循环。
我看到的最简单(可能不是最快)的想法是找到循环和一组关节点(或切割顶点,即增加连接组件数量的点),然后它们的交集就是解决方案.
以同样的方式开始:
import networkx as nx
G.add_nodes_from([9])
G.add_edges_from([(0,1), (1,2),(2,3),(3,0),(0,4),(4,5),(5,6),(6,7),(6,8)])
现在问题的解决方案:
cycles = nx.cycle_basis(G) # list of cycles
cuts = list(nx.articulation_points(G)) # list of cut verteces
nodes_needed = set() # the set of nodes we are looking for
for cycle in cycles:
for node in cycle:
if node in cuts:
nodes_needed.add(node)
这是一个使用广度优先搜索查找循环的示例。我想知道是否存在更有效的方法。即使是中等大小的图形,或更长的最大循环长度,这可能 运行 年龄。深度优先搜索也可以这样做。首先,我相信您使用 R
发布了问题,因此在下面也可以找到 R
版本。出于同样的原因,python
版本并不完全符合 pythonic,正如我从 R
快速翻译过来的一样。
解释见代码中的注释。
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']
在R
中相同:
require(igraph)
# creating a toy graph
g <- erdos.renyi.game(n = 100, p.or.m = 0.04)
# breadth first search of paths and unique loops
get_loops <- function(adj, paths, maxlen){
# tracking the actual path length:
maxlen <- maxlen - 1
nxt_paths <- list()
# iterating over all paths:
for(path in paths$paths){
# iterating neighbors of the last vertex in the path:
for(nxt in adj[[path[length(path)]]]){
# attaching the next vertex to the path:
nxt_path <- c(path, nxt)
if(path[1] == nxt & 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 <- c(paths$loops, list(nxt_path))
# if you don't need the starting vertex included
# at the end:
# paths$loops <- c(paths$loops, list(path))
}else if(!(nxt %in% path)){
# keep the path only if we don't create
# an internal loop in the path
nxt_paths <- c(nxt_paths, list(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 <- list()
loops <- list()
# 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(v in V(g)){
# for directed graphs use the 'mode' argument of neighbors()
# according to your needs ('in', 'out' or 'all')
adj[[as.numeric(v)]] <- neighbors(g, v)
}
# recursive search of loops
# for each vertex as candidate starting point
for(start in seq(length(adj))){
loops <- c(loops, get_loops(adj, list(paths = list(c(start)),
loops = list()), maxlen)$loops)
}
好的,这是对我自己的问题的回答的一部分:
感谢 Max Li's and deeenes' help, ihad the idea to rewrite the networkx cycle_basis function 在 python_igraph 工作:
import igraph as ig
G = ig.Graph()
G.add_vertices(9)
G.add_edges([(0,1), (1,2),(2,3),(3,0),(0,4),(4,5),(5,6),(6,7),(6,8)])
def cycle_basis_ig(G,root=None):
gnodes=set(n.index for n in G.vs())
cycles=[]
while gnodes: # loop over connected components
if root is None:
root=gnodes.pop()
stack=[root]
pred={root:root}
used={root:set()}
while stack: # walk the spanning tree finding cycles
z=stack.pop() # use last-in so cycles easier to find
zused=used[z]
for nbr in G.neighbors(z,mode='ALL'):
if nbr not in used: # new node
pred[nbr]=z
stack.append(nbr)
used[nbr]=set([z])
elif nbr is z: # self loops
cycles.append([z])
elif nbr not in zused:# found a cycle
pn=used[nbr]
cycle=[nbr,z]
p=pred[z]
while p not in pn:
cycle.append(p)
p=pred[p]
cycle.append(p)
cycles.append(cycle)
used[nbr].add(z)
gnodes-=set(pred)
root=None
return cycles
cb = cycle_basis_ig(G)
print 'cycle_basis_ig: ', cb
对于大图和有向图@deenes 的回答是正确的,python版本
是O.K.,但是R版本有复制列表次数和次数的瓶颈
同样,我通过以下方式修改它来解决性能问题:
# breadth first search of paths and unique loops
get_loops <- function(adj, paths, maxlen) {
# tracking the actual path length:
maxlen <- maxlen - 1
nxt_paths <- list()
# count of loops and paths in the next step, avoid copying lists that cause performance bottleneck.
if (is.null(paths$lc))
paths$lc <- 0
paths$pc <- 0
# iterating over all paths:
for (path in paths$paths) {
# iterating neighbors of the last vertex in the path:
for (nxt in adj[[path[length(path)]]]) {
# attaching the next vertex to the path:
nxt_path <- c(path, nxt)
if (path[1] == nxt & 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$lc <- paths$lc + 1
paths$loops[paths$lc] <- list(nxt_path)
# if you don't need the starting vertex included
# at the end:
# paths$loops <- c(paths$loops, list(path))
# cat(paste(paths$loops,collapse=","));cat("\n")
} else if (!(nxt %in% path)) {
# keep the path only if we don't create
# an internal loop in the path
paths$pc <- paths$pc + 1
nxt_paths[paths$pc] <- list(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))
}
}
我有一个无向图,如:
import igraph as ig
G = ig.Graph()
G.add_vertices(9)
G.add_edges([(0,1), (1,2),(2,3),(3,0),(0,4),(4,5),(5,6),(6,7),(6,8)])
有一个 "loop path" 从节点 0 通过 1,2,3 回到 0(抱歉,在图片中节点标签以 1 而不是 0 开头)
对于赋值,我需要确定 "loop path" 连接到图的其余部分的节点,即 0
,最重要的是 "loop path" 本身,即 [0,1,2,3,0]
and/or [0,3,2,1,0]
我很努力,但真的没有头绪。如果我使用 find_all_paths(G,0,0)
我当然只会得到 [0]
由于题目也打了networkx的标签,所以我用它来举例说明代码。
在图论中"loop paths"通常被称为循环。
我看到的最简单(可能不是最快)的想法是找到循环和一组关节点(或切割顶点,即增加连接组件数量的点),然后它们的交集就是解决方案.
以同样的方式开始:
import networkx as nx
G.add_nodes_from([9])
G.add_edges_from([(0,1), (1,2),(2,3),(3,0),(0,4),(4,5),(5,6),(6,7),(6,8)])
现在问题的解决方案:
cycles = nx.cycle_basis(G) # list of cycles
cuts = list(nx.articulation_points(G)) # list of cut verteces
nodes_needed = set() # the set of nodes we are looking for
for cycle in cycles:
for node in cycle:
if node in cuts:
nodes_needed.add(node)
这是一个使用广度优先搜索查找循环的示例。我想知道是否存在更有效的方法。即使是中等大小的图形,或更长的最大循环长度,这可能 运行 年龄。深度优先搜索也可以这样做。首先,我相信您使用 R
发布了问题,因此在下面也可以找到 R
版本。出于同样的原因,python
版本并不完全符合 pythonic,正如我从 R
快速翻译过来的一样。
解释见代码中的注释。
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']
在R
中相同:
require(igraph)
# creating a toy graph
g <- erdos.renyi.game(n = 100, p.or.m = 0.04)
# breadth first search of paths and unique loops
get_loops <- function(adj, paths, maxlen){
# tracking the actual path length:
maxlen <- maxlen - 1
nxt_paths <- list()
# iterating over all paths:
for(path in paths$paths){
# iterating neighbors of the last vertex in the path:
for(nxt in adj[[path[length(path)]]]){
# attaching the next vertex to the path:
nxt_path <- c(path, nxt)
if(path[1] == nxt & 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 <- c(paths$loops, list(nxt_path))
# if you don't need the starting vertex included
# at the end:
# paths$loops <- c(paths$loops, list(path))
}else if(!(nxt %in% path)){
# keep the path only if we don't create
# an internal loop in the path
nxt_paths <- c(nxt_paths, list(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 <- list()
loops <- list()
# 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(v in V(g)){
# for directed graphs use the 'mode' argument of neighbors()
# according to your needs ('in', 'out' or 'all')
adj[[as.numeric(v)]] <- neighbors(g, v)
}
# recursive search of loops
# for each vertex as candidate starting point
for(start in seq(length(adj))){
loops <- c(loops, get_loops(adj, list(paths = list(c(start)),
loops = list()), maxlen)$loops)
}
好的,这是对我自己的问题的回答的一部分:
感谢 Max Li's and deeenes' help, ihad the idea to rewrite the networkx cycle_basis function 在 python_igraph 工作:
import igraph as ig
G = ig.Graph()
G.add_vertices(9)
G.add_edges([(0,1), (1,2),(2,3),(3,0),(0,4),(4,5),(5,6),(6,7),(6,8)])
def cycle_basis_ig(G,root=None):
gnodes=set(n.index for n in G.vs())
cycles=[]
while gnodes: # loop over connected components
if root is None:
root=gnodes.pop()
stack=[root]
pred={root:root}
used={root:set()}
while stack: # walk the spanning tree finding cycles
z=stack.pop() # use last-in so cycles easier to find
zused=used[z]
for nbr in G.neighbors(z,mode='ALL'):
if nbr not in used: # new node
pred[nbr]=z
stack.append(nbr)
used[nbr]=set([z])
elif nbr is z: # self loops
cycles.append([z])
elif nbr not in zused:# found a cycle
pn=used[nbr]
cycle=[nbr,z]
p=pred[z]
while p not in pn:
cycle.append(p)
p=pred[p]
cycle.append(p)
cycles.append(cycle)
used[nbr].add(z)
gnodes-=set(pred)
root=None
return cycles
cb = cycle_basis_ig(G)
print 'cycle_basis_ig: ', cb
对于大图和有向图@deenes 的回答是正确的,python版本 是O.K.,但是R版本有复制列表次数和次数的瓶颈 同样,我通过以下方式修改它来解决性能问题:
# breadth first search of paths and unique loops
get_loops <- function(adj, paths, maxlen) {
# tracking the actual path length:
maxlen <- maxlen - 1
nxt_paths <- list()
# count of loops and paths in the next step, avoid copying lists that cause performance bottleneck.
if (is.null(paths$lc))
paths$lc <- 0
paths$pc <- 0
# iterating over all paths:
for (path in paths$paths) {
# iterating neighbors of the last vertex in the path:
for (nxt in adj[[path[length(path)]]]) {
# attaching the next vertex to the path:
nxt_path <- c(path, nxt)
if (path[1] == nxt & 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$lc <- paths$lc + 1
paths$loops[paths$lc] <- list(nxt_path)
# if you don't need the starting vertex included
# at the end:
# paths$loops <- c(paths$loops, list(path))
# cat(paste(paths$loops,collapse=","));cat("\n")
} else if (!(nxt %in% path)) {
# keep the path only if we don't create
# an internal loop in the path
paths$pc <- paths$pc + 1
nxt_paths[paths$pc] <- list(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))
}
}