BFS on time-dpendet network with limited waiting time
Konschake, Mario
Hello,
I am an epidemiologist doing research on the spread of disease via trade networks (in particular animal trade networks). I love to use networkx. One of my main issues is to investigate the effects of the sparse temporal structure of the network (i.e. edges are only present a certain times). I therefore implemented a modified BFS-traversal of a MultiDiGraph which respects limited waiting times on nodes. I use the key of MultiDiGraph edges as the timestamp when a certain edge is present.
(u,v,key=t) means that (u,v) is present at time t.
I want to only allow traversal of an edge (u,v) , when the time when u is first reached plus the waiting time k is bigger than the time when edge is present. So traversal from u is only allowed for a period of length k after u is seen for the first time.
This mimics an epidemic spread with an infectious period k with a propability of infection of 100%.
I tried different approaches with and without the use of networkx. So far a non-networkx approach seems to be the fastest. My networkx solution reads better:
import networkx as nx
import Queue
def waiting_time_bfs(M, source, source_time, waiting_time):
removed = set() #already visited nodes
queue = Queue.PriorityQueue() #always follow edges with smaller keys first
queue.put((source_time, source))
empty = False
while not empty:
try:
visit_time, parent = queue.get(block=False)
if parent not in removed:
for child, attr in M[parent].iteritems():
try:
#get the smallest key for which the edge is allowed to traverse
traversal_time = min([key for key in attr.iterkeys() if visit_time <= key <= visit_time + waiting_time]) #zweites <= mit < ersetzen
if child not in removed:
queue.put((traversal_time, child))
except ValueError:
pass
removed.add(parent)
except Queue.Empty:
empty=True
return removed
if __name__ == "__main__":
edges = [("a","b",1),("b","c",2),("c","d",4),("c","e",8)] #third item encodes day of presence
M = nx.MultiDiGraph()
for u,v,d in edges:
M.add_edge(u, v, key=d)
print waiting_time_bfs(M, "a", 1, 2)
The BFS implemeted by Aric Hagberg is slightly different: http://networkx.lanl.gov/_modules/networkx/algorithms/traversal/breadth_first_search.html#bfs_edges Especially the children are already stored in the queue using an iterator.
I am posting here to ask if someione with more expertise sees a way to increase the speed of my code.
Thanks, Mario.
Aric Hagberg
<Mario.K...@fli.bund.de> wrote:
> Hello,
>
> I am an epidemiologist doing research on the spread of disease via trade
> networks (in particular animal trade networks). I love to use networkx. One
> of my main issues is to investigate the effects of the sparse temporal
> structure of the network (i.e. edges are only present a certain times). I
> therefore implemented a modified BFS-traversal of a MultiDiGraph which
> respects limited waiting times on nodes. I use the key of MultiDiGraph edges
> as the timestamp when a certain edge is present.
>
> (u,v,key=t) means that (u,v) is present at time t.
>
> I want to only allow traversal of an edge (u,v) , when the time when u is
> first reached plus the waiting time k is bigger than the time when edge is
> present. So traversal from u is only allowed for a period of length k after
> u is seen for the first time.
>
> This mimics an epidemic spread with an infectious period k with a
> propability of infection of 100%.
>
> increase the speed of my code.
I might not be understanding quite correctly what you want. But I
think I got it pretty close.
Here is a modified version of the BFS code in NetworkX that keeps
track of the edge appearance time on edges and searches with your time
constraint. I used the 'time' attribute for edges instead of the
multigraph key. It has the same complexity as BFS but will be a
little slower because of the extra test for the time constraint, and
generating weights with child nodes. I only tested that it runs...
def bfs_edges(G, source, time, infectivity_period):
def _children(G,node):
# return generator of (nbr,t) pairs, adjust as necessary for other keys
return ((v,d['time']) for u,v,d in G.edges_iter(node,data=True))
visited = set([source])
stack = [(time,source,_children(G,source))]
while stack:
time,parent,children = stack[0]
try:
child,edge_appearance = next(children)
if (child not in visited
and time <= edge_appearance <= time + infectivity_period):
yield parent,child
visited.add(child)
stack.append((time+1,child,_children(G,child)))
except StopIteration:
stack.pop(0)
if __name__ == "__main__":
import networkx as nx
edges = [("a","b",1),("b","c",2),("c","d",4),("c","e",6)]
edges.append(('b','f',3))
edges.append(('b','c',3))
edges.append(('c','g',1))
edges.append(('c','g',4))
edges.append(('a','l',2))
edges.append(('l','f',3))
H = nx.MultiDiGraph()
for u,v,d in edges:
H.add_edge(u, v, time=d)
l = list(bfs_edges(H,'a',1,2))
print l
print set(nx.utils.flatten(l))
Aric
franck kalala
WARNING: Failure executing file: <chess_masters.py>
Aric Hagberg
It works for me. Maybe you have an older version of NetworkX?
Aric
franck kalala
Out[10]: '1.6'
In [11]: run chess_masters
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
/home/eragon/sci/chess_masters.py in <module>()
72
73
---> 74 G=chess_pgn_graph()
75
76 ngames=G.number_of_edges()
/home/eragon/sci/chess_masters.py in chess_pgn_graph(pgn_file)
51 G=nx.MultiDiGraph()
52 game={}
---> 53 datafile=nx.utils.get_file_handle(pgn_file)
54 lines = (line.decode().rstrip('\r\n') for line in datafile)
55 for line in lines:
AttributeError: 'module' object has no attribute 'get_file_handle'
WARNING: Failure executing file: <chess_masters.py>
De : Aric Hagberg <aric.h...@gmail.com>
À : networkx...@googlegroups.com
Envoyé le : Samedi 4 février 2012 0h28
Objet : Re: [networkx-discuss] error in chess_masters code
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discuss+unsub...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.
Aric Hagberg
> Am having the laster version of networkx, the complete error message looks
> like this
>
> In [10]: nx. __version__
> Out[10]: '1.6'
>
> In [11]: run chess_masters
> ---------------------------------------------------------------------------
> AttributeError Traceback (most recent call last)
>
> /home/eragon/sci/chess_masters.py in <module>()
> 72
> 73
> ---> 74 G=chess_pgn_graph()
> 75
> 76 ngames=G.number_of_edges()
>
> /home/eragon/sci/chess_masters.py in chess_pgn_graph(pgn_file)
> 51 G=nx.MultiDiGraph()
> 52 game={}
> ---> 53 datafile=nx.utils.get_file_handle(pgn_file)
> 54 lines = (line.decode().rstrip('\r\n') for line in datafile)
> 55 for line in lines:
>
>
> AttributeError: 'module' object has no attribute 'get_file_handle'
> WARNING: Failure executing file: <chess_masters.py>
That example code is different that the one you pointed to before (which works):
http://networkx.lanl.gov/examples/drawing/chess_masters.html
Aric
franck kalala
Objet : Re: Re : [networkx-discuss] error in chess_masters code