All is in the subject. I want to represent this kind of tree? > http://en.wikipedia.org/wiki/Image:Tree_graph.svg
They're actually forests. Is it possible with the Collection api or not ?
Also, how can I design an XML file to store a forrest?
Any help is welcome.
Thanks
You can certainly represent a tree with the Collection API - a general graph can be represented using adjacency lists by means of a Map<Node, List><Node>> or a Map<Node, Set><Node>>.
If you can design an XML file to store a simple tree (which should be easy, given that that's what XML does) then a forest is simply a list of simple trees. Have a forest element which contains multiple tree elements.
You refered us to a picture of a tree.
What do you want to represent? A tree or a picture of a tree? (The picture has coordinate information included along with the nodes and it takes some code to generate coordinates if none are given.)
The tree, or forest is trivial to represent. It consists of nodes, which are numbered numerically in your picture. And a set of edges where each edge connects two nodes.
That structure, nodes and edges that are pairs of nodes, is actually able to hold a more complicated structure, a graph. If all you want to do is hold a tree (or a forest) in the structure it is adequate. If you want to be able to test whether the graph that you are holding is actually a tree, you need code to verify that.
So, if you have no information at the nodes, and all they are is integers, the simplest representation is to let a Node be an integer (so you don't need to build a Node class) and an edge is a pair of integers and a tree (or forest) is a collection (an array) of edges.
class Edge{
int v1;
int ve;
}
class Tree{
Edge[] edges;
}
Can the java Collection api hold a tree? Well sure.
class Tree{
List edges;
}
Building an XML structure to hold a forest is not much different from building java code to hold such a structure. You could use any of numerous formats. For example the following would be the tree in your picture.
<forest>
<edge><v1>1</v1><v2>4</v2></edge>
<edge><v1>2</v1><v2>4</v2></edge>
<edge><v1>3</v1><v2>4</v2></edge>
<edge><v1>4</v1><v2>5</v2></edge>
<edge><v1>5</v1><v2>6</v2></edge>
</forest>
And this design was hard because ...?
Thank you both of you for your quick replies.
What I forgot to tell is that on each edge, I should have a kind of cost. And a node is more that simple integers. They have a lot of datas and they are used to calculate the cost between 2 nodes.
I thought there was a graph(forest) class in the API. I'll need to implement some alogrithms on this graph.
For the XML,
<xml>
<nodes>
<node1 name="aName">
<linkedNodes>
<linkNode1 name="aName2" cost="15"/>
<linkNode2 name="aName3 cost="25""/>
<linkNode3 name="aName4 cost="35""/>
</linkedNodes>
</node1>
</nodes>
</xml>
I don't find that a clean solution.
I would do something like:
<nodes>
<node index="0" name="..."/>
<node index="1" name="..."/>
</nodes>
<edges>
<edge node1="0"node2="1" name="..." cost="..." />
...
</edges>