python图形工具访问顶点属性

2024-03-28 21:51:03 发布

您现在位置:Python中文网/ 问答频道 /正文

对于我当前的项目,我想使用图形工具库,因为它们声称是最快的:https://graph-tool.skewed.de/performance。我有一些算法(最短路径等)可以在非常大的网络上运行,所以越快越好!在

第一个问题:这种说法“最快”是真的吗?;)

当我试图构建一个符合我需要的图形工具图形时,我发现不可能以有效的方式访问顶点属性。也许我错过了什么?在

我现在的问题是,函数“getVertexFromGraph(graph,position)”能否以更有效的方式编写?或者更一般地说:我能有效地检查一个顶点(由它的位置属性给出)是否已经在图中了吗。在

提前谢谢!在

import graph_tool as gt
#from graph_tool.all import *

edgeList = [[(0.5,1),(2.1,4.3)],[(2.1,4.3),(5.4,3.3)],[(5.4,3.3),(1.3,3.5)],[(4.4,3.3),(2.3,3.5)]] #A lot more coordinate values....

# Initialize the graph
routableNetwork = gt.Graph()

# Initialize the vertex property "position" to store the vertex coordinates
vpPosition = routableNetwork.new_vertex_property("vector<double>")
routableNetwork.vertex_properties["position"] = vpPosition

def getVertexFromGraph(graph, position):
    """
    This method checks if a vertex, identified by its position, is in the given graph or not.
    :param graph:       The graph containing all vertices to check  
    :param position:    The vertex/position to check
    :return:            The ID of the vertex if the vertex is already in the graph, 'None' otherwise
    """
    for v in graph.vertices():
        if graph.vp.position[v] == position:
            return v
    return None

def main():
    """
    This method creates the graph by looping over all given edges, inserting every: 
        - non existent vertex in the graph with its coordinates (property 'position')  
        - edge with its corresponding length (property 'distance')
    :return: -
    """
    for e in edgeList:
        vertex0 = getVertexFromGraph(routableNetwork,e[0])
        vertex1 = getVertexFromGraph(routableNetwork,e[1])
        if vertex0 == None:
            vertex0 = routableNetwork.add_vertex()
            routableNetwork.vertex_properties['position'][vertex0] = e[0]
        if vertex1 == None:
            vertex1 = routableNetwork.add_vertex()
            routableNetwork.vertex_properties['position'][vertex1] = e[1]

        edge = routableNetwork.add_edge(vertex0,vertex1)
        #routableNetwork.edge_properties['distance'][edge] = calculateDistance(e[0][0],e[0][1],e[1][0],e[1][1])

    #saveRoutableNetwork(routableNetwork)
    #graph_draw(routableNetwork, vertex_text=routableNetwork.vertex_index, vertex_font_size=18, output_size=(200, 200), output="two-nodes.png")

if __name__ == "__main__":
    main()

Tags: theinnonereturnifpositionpropertyproperties
1条回答
网友
1楼 · 发布于 2024-03-28 21:51:03

您要查找的函数是find_vertex()

https://graph-tool.skewed.de/static/doc/util.html#graph_tool.util.find_vertex

<^ >重要的是要意识到{{CD2>}通过从Python到C++卸载性能敏感的循环来实现它的速度。因此,无论何时迭代顶点,就像在代码中那样,都会失去任何优势。在

注意到,虽然^ {CD1>}是用C++实现的,因此比纯Python中的等价物快很多倍,但它仍然是O(n)操作。对于大型图,最好创建一个很好的旧python字典,该字典将属性值映射到顶点,查找成本为O(1)。在

相关问题 更多 >