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 <ti...@skewed.de>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool
