On 06.12.2016 20:29, gogurt wrote:
Hi all,
I have a temporal graph G carrying a vertex property map 'time' which is an integer representing the order in which vertices joined the graph. For each integer time from 1 until n (n = the final size of the graph) I want to calculate the number of leaves which exist in the graph up until that time.
The problem is that at different point of times in the graph, vertices which were previously leaves can be attached to and thus stop being leaves. So my thought is:
For each time t (running from 1 until n):
1) create a GraphView g of the existing graph up until time t 2) count the number of leaves in g
To do 1) I would just use the property map 'time'<t. For 2), I would just sum a list comprehension on the map returned by g.degree_property_map().
Is there a more efficient way to do this in graph-tool? I'm still relatively new to the intricacies of graph-tool, and I can see this taking a while with large graphs of a couple million nodes.
What do you call a leaf? A node with degree one? -- Tiago de Paula Peixoto <tiago@skewed.de>