← Back to OneMasterChic Blog

Calculating distanceFromRoot with JGraphT’s BreadthFirstIterator

When you perform a root-by-root BFS, you can capture each vertex’s depth (distance from that root) on the fly. Below are two patterns: one that injects depth-tracking into your existing loop, and another that subclasses BreadthFirstIterator for cleaner reuse.

1) On-the-fly distances in your existing loop

Seed a per-root map with the root at depth 0, then for each traversed edge compute child depth = parent depth + 1. At the end you’ll have:

• allDistances → Map of root → (vertex → depth)
• visitFrequency → global counts

 public void processGraphByBreadthFirst( Map,Priority> priorityMap) {

Map<Class<? extends BaseEntity>, Map<Class<? extends BaseEntity>,Integer>> allDistances = new HashMap<>(); Map<Class<? extends BaseEntity>,Integer> visitFrequency = new HashMap<>();

brainzGraphModel.getEntityDirectedGraph() .vertexSet() .forEach(root -> {

Map<Class<? extends BaseEntity>,Integer> distances = new HashMap<>(); distances.put(root, 0); Set<PriorityEdge> visitedEdges = new HashSet<>();

BreadthFirstIterator<Class<? extends BaseEntity>,PriorityEdge> bfs = brainzGraphModel.getBreadthFirstIterator(root);

while (bfs.hasNext()) { Class<? extends BaseEntity> next = bfs.next(); Class<? extends BaseEntity> parent = bfs.getParent(next);

if (parent != null) { int parentDepth = distances.getOrDefault(parent, 0); int depthFromRoot = parentDepth + 1; distances.put(next, depthFromRoot);

PriorityEdge edge = brainzGraphModel .getEntityDirectedGraph() .getEdge(parent, next); if (visitedEdges.add(edge)) { visitFrequency.merge(next, 1, Integer::sum); }

// … your priority/weight logic here … } }

allDistances.put(root, distances); });

// allDistances.get(root).get(vertex) gives distanceFromRoot } 

2) Subclass BreadthFirstIterator to track depth

If you reuse BFS+depth often, a dedicated subclass encapsulates the logic:

 public class BFSWithDepth<V,E> extends BreadthFirstIterator<V,E> { private final Map<V,Integer> depth = new HashMap<>();

public BFSWithDepth(Graph<V,E> g, V start) { super(g, start); depth.put(start, 0); }

@Override protected void encounterVertex(V v, E viaEdge) { super.encounterVertex(v, viaEdge); V parent = Graphs.getOppositeVertex(getGraph(), viaEdge, v); depth.put(v, depth.get(parent) + 1); }

public int depthOf(V v) { return depth.getOrDefault(v, -1); } } 

Usage:

 BFSWithDepth<Class<? extends BaseEntity>,PriorityEdge> bfs = new BFSWithDepth<>(graph, root); while (bfs.hasNext()) { Class<? extends BaseEntity> v = bfs.next(); int dist = bfs.depthOf(v); // … process with dist … } 

Either approach gives you a reliable distanceFromRoot to feed into your scoring adjustments (depth penalty, novelty boost, etc.).