algorithmgraphtreetree-search

Optimal solution to find the leafs of a tree

I have a tree-like structure. I can get several lines that connect together and make up the tree. The lines are made up start-points and end-points. here is some sample data from a tree in XML format.

<Skeleton>
   <Line StartX="384" StartY="135"  EndX="385" EndY="129"  /> 
   <Line StartX="384" StartY="137"  EndX="384" EndY="135"  /> 
   <Line StartX="384" StartY="138"  EndX="384" EndY="137"  /> 
   <Line StartX="384" StartY="139"  EndX="384" EndY="138"  /> 
   <Line StartX="383" StartY="144"  EndX="384" EndY="139"  /> 
   <Line StartX="383" StartY="147"  EndX="383" EndY="144"  /> 
    ...
</Skeleton>

and here is a graphical representation of the tree:

enter image description here

What I need to do is to extract the leafs and the junctions on this tree as it is shown in the image: enter image description here

I want to find an optimized algorithm regarding complexity and time to do this task.

Solution

    1. Generate a mathematical graph out of your data (coordinates are the labels of the vertices and each line from your data becomes an edge in the graph).

    2. define the root vertex of your tree.

    3. leafs are all vertices that are not the root vertex and connected to only one edge

    4. junctions are all vertices that are connected to at least 3 edges (in your example)