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
|
#include "muscle.h"
#include "distfunc.h"
const float INFINITY = float(1e29);
const unsigned NILL = uInsane;
static float *ShortestPathEstimate;
static unsigned *Predecessor;
static void GetMostDistantPair(DistFunc &DF, unsigned *ptrIndex1, unsigned *ptrIndex2)
{
const unsigned uNodeCount = DF.GetCount();
if (uNodeCount < 2)
Quit("GetMostDistantPair: < 2 seqs");
float MaxDist = -1;
unsigned Index1 = uInsane;
unsigned Index2 = uInsane;
for (unsigned i = 0; i < uNodeCount; ++i)
{
for (unsigned j = i + 1; j < uNodeCount; ++j)
{
float d = DF.GetDist(i, j);
if (d > MaxDist)
{
MaxDist = d;
Index1 = i;
Index2 = j;
}
}
}
assert(Index1 != uInsane);
assert(Index2 != uInsane);
*ptrIndex1 = Index1;
*ptrIndex2 = Index2;
}
static void InitializeSingleSource(DistFunc &DF, unsigned uIndex)
{
const unsigned uNodeCount = 0;
for (unsigned i = 0; i < uNodeCount; ++i)
{
ShortestPathEstimate[i] = INFINITY;
Predecessor[i] = NILL;
}
ShortestPathEstimate[uIndex] = 0;
}
static void Relax(DistFunc &DF, unsigned u, unsigned v)
{
float w = DF.GetDist(u, v);
float d = ShortestPathEstimate[u] + w;
if (ShortestPathEstimate[v] > d)
{
ShortestPathEstimate[v] = d;
Predecessor[v] = u;
}
}
void ShortestPath(DistFunc &DF, unsigned uIndex)
{
}
|
