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
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.