如何使用2D np数组作为输入创建networkx图形

Question

我的算法输出描述三维空间（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）中心。我的目标是使用广度优先搜索来确定对象是分开的，然后对每个对象进行分类。我无法获得正确格式的数据以用于我的算法

相反，我打算使用networkx模块，特别是使用Graph类，它将ndarray作为输入。我试过：

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.

这让我很困惑，因为verts的类型=numpy.ndarray

我愿意使用networkx完成这项任务，或者开发其他一些策略。此外，请让我知道，如果有任何编辑，可能使这篇文章更清楚

编辑：另一个可能有用的输出是faces。这些“通过引用顶点索引定义三角形面”。我相信这些可以用来“连接”或从顶点到顶点绘制线，最终创建字典

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. ]]

看起来是这样的。

Answer 1

问题在于如何构建图形。您应该首先使用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]]})

Answer 2

我可以用另一种方法来回答这个问题。这是漫长的，因为我需要包括额外的作品。一般来说，我利用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 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包含每个三角形的顶点，因此属于一个对象的所有三角形都将有一个完整的链。i、 e.构成对象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}

我想这意味着有一种比找到所有线条更快的方法