Transform jgrapht graph into a Tree

Question

I would like to know if JGraphT has any built-in feature that allows one to export a generated graph into an infinite Tree (parent node/parent children) format.

Tree class

public class Tree<T> {

  private T value;
  private List<Tree<T>> children;

  private Tree(T value) {
    this.value = value;
    this.children = new ArrayList<>();
  }

  public static <T> Tree<T> of(T value) {
    return new Tree<>(value);
  }

  public Tree<T> addChild(T value) {
    Tree<T> newChild = new Tree<>(value);
    children.add(newChild);
    return newChild;
  }
}

The data sample

I'm experimenting with a tree of components, in which a component can have n children based on a root component. The nodes can only relate to one another in descending order.

E.g (Rough draft).

Car > Trunk > Engine > Valve > Bolt 
Car > Trunk > Battery 

And so on. Of course, the list of components should grow indefinitely based on the complexity of the root component in question.

The graph

I've created a DirectedPseudograph<Component, DefaultEdge> and added all the components as vertexes and added the edges between them, that part is working well. I can get the root components and traverse the graph using DFS and BFS to list the relationship between the nodes.

The Goal

I would like to export this into a Java object to use it further in the system. I've played a bit with the JSONExporter but I wasn't able to get it into a sort of Object tree. Hence the question here is to see if there is a specific way to achieve this. I'm flexible with the data type (class Tree<T> above) as long as I can generate nested objects. I would be okay generating a nested JSON object and marshaling it into POJO if needed as well, although that would mean a lot of extra code, so I wanted to take the shortcut.

I've been playing with the .vertexSet() and .edgeSet() functions, but generating a tree out of it would require a lot of boilerplate code.

Should I leverage a BFS Iterator to go over all nodes/connections and craft a tree out of it manually?

Best,

Neill

Answer 1

You can directly construct the tree based on your data structure by iterating recursively over the nodes in the graphs as follows.

public static void main(String[] args){
    //Construct the example graph.
    Graph<String, DefaultEdge> graph = new SimpleDirectedGraph<>(DefaultEdge.class);
    Graphs.addEdgeWithVertices(graph, "Car", "Trunk");
    Graphs.addEdgeWithVertices(graph, "Trunk", "Engine");
    Graphs.addEdgeWithVertices(graph, "Engine", "Valve");
    Graphs.addEdgeWithVertices(graph, "Valve", "Bolt");
    Graphs.addEdgeWithVertices(graph, "Trunk", "Engine");
    Graphs.addEdgeWithVertices(graph, "Car", "Battery");

    //OPTIONAL: Test whether the graph contains a directed cycle. This would prevent us from constructing a tree
    CycleDetector<String, DefaultEdge> cycleDetector = new CycleDetector<>(graph);
    if(cycleDetector.detectCycles())
        throw new RuntimeException("Graph cannot contain cycles, i.e. graph must be acyclic!");

    //Construct the Tree
    Tree<String> tree = Tree.of("Car");
    buildSubtree(graph, tree);

    System.out.println("Tree: \n"+tree);
}

private static void buildSubtree(Graph<String, DefaultEdge> graph, Tree<String> root){
    for(DefaultEdge arc : graph.outgoingEdgesOf(root.value)){
        Tree<String> child = root.addChild(graph.getEdgeTarget(arc));
        buildSubtree(graph, child);
    }
}

I made a few minor modifications to the Tree class:

public class Tree<T> {
    public final T value;
    private List<Tree<T>> children;

    private Tree(T value){
        this.value=value;
        this.children = new ArrayList<>();
    }

    public static <T> Tree<T> of(T value){
        return new Tree<>(value);
    }

    public Tree<T> addChild(T value){
        Tree<T> newChild = new Tree<>(value);
        children.add(newChild);
        return newChild;
    }

    public String toString(){
        String s ="node: "+value+" - children: ("+
                children.stream().map(child -> child.value.toString()).collect(Collectors.joining(","))+
                ")\n";
        for(Tree<T> child : children)
            s+=child.toString();
        return s;
    }
}

Output:

Tree: 
node: Car - children: (Trunk,Battery)
node: Trunk - children: (Engine)
node: Engine - children: (Valve)
node: Valve - children: (Bolt)
node: Bolt - children: ()
node: Battery - children: ()

Note: From the question I cannot deduce why this particular Tree structure has any advantage over the much richer data structures offered by JGraphT. It is questionable whether using this Tree structure is a good idea.