-
Notifications
You must be signed in to change notification settings - Fork 0
/
generatesubgraphs.py
executable file
·45 lines (37 loc) · 1.15 KB
/
generatesubgraphs.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import networkx as nx
import collections
from collections import deque
from random import choice
import networkx as nx
from collections import defaultdict, deque
def bfs_edges(G, n, source, reverse=False):
if reverse and isinstance(G, nx.DiGraph):
neighbors = G.predecessors_iter
else:
neighbors = G.neighbors_iter
visited=set([source])
queue = deque([(source, neighbors(source))])
while queue and len(visited)<n:
parent, children = queue[0]
try:
child = next(children)
if child not in visited:
yield parent, child
visited.add(child)
queue.append((child, neighbors(child)))
except StopIteration:
queue.popleft()
def bfs_tree_custom(G,n):
source = choice(G.nodes())
print "source",source
T = nx.Graph()
T.add_node(source)
T.add_edges_from(bfs_edges(G,n,source,reverse=False))
return T
def bfs_predecessors(G, source):
return dict((t,s) for s,t in bfs_edges(G,source))
def bfs_successors(G, source):
d=defaultdict(list)
for s,t in bfs_edges(G,source):
d[s].append(t)
return dict(d)