On 06.12.2016 23:26, gogurt wrote:
I'm not performing this calculation as the graph is being created. I'm being handed a graph with the vertex creation times, so I need to step back through the history of the graph to recover which vertices connected to which vertices anyway. Won't that essentially also require looking at GraphViews?
Just by inspecting the time labels at each of the incident edges of a node, it is trivial to say at which time it became a "leaf" (if ever) and when it stopped being one, simply by iterating over them a single time. If the graph just grows (i.e. edges are not deleted) a node is a "leaf" if its first edge has no other edge with the same time label, and stops being one by the time the second edge arrives. Just iterating through the nodes and determining this should be much faster (i.e. O(E)) than the original algorithm you proposed using GraphViews, which would be O(N^2). To quote Alexandre:
Notice also that this points to understanding your problem, not about graph-tool or any other instrument.
Indeed, when you ask "Is there a more efficient way to do this in graph-tool?" it usually amounts basically to "Is there a more efficient way to do this?" which is something you can answer by looking at the problem more closely, without requiring deep knowledge about any details of the library. -- Tiago de Paula Peixoto <tiago@skewed.de>