Ni! Hi gogurt, Although you don't specify your problem thoroughly, here's a likely useful observation.
Being a leaf is a local property, it depends only on a vertices' own connections. Therefore, if you change the graph, you can easily keep track of how that change affected the number of leaves. And so, instead of counting the number of leaves, at each step you can calculate how your changes affect the number of leaves, and add that to the previous number. The difference in efficiency is: Your changes usually affect only few vertices at a time. Counting the number of leaves runs through all your vertices each time. Notice you don't need a GraphView to do this. Just keep a vertex property with the current degrees as you move through each step, updating only what gets changed. Notice also that this points to understanding your problem, not about graph-tool or any other instrument. Cheers, ale .~´ Le mardi 06 décembre 2016 à 12:29 -0700, gogurt a écrit : > 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. > > > > > > -- > View this message in context: http://main-discussion-list-for-the-gra > ph-tool-project.982480.n3.nabble.com/Counting-the-number-of-leaves- > at-different-times-tp4026905.html > Sent from the Main discussion list for the graph-tool project mailing > list archive at Nabble.com. > _______________________________________________ > graph-tool mailing list > [email protected] > https://lists.skewed.de/mailman/listinfo/graph-tool _______________________________________________ graph-tool mailing list [email protected] https://lists.skewed.de/mailman/listinfo/graph-tool
