Solved

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

Posted on 1998-10-12
128 Views
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
Question by:xoooox
• 6

Author Comment

ID: 1439578
Edited text of question
0

Author Comment

ID: 1439579
Edited text of question
0

Author Comment

ID: 1439580
Edited text of question
0

Author Comment

ID: 1439581
Edited text of question
0

Author Comment

ID: 1439582
Edited text of question
0

Author Comment

ID: 1439583
Edited text of question
0

LVL 13

Accepted Solution

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
next
_IsInLoop = false
end function
0

LVL 2

Expert Comment

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

Most everyone who has done any programming in VB6 knows that you can do something in code like Debug.Print MyVar and that when the program runs from the IDE, the value of MyVar will be displayed in the Immediate Window. Less well known is Debug.Asse…
Here are a few simple, working, games that you can use as-is or as the basis for your own games. Tic-Tac-Toe This is one of the simplest of all games.   The game allows for a choice of who goes first and keeps track of the number of wins for…
Show developers how to use a criteria form to limit the data that appears on an Access report. It is a common requirement that users can specify the criteria for a report at runtime. The easiest way to accomplish this is using a criteria form that a…
This lesson covers basic error handling code in Microsoft Excel using VBA. This is the first lesson in a 3-part series that uses code to loop through an Excel spreadsheet in VBA and then fix errors, taking advantage of error handling code. This l…