Algorithm - preventing the roots of a tree from joining up with one another

Hello, here's my question :

a. I have an algorithm that grows a tree(can either be free or rooted).

                 v4
                /   \
               /     \
              /       \
             /          \
            /            \
           v2            v6
          /  \             /  |  \
         /    \           /   |    \
        v1   v3    v5   v7  v8
        |                            |
        |                            |
       v10                        v9
                                    ....and so on  


The trouble with my algorithm is that the roots of the tree will join to one another as long as a certain criteria is satisfied.

For example, if a criteria(eg. shortest distance) is satisfied between v10 and v3, then a line will be drawn joining v10 and v3. When that happens, I don't have a proper tree structure anymore. Sad !
Similarly if v10 joins v5 or v10 joins v8 or v2 joins v6, I don't get a tree.

b. I hope that someone out there can enlighten me with some algorithm that allows me to test if an illegal line is about to be drawn.  

IF illegal line to be drawn then return a false value.

c. I be glad to provide more details.

Thanks a lot.













xooooxAsked:
Who is Participating?
 
MirkwoodCommented:
First of all search the web for the shortest path algorithms of Floyd and Dykstra. Probably one of the algorithms is the one that you are looking for. In other words, what is the problem that you tried to solve?

to find out if a graph is still tree is the same as to find out if the current node (one of the two ends of the new edge) is not part of a loop, since a tree does not have any loops.

Here is an abstract. Note that it is an recursive function. Adjacentnodes is a collection of nodes that are connected with this node.

private function IsInLoop (node) as  boolean
    isInLoop = _IsInLoop (node, new collection)    
end function

private function _IsInLoop (node, traversed as collection) as boolean
   if (node in traversed) then  ' is node in the collection of traversed
       _IsInLoop = true 'loop is created
       exit function
   end if
   traversed.add node
   for each adjecentnode in node.adjacentnodes
        _IsInLoop adjecentnode, traversed
   next  
   _IsInLoop = false
end function
0
 
xooooxAuthor Commented:
Edited text of question
0
 
xooooxAuthor Commented:
Edited text of question
0
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

 
xooooxAuthor Commented:
Edited text of question
0
 
xooooxAuthor Commented:
Edited text of question
0
 
xooooxAuthor Commented:
Edited text of question
0
 
xooooxAuthor Commented:
Edited text of question
0
 
chris_aCommented:
I do similar things in C, I use a map of nodes already connected for a quick look-up, you can do the same with an indexed collection, this is far quicker than the looping method since it gets you out of VB code.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.