On 20.08.2015 20:40, gogurt wrote:
The way I've done this in NetworkX is to essentially keep track of 3 lists of nodes (infected, active, unexplored) and update them in a simple loop. Then at the end of the process when the epidemic dies or hits a threshold, I just subset the graph and get the subgraph which represents the path of the infection.
The difference between graph-tool and NetworkX for things like this is very superficial. Essentially every algorithm that you can come up with for networkx can be mapped one-to-one to graph-tool, and the efficiency will in general be about the same. Graph-tool will be faster only when the important loops can be moved out of Python and into C++.
*My question is: *what's the most efficient way to do this using graph-tool?
At first I thought the same approach (subsetting vertices, which would mean working with vertex iterables) would be the fastest way, but then I thought maybe working on the original graph with a vertex PropertyMap would be better.
You can do exactly that, but the lookup will be slower if you use sets or lists, than if you just mark each infected node with a Boolean property map.
But my intuition is extremely poor on this (e.g. is it even possible to subset vertices in a graph based on their values in a PropertyMap object?).
Why shouldn't it be possible? There are many ways to to this. The simplest is something like: infected = [v for v in g.vertices() if infected[v]] but this is of course O(N). I think the best approach is to keep an infected set together with a property map: is_infected = g.new_vertex_property("bool", False) infected_set = [] root = g.vertex(10) is_infected[root] = True infected_set.append(root) while len(infected_set) < g.num_vertices(): new_infected = [] for v in infected_set: for u in v.out_neighbours(): if random() < p and not is_infected[u]: is_infected[u] = True new_infected.append(u) infected_set.extend(new_infected) I hope this helps. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>