|
#############################################################################
## This program is free software: you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
## the Free Software Foundation, either version 2 of the License, or
## (at your option) any later version.
##
## This program is distributed in the hope that it will be useful,
## but WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
## GNU General Public License for more details.
##
#W autGraphs.gi Michael Albert,
#W Steve Linton,
#W Ruth Hoffmann
##
#Y Copyright (C) 2004-2015 School of Computer Science,
#Y University of St. Andrews, North Haugh,
#Y St. Andrews, Fife KY16 9SS, Scotland
##
#############################################################################
##
#F GraphToAut(g,innode,outnode)
##
## Returns an automaton representing the input token passing network.
##
InstallGlobalFunction(GraphToAut, function(g,innode,outnode)
local states, ht, tm, ins, k, reported, s, i, y, t,
he, x, init, a;
states := [[]];
ht := SparseHashTable( s->HashKeyBag(s,57,0,4+4*Length(s)) );
AddHashEntry(ht,[],1);
tm := List([1..Length(g)], x-> [[]]);
ins := g[innode];
k := 1;
reported := 0;
while k <= Length(states) do
if Length(states)-reported > 100000 then
Info(InfoAutomataSL,2,"Processing ",k," out of ",Length(states));
reported := Length(states);
fi;
s := states[k];
for i in [1..Length(s)] do
for y in g[s[i]] do
if y <> outnode then
if not y in s then
t := ShallowCopy(s);
t[i] := y;
MakeImmutable(t);
he := GetHashEntry(ht,t);
if he = fail then
Add(states,t);
AddHashEntry(ht,t,Length(states));
he := Length(states);
for x in tm do
Add(x,[]);
od;
fi;
AddSet(tm[Length(tm)][k],he);
fi;
else
t := s{[1..i-1]};
t{[i..Length(s)-1]} := s{[i+1..Length(s)]};
MakeImmutable(t);
he := GetHashEntry(ht,t);
if he = fail then
Add(states,t);
AddHashEntry(ht,t,Length(states));
he := Length(states);
for x in tm do
Add(x,[]);
od;
fi;
AddSet(tm[i][k],he);
fi;
od;
od;
for x in [innode] do
if not x in s then
t := ShallowCopy(s);
Add(t,x);
MakeImmutable(t);
he := GetHashEntry(ht,t);
if he = fail then
Add(states,t);
AddHashEntry(ht,t,Length(states));
he := Length(states);
for y in tm do
Add(y,[]);
od;
fi;
AddSet(tm[Length(tm)][k],he);
fi;
od;
if outnode in ins then
AddSet(tm[Length(s)+1][k],k);
fi;
k := k+1;
od;
for i in [1..Length(tm)-1] do
if ForAll(tm[i], x->Length(x) = 0) then
Unbind(tm[i]);
fi;
od;
tm := Compacted(tm);
init := 1;
Info(InfoAutomataSL, 1, "Constructed automaton for ",Length(g),
" vertex graph ", Length(states), " states, ",Length(tm)-1," Symbols");
a := Automaton("epsilon", Length(states), Length(tm),tm,[init],[init]);
a!.statenames := states;
return a;
end );
#############################################################################
##
#F ConstrainedGraphToAut(g,innode,outnode,capacity)
##
## Returns an automaton representing the input token passing network, with
## limited capacity.
##
InstallGlobalFunction(ConstrainedGraphToAut, function(g,innode,outnode,capacity)
local states, ht, tm, ins, k, reported, s, i, y, t,
he, x, init, a;
states := [[]];
ht := SparseHashTable( s->HashKeyBag(s,57,0,4+4*Length(s)) );
AddHashEntry(ht,[],1);
tm := List([1..Length(g)], x-> [[]]);
ins := g[innode];
k := 1;
reported := 0;
while k <= Length(states) do
if Length(states)-reported > 100000 then
Info(InfoAutomataSL,2,"Processing ",k," out of ",Length(states));
reported := Length(states);
fi;
s := states[k];
for i in [1..Length(s)] do
for y in g[s[i]] do
if y <> outnode then
if not y in s then
t := ShallowCopy(s);
t[i] := y;
MakeImmutable(t);
he := GetHashEntry(ht,t);
if he = fail then
Add(states,t);
AddHashEntry(ht,t,Length(states));
he := Length(states);
for x in tm do
Add(x,[]);
od;
fi;
AddSet(tm[Length(tm)][k],he);
fi;
else
t := s{[1..i-1]};
t{[i..Length(s)-1]} := s{[i+1..Length(s)]};
MakeImmutable(t);
he := GetHashEntry(ht,t);
if he = fail then
Add(states,t);
AddHashEntry(ht,t,Length(states));
he := Length(states);
for x in tm do
Add(x,[]);
od;
fi;
AddSet(tm[i][k],he);
fi;
od;
od;
for x in [innode] do
if Length(s) < capacity and not x in s then
t := ShallowCopy(s);
Add(t,x);
MakeImmutable(t);
he := GetHashEntry(ht,t);
if he = fail then
Add(states,t);
AddHashEntry(ht,t,Length(states));
he := Length(states);
for y in tm do
Add(y,[]);
od;
fi;
AddSet(tm[Length(tm)][k],he);
fi;
od;
k := k+1;
od;
init := 1;
Info(InfoAutomataSL, 1, "Constructed automaton for ",Length(g),
" vertex graph ", Length(states), " states, ",Length(tm)-1," Symbols");
a := Automaton("epsilon", Length(states), Length(tm),tm,[init],[init]);
a!.statenames := states;
return a;
end );
#############################################################################
##
#F Parstacks(m,n)
##
## Constructs a token passing network with 2 different sized stacks (m,n)
## positioned parallel.
##
InstallGlobalFunction(Parstacks, function(m,n)
local g,i;
g := List([1..2+m+n], x->[]);
g[1] := [2,2+m];
g[2] := [3,2+m+n];
for i in [3..m] do
g[i] := [i-1,i+1];
od;
g[m+1] := [m];
g[m+2] := [m+3,m+n+2];
for i in [m+3..m+n] do
g[i] := [i-1,i+1];
od;
g[m+n+1] := [m+n];
return g;
end );
#############################################################################
##
#F Seqstacks(arg)
##
## Builds a token passing network containing a series (length of arg) of
## stacks of size arg[i].
##
InstallGlobalFunction(Seqstacks, function(arg)
local g, next, m, i;
if IsList(arg[1]) and Length(arg)=1 then
arg := arg[1];
fi;
g := [];
g[1] := [2];
next := 2;
for m in arg do
g[next] := [next+1,next+m];
g[next+m-1] := [next+m-2];
for i in [next+1..next+m-2] do
g[i] := [i-1,i+1];
od;
next := next+m;
od;
Add(g,[]);
return g;
end );
#############################################################################
##
#F BufferAndStack(n,m)
##
## Produces a token passing network containing a buffer of size n, followed
## by a stack of size m.
##
InstallGlobalFunction(BufferAndStack, function(n,m)
local gamma, i;
gamma := [];
gamma[1] := [2..n+1];
for i in [2..n+1] do
gamma[i] := [n+2];
od;
gamma[n+2] := [n+3, n+m+2];
for i in [n+3..n+m] do
gamma[i] := [i-1,i+1];
od;
gamma[n+m+1] := [n+m];
gamma[n+m+2] := [];
return gamma;
end );
[ Dauer der Verarbeitung: 0.41 Sekunden
(vorverarbeitet)
]
|
