Key words from question:
#services
#directed-acyclic-graph
#entrypoint
#dependencies
#load-factor
Inputs:
- directed acyclic graph
("m=n,p,q" means these edges exist: m->n, m->p, m->q)
["a=",
"b=a",
"c=b,x",
"d=b,c",
"e=b,c,d"]- node name
"e"
Output:
map of node name to number of times visited
{"e": 1,
"a": 4,
"c": 2,
"d": 1,
"b": 4}Code
from collections import defaultdict
def f(inputlist, start):
s = set()
adj = defaultdict(list)
for x in inputlist:
s.add(x.split('=')[0])
for x in inputlist:
i = x.split('=')[0]
j = x.split('=')[1].split(",")
for k in j:
if k != '' and k in s:
adj[i].append(k)
counts = defaultdict(int)
def dfs(start):
counts[start] += 1
for x in adj[start]:
dfs(x)
dfs(start)
return counts
Comments (5)