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 <[email protected]>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list [email protected] https://lists.skewed.de/mailman/listinfo/graph-tool
