minimum spanning trees (MST) can be maps of nodes and edges such that a
single path
is calculated that all nodes lie on and such that the total length of the
path is
at (or near) a minimum value.

Almost all MSTs are two-dimensional - useful for network designs that
eliminate
loops, vehicle routing problems that minimize fuel costs, integrated circuit
design, etc.

kruskal's algorithm is one method of genrating a MST (prim's algorithm is
another one)

I wrote a script that generates a MST pov code object file - using a
modified version
of kruskal for speed improvements and to produce three dimensional trees..

Inputs to the script are number of nodes, ranges for each of x,y,z
coordinates.

Attached are simple examples of the output.

The first image has the range for the z coordinates deliberately
flattened to a value of zero - shows a 2D MST.

The second image is a 3D MST without z flattening.

Both images employ 256 nodes.

The pov script has spheres for the nodes and
cylinders for the edges.
(Of course any arbitrary objects could be substituted
 for spehere|cyclinder.)
These images are meant just to demonstrate  MSTs.

I'm going to experiment with various things as nodes and edges.
Suggestions are welcome.
First idea is a reticule of crystals.

Question: I had doubts about nodes|edges not intersecting
via this method so I wrapped the object file with intersection { }.
Since nothing rendered I assume this means there are no
intersections of objects.
Is this a fair assumption?
Obviously, sphere radii and cylinder radii can radically modify
possible intersections.

pan

Post a reply to this message

Attachments:
Download 'kruskal_02.png' (134 KB) Download 'kruskal_01.png' (95 KB)

Preview of image 'kruskal_02.png'

Preview of image 'kruskal_01.png'

"pan" <pan### [at] syixcom> wrote in message news:4158fb48@news.povray.org...
> minimum spanning trees (MST) can be maps of nodes and edges such that a
> single path
> is calculated that all nodes lie on and such that the total length of the
> path is
> at (or near) a minimum value.

Does the path double-back? Otherwise, it looks like there are a bunch of
dead ends.

Post a reply to this message

"Dave Blandston" <gra### [at] earthlinknet> wrote in message
news:4158febb$1@news.povray.org...
> "pan" <pan### [at] syixcom> wrote in message news:4158fb48@news.povray.org...
> > minimum spanning trees (MST) can be maps of nodes and edges such that a
> > single path
> > is calculated that all nodes lie on and such that the total length of
the
> > path is
> > at (or near) a minimum value.
>
> Does the path double-back? Otherwise, it looks like there are a bunch of
> dead ends.
>
No - the algorithm is designed to prevent any loops.
That's the purpose of it.
Think of a computer network - you don't want ethernet loops in your routing.

A spanning tree is defined as a single path that connects all points in the
graph.
A minimal spanning tree optimizes that path according to what you're
after. Usually a total distance thing, but the edges could represent
financial costs, etc.

The images I posted are to minimize the total sum length of a path
that connects all points in the graph.

You put into your database all points and a table of values for each
possible
connection between all pairs of points. For 256 points you have 34,000 +
unique
possible connections. (Halved because path A -> B is likely the same value
as
path B -> A). If you drew a graph with all those lines on it you would
probably never get any use from the graph. This algorithm can be
biased and weighted to manipulate the final optimized path. Lots
easier to let the computer untangle the knots.

Post a reply to this message

Wasn't it Dave Blandston who wrote:
>"pan" <pan### [at] syixcom> wrote in message news:4158fb48@news.povray.org...
>> minimum spanning trees (MST) can be maps of nodes and edges such that a
>> single path
>> is calculated that all nodes lie on and such that the total length of the
>> path is
>> at (or near) a minimum value.
>
>Does the path double-back? Otherwise, it looks like there are a bunch of
>dead ends.

The walk is not actually a path, it's not even a trail, it's actually a
tree.

-- 
Mike Williams
Gentleman of Leisure

Post a reply to this message

"Mike Williams" <nos### [at] econymdemoncouk> wrote in message
news:SWv### [at] econymdemoncouk...
> The walk is not actually a path, it's not even a trail, it's actually a
> tree.

Oh. I had a vague recollection of the "Traveling Salesman" problem from
college...

Post a reply to this message

"pan" <pan### [at] syixcom> wrote:
> Question: I had doubts about nodes|edges not intersecting
> via this method so I wrapped the object file with intersection { }.
> Since nothing rendered I assume this means there are no
> intersections of objects.
> Is this a fair assumption?

Actually, no, if you're talking about PAIRWISE intersections.  This woud
just show that there's no point in the intersection of all the objects.

That is, if A = {1,2}, B = {2,3} and C = {3,4},
intersection {object{A} object{B} object{C} } would be empty.

Dave Matthews

Post a reply to this message

Dave Blandston wrote:
> Oh. I had a vague recollection of the "Traveling Salesman" problem from
> college...

That wonderful problem that computer science says is impossible to solve 
but which traveling salesmen have been solving for centuries. ;-)

Post a reply to this message

> "pan" <pan### [at] syixcom> wrote:
>> Question: I had doubts about nodes|edges not intersecting
>> via this method so I wrapped the object file with intersection { }.
>> Since nothing rendered I assume this means there are no
>> intersections of objects.
>> Is this a fair assumption?
> 
> Actually, no, if you're talking about PAIRWISE intersections.  This
> woud just show that there's no point in the intersection of all the
> objects. 
> 
> That is, if A = {1,2}, B = {2,3} and C = {3,4},
> intersection {object{A} object{B} object{C} } would be empty.
> 
> Dave Matthews

Good remark!
Your wrapping would in fact have taken advantage of my interunion
patch... 

Now, the question from a mathematical point-of-view is:
 In a 2D plane, is there a configuration of vertex so that it is
 possible for the tree to cross itself. 

I would say that it is, alas, possible, if the distance between the
vertex are not proportional to the cost of the link/edge. 

If the cost of the link is proportionnal to the distance between the
ends of it, you could demonstrate that a ST crossing itself is not a
MST. (because, by replacing 2 long link with 2 smaller not crossing, you
have a gain toward the MST). Therefore, A MST on such condition would
not cross itself. 

Now, let's figure distance is not proportional to link cost. You got a
problem... 

A <0,0>
B <1,0>
C <1,1>
D <0,1>

Cost matrix (symetry implied, I will let you deal with non-symetric cost
another time...): 
 AB: 1000
 AC: 1
 AD: 1000
 BC: 1
 BD: 1
 CD: 1000

The MST is ACBD (or whatever you order them along that path).
But AC and BD are crossing!

Have a nice week-end!
-- 




l'habillement, les chaussures que le maquillage et les accessoires.

Post a reply to this message