The last lesson claimed that variable-depth traversal is the thing graphs are for. This lab makes you feel it, by having you write the traversal by hand.
makeGraph() is provided. It gives you three accessors — vertex(id),
out(id, type) and in(id, type) — which is roughly the adjacency a graph
engine keeps. Everything else is yours.
What to implement
reachable(graph, startId, type, maxDepth) — every vertex within
maxDepth hops, as a Map of id to shortest depth. Two things to get right:
the relationships here are symmetric, so an incoming edge counts as much as an
outgoing one; and the fixture graph contains a cycle, so a traversal without a
visited set will run until the lab times out.
shortestPath(graph, fromId, toId, type) — the vertex ids along the
shortest route, both ends included, or null when there is none.
colleagues(graph, personId) — people who worked at the same company over
an overlapping period. WORKED_AT edges carry { from, to } and a to of
null means still employed. Two half-open ranges overlap when each starts
before the other ends.
degreesOfSeparation(graph, aId, bId) — hops between two people over
KNOWS, 0 for the same person, -1 when unreachable.