| From: | Ashley Clarke |
| Date: | 3 May 99 at 13:40:15 |
| Subject: | [amos-list] Discover Loops in your own Home fast! |
From: Ashley Clarke <ashley@a-clarke.demon.co.uk>
> What sort of "Loop detector" have you used?
> [Explains own method..]
> Claude
---
My Philosophy to work the Loop detector problem is that the
Computers memory already has all the facts it needs to sort
them into usefull data without the need for fraction calculation.
It needs only to know:
1) The total number of Branches;
2) The Node numbers FROM and TO for each Branch;
3) The number of Nodes skipped between FROM and TO for each Branch.
As each Loop can be imagined as a Circle (obviously), my original
intention was to somehow use Tangents from each Node as they are all
layed out in order round the Circumference. Way too complicated and
uses slow, fractional numbers.
If, however, you can imagine (or draw) a Circle which is discected
around its circumference by the total number of Branches in your
Network, it can then be pulled-out to form a Table to base a Linked-List on.
The List length therefore becomes the total number of Branches stored in
memory.
The first column of the List contains the Branch number, second column
contains
FROM and TO Node connections for that Branch and the third column contains
the "length", or number of Nodes skipped (in order) to meet the TO Node.
All fairly basic so far and no risks of crashing your machine at all!
If you take the "lengths" of the Branches (as defined in the third column)
and re-order them diagramatically back into the circle, not bothering about
how much they overlap at this stage of thinking, you'll notice that they
share in common, "shears", making definate segments where the relationship
between each one is defined where they start and end. You'll notice that by
tracing with your finger around the circle, each Loop could be defined this
way.
Stretch this diagram out again and it resembles a Brick wall with holes
where you couldn't find a row of Branch-lengths to fit exactly on top of
one another. This, for me is the tricky bit, which is why this method's
only theorised!
By sorting the Branch lengths in their Number order, it is always
possible to form a "Brick Wall" with no holes, therefore, a Linked-List.
Once this list has been formulated, the Computer has a very logical view
of the data and can count very fast the relationships between Branches
and Nodes from an organised body of data at any time.
Ashley Clarke <ashley@a-clarke.demon.co.uk>
------------------------------------------------------------------------
Have you visited the new ONElist home page lately?
http://www.ONElist.com
ONElist: The Leading e-mail list and community service on the Internet!
------------------------------------------------------------------------
Official AMOS WWW: http://members.xoom.com/AmosFactory/front.html