Subject:
|
Minimum Spanning Tree
|
Newsgroups:
|
lugnet.robotics.rcx.nqc
|
Date:
|
Sat, 27 Jan 2001 12:42:30 GMT
|
Reply-To:
|
ash@jadzia-dax#NoSpam#.de
|
Viewed:
|
2539 times
|
| |
|
|
Hi,
I have got a problem with a program I wrote, and I can't find the error.
My intention was to have the program calculate a minimum spanning tree
on basis of Kruskals algorithm, which most of you are familiar with, I
presume. The program expects input of the following structure:
1-----2
| \ / |
|--3--|
| / \ |
4-----5
This is the graph in question. The user input consists only of the edge
weights. The edges are ordered like this: Egde 1: Connects Vertex 1-2,
Edge 2: Connects Vertex 1-3, Edge 3: Connects Vertex 1-4, Edge 4:
Connects Vertex 2-3, and so on. By pressing the button on Sensor_1 x
times, the user gives an input of weight x to the respective edge. Then,
when every edge has its weight, the programm calculates the MST and
beeps x times for every edge x it has used. Unfortunately, the beeps I
get are nonsense. Can anybody spot an error I fail to see? The program
is quoted here:
int Length[8], Edges[8], Edges2[4], Set[5], Node[2], CounterLength = 1,
Counter2Length = 0, TempLength = 0, TempLength2 = 1;
task main(){
SetSensor (SENSOR_1, SENSOR_TOUCH);
SetSensor (SENSOR_2, SENSOR_TOUCH);
until(CounterLength == 9){ //Input of 8
edges at the whole
Edges[CounterLength] = CounterLength;
//Reference-edgecount
if(SENSOR_1 == 1){ //Input of
length by user
Length[CounterLength] = (Length[CounterLength] + 1); //Length of
current edge
PlayTone(440,25); //Verification
Wait(25);}
if(SENSOR_2 == 1){ //Next edge
CounterLength = ++CounterLength;
PlayTone(220,25);
Wait(25);}}
CounterLength = 0;
//CounterLength now becomes a standard counter.
until(CounterLength == 9){ //This
algorithm sorts the edges in increasing order.
++CounterLength; //It is, of
course, quite primitive.
until(Counter2Length == 9){ //Every edge
is compared to the other edges, and,
++Counter2Length; //if
necessary, swapped.
if(Length[CounterLength] > Length[Counter2Length]){
TempLength = Length[CounterLength];
Length[CounterLength] = Length[Counter2Length];
Length[Counter2Length] = TempLength;
TempLength = Edges[CounterLength]; //If so, the
reference edge-count is swapped, too
Edges[CounterLength] = Edges[Counter2Length];
Edges[Counter2Length] = TempLength;}}}
TempLength = 1; //Every vertex
now gets its own set.
until(TempLength == 6){
Set[TempLength] = TempLength;
++TempLength;}
TempLength = 0;
CounterLength = 1;
until(TempLength == 9){ //For every
edge, check if it forms a circle with other edges.
++TempLength; //Not very
elegant, as I defined the two nodes of every edge by hand.
switch(Edges[TempLength]){
case 1:
Node[1] = Set[1];
Node[2] = Set[2];
break;
case 2:
Node[1] = Set[1];
Node[2] = Set[3];
break;
case 3:
Node[1] = Set[1];
Node[2] = Set[4];
break;
case 4:
Node[1] = Set[2];
Node[2] = Set[3];
break;
case 5:
Node[1] = Set[2];
Node[2] = Set[5];
break;
case 6:
Node[1] = Set[3];
Node[2] = Set[4];
break;
case 7:
Node[1] = Set[3];
Node[2] = Set[5];
break;
case 8:
Node[1] = Set[4];
Node[2] = Set[5];
break;}
if(Node[1] < Node[2]){ //The checked
two vertices V1 and V2 are only connected if Set[V1] = Set[V2]
Edges2[CounterLength] = Edges[TempLength]; //This line
saves every edge
++CounterLength;
TempLength2 = 1; //Node[V1] and
Node[V2] are only temporary containers for these sets mentioned above.
until(TempLength2 == 6){
if(Set[TempLength2] == Node[2]) //Update the
sets to keep this invariant intact.
Set[TempLength2] = Node[1]; //The set
representative is the smallest number contained in the set, and it
++TempLength2;}} //is also the
only valued saved in Set[x]}
if(Node[1] > Node[2]){
Edges2[CounterLength] = Edges[TempLength];
++CounterLength;
TempLength2 = 1;
until(TempLength2 == 6){
if(Set[TempLength2] == Node[1])
Set[TempLength2] = Node[2];
++TempLength2;}}}
TempLength = 1; //Beep x times
for edge no. x
until(TempLength == 5){
repeat(Edges2[TempLength]){
PlayTone(440,25);
Wait(35);}
PlayTone(220,25);
Wait(35);
until(SENSOR_2 == 1);
++TempLength;}}
--
TIE: Andi S.
|
|
1 Message in This Thread:
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
