Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

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

Posted on 1998-10-12
8
132 Views
Last Modified: 2010-04-30
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.













0
Comment
Question by:xoooox
  • 6
8 Comments
 

Author Comment

by:xoooox
ID: 1439578
Edited text of question
0
 

Author Comment

by:xoooox
ID: 1439579
Edited text of question
0
 

Author Comment

by:xoooox
ID: 1439580
Edited text of question
0
Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 

Author Comment

by:xoooox
ID: 1439581
Edited text of question
0
 

Author Comment

by:xoooox
ID: 1439582
Edited text of question
0
 

Author Comment

by:xoooox
ID: 1439583
Edited text of question
0
 
LVL 13

Accepted Solution

by:
Mirkwood earned 250 total points
ID: 1439584
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
 
LVL 2

Expert Comment

by:chris_a
ID: 1439585
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

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Protecting vb6 & .Net code Obfuscation 18 150
Passing a Text Box name to a Sub 6 99
Set email body to html using vbscript 6 49
Collapse and expand table in Word 2010 2 29
Have you ever wanted to restrict the users input in a textbox to numbers, and while doing that make sure that they can't 'cheat' by pasting in non-numeric text? Of course you can do that with code you write yourself but it's tedious and error-prone …
When designing a form there are several BorderStyles to choose from, all of which can be classified as either 'Fixed' or 'Sizable' and I'd guess that 'Fixed Single' or one of the other fixed types is the most popular choice. I assume it's the most p…
Get people started with the process of using Access VBA to control Excel using automation, Microsoft Access can control other applications. An example is the ability to programmatically talk to Excel. Using automation, an Access application can laun…
Get people started with the utilization of class modules. Class modules can be a powerful tool in Microsoft Access. They allow you to create self-contained objects that encapsulate functionality. They can easily hide the complexity of a process from…

790 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question