1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
/* For copyright information, see olden_v1.0/COPYRIGHT */
#include <string.h>
#include "mst.h"
#include "ssplain.h"
typedef struct blue_return {
Vertex vert;
int dist;
} BlueReturn;
static BlueReturn BlueRule(Vertex inserted, Vertex vlist)
{
BlueReturn retval;
Vertex tmp,prev;
Hash hash;
int dist,dist2;
int count;
if (!vlist) {
retval.dist = 999999;
return retval;
}
prev = vlist;
retval.vert = vlist;
retval.dist = vlist->mindist;
hash = vlist->edgehash;
dist = (int) HashLookup((unsigned int) inserted, hash);
/*chatting("Found %d at 0x%x for 0x%x\n",dist,inserted,vlist);*/
if (dist)
{
if (dist<retval.dist)
{
vlist->mindist = dist;
retval.dist = dist;
}
}
else chatting("Not found\n");
count = 0;
/* We are guaranteed that inserted is not first in list */
for (tmp=vlist->next; tmp; prev=tmp,tmp=tmp->next)
{
count++;
/* Splice chosen vertex out of the list */
if (tmp==inserted)
{
Vertex next;
next = tmp->next;
prev->next = next;
}
/* Find the shortest distance to any other vertex not in the list */
else
{
hash = tmp->edgehash;
dist2 = tmp->mindist;
dist = (int) HashLookup((unsigned int) inserted, hash);
/*chatting("Found %d at 0x%x for 0x%x\n",dist,inserted,tmp);*/
if (dist)
{
if (dist<dist2)
{
tmp->mindist = dist;
dist2 = dist;
}
}
else chatting("Not found\n");
if (dist2<retval.dist)
{
retval.vert = tmp;
retval.dist = dist2;
}
} /* else */
} /* for */
/*chatting("Count was %d\n",count);*/
return retval;
}
static Vertex MyVertexList = NULL;
static int ComputeMst(Graph graph,int numvert)
{
Vertex inserted,tmp;
int cost=0,dist;
/* make copy of graph */
chatting("Compute phase 1\n");
/* Insert first node */
inserted = graph->vlist;
tmp = inserted->next;
graph->vlist = tmp;
MyVertexList = tmp;
numvert--;
/* Announce insertion and find next one */
chatting("Compute phase 2\n");
while (numvert)
{
BlueReturn br;
if (inserted == MyVertexList)
MyVertexList = MyVertexList->next;
br = BlueRule(inserted, MyVertexList);
inserted = br.vert;
dist = br.dist;
numvert--;
cost = cost+dist;
}
return cost;
}
extern int dealwithargs(int argc, char *argv[]);
int main(int argc, char *argv[])
{
Graph graph;
int dist;
int size;
chatting("Hash entry size = %d\n", sizeof(struct hash_entry));
chatting("Hash size = %d\n", sizeof(struct hash));
chatting("Vertex size = %d\n", sizeof(struct vert_st));
size = dealwithargs(argc,argv);
chatting("Making graph of size %d\n",size);
graph = MakeGraph(size);
chatting("Graph completed\n");
chatting("About to compute mst \n");
dist = ComputeMst(graph,size);
chatting("MST has cost %d\n",dist);
exit(0);
}
|
