将社区结构(列表)转换为邻接表
Convert community structure (list) to adjacency list
给定社区结构(列表列表):
[[A,B,C], [B,D,E,G], [A,C,F,H],[F,K, H]]
并假设每条边的权重为 1,在子组内是无向的。
我想通过对每个人应用广度/深度优先搜索来找到最有影响力的人,他与 G、F(边的最小和)有最短的联系。
广度优先搜索的通用代码如下:
def bfs_paths(graph, start, goal):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
queue.append((next, path + [next]))
问题是 'graph' 应该表示为邻接表。例如:
graph = {'A': set(['B', 'C', 'F', 'H']),
'B': set(['D', 'E','G']),
'C': set(['A', 'F', 'H']),
'D': set(['B', 'E', 'G' ]),
'E': set(['B', 'D', 'G' ]),
'F': set(['K', 'H']),
'G': set(['B', 'D', 'E'])
'H': set(['K', 'F']}
主要问题:如何将社区结构(列表)转换为邻接表?
附带问题:还有其他合适的算法吗?
Edit1:我试过按照这个 。但我坚持改进代码以满足预期结果
这样可能会得到想要的结果
A1=[['A','B','C'], ['B','D','E','G'], ['A','C','F','H'],['F','K', 'H']]
dict1={}
for l in A1:
for i in l:
dict1[i]=[]
for i in dict1:
index=100
for j in A1:
try:
if j.index(i)<index:
index=j.index(i)
dict1[i]=[]
for k in j:
if k!=i:
dict1[i].append(k)
except:
pass
假设所有社区都完全连接,您可以通过迭代组并使用 setdefault
在需要的地方创建新条目并添加节点来相当快速地转换为邻接列表:
community = [['A','B','C'], ['B','D','E','G'], ['A','C','F','H'],['F','K','H']]
adj_list = {}
for group in community:
for member in group:
adj_list.setdefault(member, set()).update((set(group) - {member}))
adj_list
将是:
{'A': {'B', 'C', 'F', 'H'},
'B': {'A', 'C', 'D', 'E', 'G'},
'C': {'A', 'B', 'F', 'H'},
'D': {'B', 'E', 'G'},
'E': {'B', 'D', 'G'},
'G': {'B', 'D', 'E'},
'F': {'A', 'C', 'H', 'K'},
'H': {'A', 'C', 'F', 'K'},
'K': {'F', 'H'}}
另一种方法是使用 defaultdict(set)
,然后您只需对其进行索引并以类似方式进行更新即可。
给定社区结构(列表列表):
[[A,B,C], [B,D,E,G], [A,C,F,H],[F,K, H]]
并假设每条边的权重为 1,在子组内是无向的。
我想通过对每个人应用广度/深度优先搜索来找到最有影响力的人,他与 G、F(边的最小和)有最短的联系。
广度优先搜索的通用代码如下:
def bfs_paths(graph, start, goal):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
queue.append((next, path + [next]))
问题是 'graph' 应该表示为邻接表。例如:
graph = {'A': set(['B', 'C', 'F', 'H']),
'B': set(['D', 'E','G']),
'C': set(['A', 'F', 'H']),
'D': set(['B', 'E', 'G' ]),
'E': set(['B', 'D', 'G' ]),
'F': set(['K', 'H']),
'G': set(['B', 'D', 'E'])
'H': set(['K', 'F']}
主要问题:如何将社区结构(列表)转换为邻接表?
附带问题:还有其他合适的算法吗?
Edit1:我试过按照这个
这样可能会得到想要的结果
A1=[['A','B','C'], ['B','D','E','G'], ['A','C','F','H'],['F','K', 'H']]
dict1={}
for l in A1:
for i in l:
dict1[i]=[]
for i in dict1:
index=100
for j in A1:
try:
if j.index(i)<index:
index=j.index(i)
dict1[i]=[]
for k in j:
if k!=i:
dict1[i].append(k)
except:
pass
假设所有社区都完全连接,您可以通过迭代组并使用 setdefault
在需要的地方创建新条目并添加节点来相当快速地转换为邻接列表:
community = [['A','B','C'], ['B','D','E','G'], ['A','C','F','H'],['F','K','H']]
adj_list = {}
for group in community:
for member in group:
adj_list.setdefault(member, set()).update((set(group) - {member}))
adj_list
将是:
{'A': {'B', 'C', 'F', 'H'},
'B': {'A', 'C', 'D', 'E', 'G'},
'C': {'A', 'B', 'F', 'H'},
'D': {'B', 'E', 'G'},
'E': {'B', 'D', 'G'},
'G': {'B', 'D', 'E'},
'F': {'A', 'C', 'H', 'K'},
'H': {'A', 'C', 'F', 'K'},
'K': {'F', 'H'}}
另一种方法是使用 defaultdict(set)
,然后您只需对其进行索引并以类似方式进行更新即可。