使用JGraphT获取树节点层级并按层级分组构建ArrayList

Got it, let's work through this problem together. You're using JGraphT's directed tree structure and want to calculate each node's level, then group nodes by their levels into an ArrayList<ArrayList<Obj>>. Here's a straightforward, step-by-step solution:

Since it's a tree structure, we first need to confirm the root node (in your example, that's a). We'll use Breadth-First Search (BFS) to traverse the tree—this is perfect for level-based traversal, as it processes all nodes of one level before moving to the next.

// Define your root node (adjust if your root is different)
Obj root = a;

// Map to store each node and its corresponding level
Map<Obj, Integer> nodeLevelMap = new HashMap<>();
// Set root level to 0 (you can use 1 instead if that fits your business logic)
nodeLevelMap.put(root, 0);

// Queue for BFS traversal
Queue<Obj> traversalQueue = new LinkedList<>();
traversalQueue.add(root);

while (!traversalQueue.isEmpty()) {
    Obj currentNode = traversalQueue.poll();
    int currentLevel = nodeLevelMap.get(currentNode);
    
    // Iterate through all outgoing edges (since it's a directed tree, these point to child nodes)
    for (DefaultEdge edge : serviceGraph.outgoingEdgesOf(currentNode)) {
        Obj childNode = serviceGraph.getEdgeTarget(edge);
        // Only process nodes we haven't assigned a level to yet
        if (!nodeLevelMap.containsKey(childNode)) {
            nodeLevelMap.put(childNode, currentLevel + 1);
            traversalQueue.add(childNode);
        }
    }
}

Now that we have every node's level, we can organize them into a nested ArrayList where the outer list's index matches the node level, and the inner list holds all nodes at that level.

// Find the highest level to size our outer list correctly
int maxLevel = Collections.max(nodeLevelMap.values());
ArrayList<ArrayList<Obj>> levelGroupedNodes = new ArrayList<>();

// Initialize empty lists for each level
for (int i = 0; i <= maxLevel; i++) {
    levelGroupedNodes.add(new ArrayList<>());
}

// Populate each level's list with corresponding nodes
for (Map.Entry<Obj, Integer> entry : nodeLevelMap.entrySet()) {
    int nodeLevel = entry.getValue();
    Obj node = entry.getKey();
    levelGroupedNodes.get(nodeLevel).add(node);
}

To make sure everything works as expected, you can print out the grouped nodes:

for (int i = 0; i < levelGroupedNodes.size(); i++) {
    System.out.printf("Level %d nodes: %s%n", i, levelGroupedNodes.get(i));
}

Using your example graph structure, the output would look like this:

Level 0 nodes: [a]
Level 1 nodes: [b]
Level 2 nodes: [c, z]
... (other nodes will appear here based on your remaining edges)

• If your tree might have multiple root nodes (unlikely for a standard tree, but possible if your graph isn't strictly a tree), add logic to find nodes with an in-degree of 0 as roots.
• For undirected trees, add a Set<Obj> visited collection to avoid revisiting the parent node during traversal.

内容的提问来源于stack exchange，提问作者user_mda