如何使用 2D np 数组作为输入创建 networkx 图形
How to create a networkx Graph using 2D np array as input
我的算法输出描述 3D 对象的顶点集 space (x, y, z)。在这种情况下，有两个对象：
verts =
[[0.1 1. 1. ] [1. 1. 0.1] [1. 0.1 1. ] [1. 1. 1.9] [1. 1.9 1. ]
[1.9 1. 1. ] [7.1 8. 8. ] [8. 8. 7.1] [8. 7.1 8. ] [8. 8. 8.9]
[8. 8.9 8. ] [8.9 8. 8. ]]
有两个四面体，一个以 (1, 1, 1) 为中心，另一个以 (8, 8, 8) 为中心。我的目标是使用广度优先搜索来识别对象是分开的，然后 classify 每个。我无法为我的算法获取正确形式的数据。
相反，我打算使用 networkx 模块，特别是使用 Graph class，它将 ndarrays 作为输入。我试过：
import networkx as nx
import numpy as np
graph = Graph(verts)
for idx, graph in enumerate(nx.connected_components(graph)):
print("Graph ",idx, " in ", graph,'\n\n',file=open("output.txt","a"))
但是，我无法创建图表。相反，我收到错误：
"Input is not a correct numpy matrix or array.")
networkx.exception.NetworkXError: Input is not a correct numpy matrix or array.
这让我很困惑，因为顶点类型 = numpy.ndarray。
我愿意使用 networkx 来完成这项任务，或者开发一些其他策略。此外，如果有任何编辑可以使 post 更清楚，请告诉我。
编辑：可能有帮助的一件事是另一个输出，面孔。这些 'define triangular faces via referencing vertex indices from verts.' 我相信这些可以用来 'connect' 或从一个顶点到另一个顶点画线，最终创建一个字典。
faces =
[[ 2 1 0] [ 0 3 2] [ 1 4 0] [ 0 4 3] [ 5 1 2] [ 3 5 2]
[ 5 4 1] [ 4 5 3] [ 8 7 6] [ 6 9 8] [ 7 10 6] [ 6 10 9]
[11 7 8] [ 9 11 8] [11 10 7] [10 11 9]]
提出了一种方法，对这组数据有效。但是，它并不适用于所有人。此修改会上传一组新数据。
verts =
[[0.1 1. 1. ] [1. 1. 0.1] [1. 0.1 1. ] [1. 1. 1.9] [1. 1.9 1. ] [1.9 1. 1. ]
[3.1 1. 4. ] [4. 1. 3.1] [4. 0.1 4. ] [4. 1. 4.9] [4. 1.9 4. ] [5. 1. 3.1]
[5. 0.1 4. ] [5. 1. 4.9] [5. 1.9 4. ] [5.9 1. 4. ] [7.1 8. 8. ]
[8. 8. 7.1] [8. 7.1 8. ] [8. 8. 8.9] [8. 8.9 8. ] [9. 8. 7.1]
[9. 7.1 8. ] [9. 8. 8.9] [9. 8.9 8. ] [9.9 8. 8. ]]
看起来像这样。
问题在于您如何构建图表。您应该首先使用 g = nx.Graph() 创建图的新实例，然后使用其方法添加其节点或边。在这种情况下，您想从嵌套列表中添加它的路径：
G = nx.Graph()
for path in verts:
nx.add_path(G, path)
然后获取连通分量：
cc = list(nx.connected_components(G))
# [{0.1, 1.0, 1.9}, {7.1, 8.0, 8.9}]
现在，如果您想查找每条路径属于哪个组件，您可以遍历路径并检查它们与哪些组件相交：
from collections import defaultdict
subgraphs = defaultdict(list)
for path in verts:
for ix,c in enumerate(cc):
if c.intersection(path):
subgraphs[ix].append(path)
print(subgraphs)
defaultdict(list,
{0: [[0.1, 1.0, 1.0],
[1.0, 1.0, 0.1],
[1.0, 0.1, 1.0],
[1.0, 1.0, 1.9],
[1.0, 1.9, 1.0],
[1.9, 1.0, 1.0]],
1: [[7.1, 8.0, 8.0],
[8.0, 8.0, 7.1],
[8.0, 7.1, 8.0],
[8.0, 8.0, 8.9],
[8.0, 8.9, 8.0],
[8.9, 8.0, 8.0]]})
我可以用另一种方法回答这个问题。它很长，因为我需要包括额外的部分。总的来说，我通过使用 faces 解决了这个问题，它定义了每个三角形及其顶点的索引。 faces 告诉我连接了哪些顶点。这使我能够构建一个线列表，其中包含顶点之间的所有连接。
# using faces and verts in original post
linelist = []
for idx, vert in enumerate(faces):
print(vert)
for i,x in enumerate(vert):
l = [np.ndarray.tolist(verts[faces[idx][i]]), np.ndarray.tolist(verts[faces[idx][(i+1)%len(vert)]])]
linelist.append(l)
产生如下元素：
[[1.0, 0.10000000149011612, 1.0], [1.0, 1.0, 0.10000000149011612]]
编辑：发现更快的方法：
tmp = [tuple(tuple(j) for j in i) for i in linelist]
graph = nx.Graph(tmp)
graphs = []
i=0
open('output.txt','w').close()
for idx, graph in enumerate(nx.connected_components(graph)):
graphs.append(graph)
print("Graph ",idx," corresponds to vertices: ",graph,'\n\n',file=open("output.txt","a"))
i+=1
这些点是相连的。接下来，我用别人的代码创建了一个字典，其中每个键是一个顶点，每个值是一个连接的顶点。然后我在这本词典上使用了呼吸优先搜索。请参阅下面的 class。
class MS_Graph():
def __init__ (self, linelist=None, vertices=None):
self.linelist = linelist if linelist is not None else None
self.vertices = vertices if vertices is not None else None
def getGraph(self):
'''
Takes self.linelist and converts to dict
'''
linelist = self.linelist
# edge list usually reads v1 -> v2
graph = {}
# however these are lines so symmetry is assumed
for l in linelist:
v1, v2 = map(tuple, l)
graph[v1] = graph.get(v1, ()) + (v2,)
graph[v2] = graph.get(v2, ()) + (v1,)
return graph
def BFS(self, graph):
"""
Implement breadth-first search
"""
# get nodes
#nodes = list(graph.keys()) # changed 4/16/2020
nodes = list(graph)
graphs = []
# check all nodes
while nodes:
# initialize BFS
toCheck = [nodes[0]]
discovered = []
# run bfs
while toCheck:
startNode = toCheck.pop()
for neighbor in graph.get(startNode):
if neighbor not in discovered:
discovered.append(neighbor)
toCheck.append(neighbor)
nodes.remove(neighbor)
# add discovered graphs
graphs.append(discovered)
self.graphs = graphs
return graphs
而且，把它放在一起：
Graph = MS_Graph(linelist)
graph = Graph.getGraph()
graphs = Graph.BFS(graph)
print(len(graphs))
# output: 3
print(graphs)
# output:
[[(1.0, 1.0, 0.10000000149011612), (0.10000000149011612, 1.0, 1.0), (1.0, 1.0, 1.899999976158142), (1.899999976158142, 1.0, 1.0), (1.0, 0.10000000149011612, 1.0), (1.0, 1.899999976158142, 1.0)],
[(4.0, 1.0, 3.0999999046325684), (3.0999999046325684, 1.0, 4.0), (4.0, 1.0, 4.900000095367432), (5.0, 1.0, 3.0999999046325684), (5.0, 0.10000000149011612, 4.0), (4.0, 0.10000000149011612, 4.0), (5.0, 1.0, 4.900000095367432), (5.900000095367432, 1.0, 4.0), (5.0, 1.899999976158142, 4.0), (4.0, 1.899999976158142, 4.0)],
[(8.0, 8.0, 7.099999904632568), (7.099999904632568, 8.0, 8.0), (8.0, 8.0, 8.899999618530273), (8.899999618530273, 8.0, 8.0), (8.0, 7.099999904632568, 8.0), (8.0, 8.899999618530273, 8.0)]]
也就是说，我确实想知道是否有更快的方法。
编辑：可能有更快的方法。由于 faces 包含每个三角形的顶点，属于一个对象的所有三角形都将有一个完整的链。即构成对象 1 的顶点集将不同于构成任何其他对象的顶点集。
例如每个对象的面集：
object_1_faces =
[ 2 1 0]
[ 0 3 2]
[ 1 4 0]
[ 0 4 3]
[ 5 1 2]
[ 3 5 2]
[ 5 4 1]
[ 4 5 3]
object_2_faces =
[ 8 7 6]
[ 6 9 8]
[ 7 10 6]
[ 6 10 9]
[11 7 8]
[ 9 11 8]
[11 10 7]
[10 11 9]
object_1_vertices = {0,1,2,3,4,5}
object_2_vertices = {6,7,8,9,10,11}
我想这意味着有比查找所有行更快的方法。
我的算法输出描述 3D 对象的顶点集 space (x, y, z)。在这种情况下，有两个对象：
verts =
[[0.1 1. 1. ] [1. 1. 0.1] [1. 0.1 1. ] [1. 1. 1.9] [1. 1.9 1. ]
[1.9 1. 1. ] [7.1 8. 8. ] [8. 8. 7.1] [8. 7.1 8. ] [8. 8. 8.9]
[8. 8.9 8. ] [8.9 8. 8. ]]
有两个四面体，一个以 (1, 1, 1) 为中心，另一个以 (8, 8, 8) 为中心。我的目标是使用广度优先搜索来识别对象是分开的，然后 classify 每个。我无法为我的算法获取正确形式的数据。
相反，我打算使用 networkx 模块，特别是使用 Graph class，它将 ndarrays 作为输入。我试过：
import networkx as nx
import numpy as np
graph = Graph(verts)
for idx, graph in enumerate(nx.connected_components(graph)):
print("Graph ",idx, " in ", graph,'\n\n',file=open("output.txt","a"))
但是，我无法创建图表。相反，我收到错误：
"Input is not a correct numpy matrix or array.")
networkx.exception.NetworkXError: Input is not a correct numpy matrix or array.
这让我很困惑，因为顶点类型 = numpy.ndarray。
我愿意使用 networkx 来完成这项任务，或者开发一些其他策略。此外，如果有任何编辑可以使 post 更清楚，请告诉我。
编辑：可能有帮助的一件事是另一个输出，面孔。这些 'define triangular faces via referencing vertex indices from verts.' 我相信这些可以用来 'connect' 或从一个顶点到另一个顶点画线，最终创建一个字典。
faces =
[[ 2 1 0] [ 0 3 2] [ 1 4 0] [ 0 4 3] [ 5 1 2] [ 3 5 2]
[ 5 4 1] [ 4 5 3] [ 8 7 6] [ 6 9 8] [ 7 10 6] [ 6 10 9]
[11 7 8] [ 9 11 8] [11 10 7] [10 11 9]]
提出了一种方法，对这组数据有效。但是，它并不适用于所有人。此修改会上传一组新数据。
verts =
[[0.1 1. 1. ] [1. 1. 0.1] [1. 0.1 1. ] [1. 1. 1.9] [1. 1.9 1. ] [1.9 1. 1. ]
[3.1 1. 4. ] [4. 1. 3.1] [4. 0.1 4. ] [4. 1. 4.9] [4. 1.9 4. ] [5. 1. 3.1]
[5. 0.1 4. ] [5. 1. 4.9] [5. 1.9 4. ] [5.9 1. 4. ] [7.1 8. 8. ]
[8. 8. 7.1] [8. 7.1 8. ] [8. 8. 8.9] [8. 8.9 8. ] [9. 8. 7.1]
[9. 7.1 8. ] [9. 8. 8.9] [9. 8.9 8. ] [9.9 8. 8. ]]
看起来像这样。
问题在于您如何构建图表。您应该首先使用 g = nx.Graph() 创建图的新实例，然后使用其方法添加其节点或边。在这种情况下，您想从嵌套列表中添加它的路径：
G = nx.Graph()
for path in verts:
nx.add_path(G, path)
然后获取连通分量：
cc = list(nx.connected_components(G))
# [{0.1, 1.0, 1.9}, {7.1, 8.0, 8.9}]
现在，如果您想查找每条路径属于哪个组件，您可以遍历路径并检查它们与哪些组件相交：
from collections import defaultdict
subgraphs = defaultdict(list)
for path in verts:
for ix,c in enumerate(cc):
if c.intersection(path):
subgraphs[ix].append(path)
print(subgraphs)
defaultdict(list,
{0: [[0.1, 1.0, 1.0],
[1.0, 1.0, 0.1],
[1.0, 0.1, 1.0],
[1.0, 1.0, 1.9],
[1.0, 1.9, 1.0],
[1.9, 1.0, 1.0]],
1: [[7.1, 8.0, 8.0],
[8.0, 8.0, 7.1],
[8.0, 7.1, 8.0],
[8.0, 8.0, 8.9],
[8.0, 8.9, 8.0],
[8.9, 8.0, 8.0]]})
我可以用另一种方法回答这个问题。它很长，因为我需要包括额外的部分。总的来说，我通过使用 faces 解决了这个问题，它定义了每个三角形及其顶点的索引。 faces 告诉我连接了哪些顶点。这使我能够构建一个线列表，其中包含顶点之间的所有连接。
# using faces and verts in original post
linelist = []
for idx, vert in enumerate(faces):
print(vert)
for i,x in enumerate(vert):
l = [np.ndarray.tolist(verts[faces[idx][i]]), np.ndarray.tolist(verts[faces[idx][(i+1)%len(vert)]])]
linelist.append(l)
产生如下元素：
[[1.0, 0.10000000149011612, 1.0], [1.0, 1.0, 0.10000000149011612]]
编辑：发现更快的方法：
tmp = [tuple(tuple(j) for j in i) for i in linelist]
graph = nx.Graph(tmp)
graphs = []
i=0
open('output.txt','w').close()
for idx, graph in enumerate(nx.connected_components(graph)):
graphs.append(graph)
print("Graph ",idx," corresponds to vertices: ",graph,'\n\n',file=open("output.txt","a"))
i+=1
这些点是相连的。接下来，我用别人的代码创建了一个字典，其中每个键是一个顶点，每个值是一个连接的顶点。然后我在这本词典上使用了呼吸优先搜索。请参阅下面的 class。
class MS_Graph():
def __init__ (self, linelist=None, vertices=None):
self.linelist = linelist if linelist is not None else None
self.vertices = vertices if vertices is not None else None
def getGraph(self):
'''
Takes self.linelist and converts to dict
'''
linelist = self.linelist
# edge list usually reads v1 -> v2
graph = {}
# however these are lines so symmetry is assumed
for l in linelist:
v1, v2 = map(tuple, l)
graph[v1] = graph.get(v1, ()) + (v2,)
graph[v2] = graph.get(v2, ()) + (v1,)
return graph
def BFS(self, graph):
"""
Implement breadth-first search
"""
# get nodes
#nodes = list(graph.keys()) # changed 4/16/2020
nodes = list(graph)
graphs = []
# check all nodes
while nodes:
# initialize BFS
toCheck = [nodes[0]]
discovered = []
# run bfs
while toCheck:
startNode = toCheck.pop()
for neighbor in graph.get(startNode):
if neighbor not in discovered:
discovered.append(neighbor)
toCheck.append(neighbor)
nodes.remove(neighbor)
# add discovered graphs
graphs.append(discovered)
self.graphs = graphs
return graphs
而且，把它放在一起：
Graph = MS_Graph(linelist)
graph = Graph.getGraph()
graphs = Graph.BFS(graph)
print(len(graphs))
# output: 3
print(graphs)
# output:
[[(1.0, 1.0, 0.10000000149011612), (0.10000000149011612, 1.0, 1.0), (1.0, 1.0, 1.899999976158142), (1.899999976158142, 1.0, 1.0), (1.0, 0.10000000149011612, 1.0), (1.0, 1.899999976158142, 1.0)],
[(4.0, 1.0, 3.0999999046325684), (3.0999999046325684, 1.0, 4.0), (4.0, 1.0, 4.900000095367432), (5.0, 1.0, 3.0999999046325684), (5.0, 0.10000000149011612, 4.0), (4.0, 0.10000000149011612, 4.0), (5.0, 1.0, 4.900000095367432), (5.900000095367432, 1.0, 4.0), (5.0, 1.899999976158142, 4.0), (4.0, 1.899999976158142, 4.0)],
[(8.0, 8.0, 7.099999904632568), (7.099999904632568, 8.0, 8.0), (8.0, 8.0, 8.899999618530273), (8.899999618530273, 8.0, 8.0), (8.0, 7.099999904632568, 8.0), (8.0, 8.899999618530273, 8.0)]]
也就是说，我确实想知道是否有更快的方法。
编辑：可能有更快的方法。由于 faces 包含每个三角形的顶点，属于一个对象的所有三角形都将有一个完整的链。即构成对象 1 的顶点集将不同于构成任何其他对象的顶点集。
例如每个对象的面集：
object_1_faces =
[ 2 1 0]
[ 0 3 2]
[ 1 4 0]
[ 0 4 3]
[ 5 1 2]
[ 3 5 2]
[ 5 4 1]
[ 4 5 3]
object_2_faces =
[ 8 7 6]
[ 6 9 8]
[ 7 10 6]
[ 6 10 9]
[11 7 8]
[ 9 11 8]
[11 10 7]
[10 11 9]
object_1_vertices = {0,1,2,3,4,5}
object_2_vertices = {6,7,8,9,10,11}
我想这意味着有比查找所有行更快的方法。