|
# In reality we only need a list indexed by triples, so we
# will quite probably end up with a tree where the leaves have
# weights as labels.
InstallGlobalFunction(CyclicSubList,
function(l, pos, len)
local r, i, j, llen;
llen := Length(l);
r := [];
i := pos; j := 1;
while j <= len do
r[j] := l[i];
i := i + 1; j := j + 1;
if i > llen then
i := 1;
fi;
od;
return r;
end);
InstallGlobalFunction( EnterAllSubwords,
function(idx, word, value)
local i, v, pos, ww;
pos := [1..Length(word)];
ww := List(word, x -> __ID(x));
for i in pos do
v := idx[ ww{ CyclicSubList(pos, i, 3) } ];
if value < v then
idx[ ww{ CyclicSubList(pos, i, 3) } ] := value;
fi;
od;
end);
#
InstallGlobalFunction( DigraphDijkstraST,
function(graph, s, t)
local vertices, dist, prev, queue, u, v, alt;
dist := [];
prev := [];
queue := BinaryHeap({x,y} -> x[1] < y[1]);
for v in DigraphVertices(graph) do
dist[v] := infinity;
prev[v] := -1;
od;
dist[s] := 0;
Push(queue, [0, s]);
while not IsEmpty(queue) do
u := Pop(queue);
u := u[2];
if u = t then
return [ dist, prev ];
fi;
for v in OutNeighbours(graph)[u] do
alt := dist[u] + DigraphEdgeLabel(graph, u, v);
if alt < dist[v] then
dist[v] := alt;
prev[v] := u;
Push(queue, [dist[v], v]);
fi;
od;
od;
return infinity;
end);
InstallGlobalFunction( DigraphDijkstraS,
function(graph, s)
local vertices, dist, prev, queue, u, v, alt;
dist := [];
prev := [];
queue := BinaryHeap({x,y} -> x[1] < y[1]);
for v in DigraphVertices(graph) do
dist[v] := infinity;
prev[v] := -1;
od;
dist[s] := 0;
Push(queue, [0, s]);
while not IsEmpty(queue) do
u := Pop(queue);
u := u[2];
for v in OutNeighbours(graph)[u] do
alt := dist[u] + DigraphEdgeLabel(graph, u, v);
if alt < dist[v] then
dist[v] := alt;
prev[v] := u;
Push(queue, [dist[v], v]);
fi;
od;
od;
return [ dist, prev ];
end);
[ Dauer der Verarbeitung: 0.8 Sekunden
(vorverarbeitet)
]
|
