python 图形工具访问顶点属性
python graph-tool access vertex properties
对于我当前的项目,我想使用图形工具库,因为它们声称是最快的:https://graph-tool.skewed.de/performance。我有一些算法(最短路径等)可以在非常大的网络上 运行,所以越快越好!
第一个问题:这个说法 'being the fastest' 是真的吗? ;)
在尝试构建适合我需要的图形工具图形时,我发现无法以有效的方式访问顶点属性。也许我错过了什么?
我现在的问题是,函数 "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()
您要找的函数是find_vertex()
:
https://graph-tool.skewed.de/static/doc/util.html#graph_tool.util.find_vertex
重要的是要认识到 graph-tool
通过将对性能敏感的循环从 Python 卸载到 C++ 来实现其速度。因此,每当您像在代码中那样遍历顶点时,就会失去任何优势。
另请注意,尽管 find_vertex()
是用 C++ 实现的,因此比纯 Python 中的等效项快很多倍,但它仍然是一个 O(N) 操作。对于大图,最好创建一个很好的旧 python 字典,将 属性 值映射到顶点,它的查找成本为 O(1)。
对于我当前的项目,我想使用图形工具库,因为它们声称是最快的:https://graph-tool.skewed.de/performance。我有一些算法(最短路径等)可以在非常大的网络上 运行,所以越快越好!
第一个问题:这个说法 'being the fastest' 是真的吗? ;)
在尝试构建适合我需要的图形工具图形时,我发现无法以有效的方式访问顶点属性。也许我错过了什么?
我现在的问题是,函数 "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()
您要找的函数是find_vertex()
:
https://graph-tool.skewed.de/static/doc/util.html#graph_tool.util.find_vertex
重要的是要认识到 graph-tool
通过将对性能敏感的循环从 Python 卸载到 C++ 来实现其速度。因此,每当您像在代码中那样遍历顶点时,就会失去任何优势。
另请注意,尽管 find_vertex()
是用 C++ 实现的,因此比纯 Python 中的等效项快很多倍,但它仍然是一个 O(N) 操作。对于大图,最好创建一个很好的旧 python 字典,将 属性 值映射到顶点,它的查找成本为 O(1)。