(* Ein Beispiel zum ausprobieren *);
val graph=[(1,3,23),(1,4,1),(2,4,4),(4,5,9),(5,7,3),(6,7,17)];
type kante = (int*int*int)
type ebene = kante list;
fun ausgabe(baum:ebene) =
let
(* ------------------------------------------------------------------ *)
fun KILLELEMENT(liste:ebene,element:kante)=
if tl(liste)=[]
then if hd(liste)=element
then []
else [hd(liste)]
else if hd(liste)=element
then tl(liste)
else hd(liste)::KILLELEMENT(tl(liste),element);
(* entfernt angegebenes elment aus liste *)
(* ------------------------------------------------------------------ *)
fun min(liste:ebene)=
if length(liste) > 2
then if #1(nth(liste,1))< #1(nth(liste,0))
then min(tl(liste))
else if #1(nth(liste,1))= #1(nth(liste,0))
then if #2(nth(liste,1))< #2(nth(liste,0))
then min(tl(liste))
else min(hd(liste)::tl(tl(liste)))
else min(hd(liste)::tl(tl(liste)))
else if #1(nth(liste,1))< #1(nth(liste,0))
then hd(tl(liste))
else if #1(nth(liste,1))= #1(nth(liste,0))
then if #2(nth(liste,1))< #2(nth(liste,0))
then hd(tl(liste))
else hd(liste)
else hd(liste);
fun MINSORT(liste:ebene)=
if length(liste)=1
then [nth(liste,0)]
else min(liste)::MINSORT(KILLELEMENT(liste,min(liste)));
(* sortiert liste nach kleinstem element *)
(* ------------------------------------------------------------------ *)
fun BETA(liste:ebene,knoten:int,zahl:int)=
if knoten = #1(nth(liste,zahl))
then (#2(nth(liste,zahl)),true,nth(liste,zahl))
else if knoten = #2(nth(liste,zahl))
then (#1(nth(liste,zahl)),true,nth(liste,zahl))
else if zahl=(length(liste)-1)
then (0,false,(0,0,0))
else BETA(liste,knoten,zahl+1);
fun GAMMA(liste,knoten)=
if length(liste)=0
then []
else if #2(BETA(liste,knoten,0))
then #1(BETA(liste,knoten,0))::
GAMMA(KILLELEMENT(liste,#3(BETA(liste,knoten,0)))
,#1(BETA(liste,knoten,0)))
else [];
fun DELTA(liste)=
#1(nth(liste,0))::GAMMA(liste,#1(nth(liste,0)));
fun EPSILON(hliste,zahl1,zahl2)=
if nth(hliste,zahl1)=nth(hliste,zahl2)
then false
else if zahl2=(length(hliste)-1)
then if zahl1=(length(hliste)-2)
then true
else EPSILON(hliste,zahl1+1,zahl1+2)
else EPSILON(hliste,zahl1,zahl2+1);
(* begehen des graphen zur überfrüfung auf zyklen *)
(* ------------------------------------------------------------------ *)
fun OMIKRON(liste,hliste,zahl)=
if #1(nth(liste,zahl))=nth(hliste,0)
then if #2(nth(liste,zahl))=nth(hliste,1)
then if length(hliste)=2
then KILLELEMENT(liste,nth(liste,zahl))
else OMIKRON(KILLELEMENT(liste,nth(liste,zahl)),tl(hliste),0)
else OMIKRON(liste,hliste,zahl+1)
else if #2(nth(liste,zahl))=nth(hliste,0)
then if #1(nth(liste,zahl))=nth(hliste,1)
then if length(hliste)=2
then KILLELEMENT(liste,nth(liste,zahl))
else OMIKRON(KILLELEMENT(liste,nth(liste,zahl)),tl(hliste),0)
else OMIKRON(liste,hliste,zahl+1)
else OMIKRON(liste,hliste,zahl+1);
fun OMEGA(liste)=
if length(OMIKRON(liste,DELTA(liste),0))=0
then EPSILON(DELTA(liste),0,1)
else if EPSILON(DELTA(liste),0,1)
then OMEGA(OMIKRON(liste,DELTA(liste),0))
else false;
fun CONTROL(liste)=
if length(liste)=0
then false
else if length(liste)<3
then true
else OMEGA(liste);
(* überfrüfen des graphen auf zyklen *)
(* ------------------------------------------------------------------ *)
fun kleinsteLaenge(Liste:ebene)=
if length(Liste) > 2
then if #3(nth(Liste,1)) >= #3(nth(Liste,0))
then kleinsteLaenge(tl(Liste))
else kleinsteLaenge(hd(Liste)::(tl(tl(Liste))))
else if #3(nth(Liste,1)) >= #3(nth(Liste,0))
then hd(tl(Liste))
else hd(Liste);
fun SORTLIST(liste:ebene)=
if length(liste)=1
then [nth(liste,0)]
else kleinsteLaenge(liste)::SORTLIST(KILLELEMENT(liste,kleinsteLaenge(liste)));
fun GRAPH(liste:ebene)=
if length(liste)<3
then liste
else if length(liste)=1
then [nth(liste,0)]
else if CONTROL(MINSORT(hd(liste)::GRAPH(tl(liste))))
then hd(liste)::GRAPH(tl(liste))
else GRAPH(tl(liste));
(* bestimmen des minimalen baumes *)
fun KANALBAUER(liste)=GRAPH(SORTLIST(liste));
(* hauptfunktion eingabe eines graphen -> ausgabe des minimalen baumes *)
(* ALPHA(graph,element);
made by Daniel Stebner *)
fun ALPHA(liste:ebene,element:(int*int*int))=
if tl(liste)=[]
then if hd(liste)=element
then []
else [hd(liste)]
else if hd(liste)=element
then tl(liste)
else hd(liste)::ALPHA(tl(liste),element);
(* blaetter(graph,1,1,1);
Diese Funktion liefert alle Blaetter eines Graphen. *)
fun blaetter((baum:ebene),i:int,j:int,s:int) =
if s=1
then
if i<=length(baum) andalso j<=length(baum)
then
if i<>j
then
if ((#1(nth(baum,(j-1))) <> #1(nth(baum,(i-1)))) andalso
(#1(nth(baum,(j-1))) <> #2(nth(baum,(i-1)))))
then
if ((i=length(baum)) orelse
(j=length(baum) andalso i=(length(baum)-1)))
then [nth(baum,j-1)]@blaetter(baum,1,j+1,1)
else blaetter(baum,i+1,j,1)
else blaetter(baum,1,j+1,1)
else blaetter(baum,i+1,j,1)
else blaetter(baum,1,1,2)
else
if i<= length(baum) andalso j<=length(baum)
then
if i<>j
then
if ((#2(nth(baum,(j-1))) <> #1(nth(baum,(i-1)))) andalso
(#2(nth(baum,(j-1))) <> #2(nth(baum,(i-1)))))
then
if ((i=length(baum)) orelse
(j=length(baum) andalso i=(length(baum)-1)))
then [nth(baum,j-1)]@blaetter(baum,1,j+1,2)
else blaetter(baum,i+1,j,2)
else blaetter(baum,1,j+1,2)
else blaetter(baum,i+1,j,2)
else [];
(* adjunkte(graph,punkt,0,0,1,0);
Diese Funktion nacht aus Kannten mit dem gemeinsammen Punkt "punkt"
eine Kannte. *)
fun adjunkte(baum:ebene,p1:int,lange:int,p2:int,i:int,m:int)=
if i<>length(baum) andalso m=0
then
if #1(nth(baum,(i-1)))=p1
then adjunkte(ALPHA(baum,nth(baum,(i-1))),p1,#3(nth(baum,(i-1))),#2(nth(baum,(i-1))),i,1)
else
if #2(nth(baum,(i-1)))=p1
then adjunkte(ALPHA(baum,nth(baum,(i-1))),p1,#3(nth(baum,(i-1))),#1(nth(baum,(i-1))),i,1)
else adjunkte(baum,p1,lange,p2,i+1,0)
else
if i<=length(baum)
then
if #1(nth(baum,(i-1)))=p1
then adjunkte((ALPHA(baum,nth(baum,(i-1)))@
[(#2(nth(baum,(i-1))),p2,(#3(nth(baum,(i-1)))+lange))]),p1,lange,p2,1,1)
else
if #2(nth(baum,(i-1)))=p1
then adjunkte((ALPHA(baum,nth(baum,(i-1)))@
[(#1(nth(baum,(i-1))),p2,(#3(nth(baum,(i-1)))+lange))]),p1,lange,p2,1,1)
else adjunkte(baum,p1,lange,p2,(i+1),1)
else baum;
(* blaetterp(graph,1,1,1,zentrum);
Diese Funktion liefert alle Punkte die an den aeusersten Kanten eines Graphen
liegen und NICHT die aeusersten Punkte sind. Der Punkt "zentrum" wird dabei
uebergangen. *)
fun blaetterp ((baum:ebene),i:int,j:int,s:int,zentrum:int) =
if s=1
then
if i<=length(baum) andalso j<=length(baum)
then
if i<>j
then
if ((#1(nth(baum,(j-1))) <> #1(nth(baum,(i-1)))) andalso
(#1(nth(baum,(j-1))) <> #2(nth(baum,(i-1)))))
then
if ((i=length(baum)) orelse
(j=length(baum) andalso i=(length(baum)-1)))
then
if zentrum = (#2(nth(baum,j-1)))
then blaetterp(baum,1,j+1,1,zentrum)
else [(#2(nth(baum,j-1)))]@blaetterp(baum,1,j+1,1,zentrum)
else blaetterp(baum,i+1,j,1,zentrum)
else blaetterp(baum,1,j+1,1,zentrum)
else blaetterp(baum,i+1,j,1,zentrum)
else blaetterp(baum,1,1,2,zentrum)
else
if i<= length(baum) andalso j<=length(baum)
then
if i<>j
then
if ((#2(nth(baum,(j-1))) <> #1(nth(baum,(i-1)))) andalso
(#2(nth(baum,(j-1))) <> #2(nth(baum,(i-1)))))
then
if ((i=length(baum)) orelse
(j=length(baum) andalso i=(length(baum)-1)))
then
if zentrum = (#1(nth(baum,j-1)))
then blaetterp(baum,1,j+1,2,zentrum)
else [(#1(nth(baum,j-1)))]@blaetterp(baum,1,j+1,2,zentrum)
else blaetterp(baum,i+1,j,2,zentrum)
else blaetterp(baum,1,j+1,2,zentrum)
else blaetterp(baum,i+1,j,2,zentrum)
else [];
(* nurgewicht(graph,punktliste,zentrum)
Diese Funktion liefert die Gesammtkannten von einem Punkt "Zentrum"
eines Graphen. Punkte aus der Liste werden dabei eliminiert. *)
fun nurgewicht((baum:ebene),punkt:int list,zentrum:int)=
if length(punkt)<>0
then
if hd(punkt)<>zentrum
then nurgewicht(adjunkte(baum,hd(punkt),0,0,1,0),tl(punkt),zentrum)
else nurgewicht(baum,tl(punkt),zentrum)
else
if blaetterp(baum,1,1,1,zentrum)<>[]
then nurgewicht(baum,blaetterp(baum,1,1,1,zentrum),zentrum)
else baum;
(* punkteliste(graph);
Diese Funktion liegert eine Liste der Punkte eines Graphen. Dabei
tretten Punkte mehrmals auf. *)
fun punkteliste(baum:ebene)=
if baum <> []
then [(#1(nth(baum,0))),(#2(nth(baum,0)))]@punkteliste(tl(baum))
else [];
(* maxgew(graph,zentrum,0);
Diese Funktion liefert das Blatt mit der groessten Laenge. *)
fun maxgew(baum:ebene,zentrum:int,gew:int)=
if baum <> []
then
if #3(nth(baum,0)) > gew
then maxgew(tl(baum),zentrum,#3(nth(baum,0)))
else maxgew(tl(baum),zentrum,gew)
else (zentrum,gew);
(* gewliste(graph,punkteliste);
Diese Funktion liefert eine Liste aller Punkte "punkteliste" aus einem
Graphen mit der Laenge ihrer maximalen Kannte. (Punkt-Weg-Liste) *)
fun gewliste(baum:ebene,punkte: int list)=
if punkte <> []
then [maxgew(nurgewicht(baum,blaetterp(baum,1,1,1,hd(punkte)),hd(punkte)),
hd(punkte),0)]@
gewliste(baum,tl(punkte))
else [];
(* zentrum(Punkt-Weg-Liste,wo);
Diese Funktion liefert den Punkt mit dem kuerzesten Weg *)
fun zentrum(liste:(int*int)list,wo:(int*int))=
if #1(wo) = 0
then zentrum(tl(liste),hd(liste))
else
if liste <> []
then
if #2(wo) > #2(hd(liste))
then zentrum(tl(liste),hd(liste))
else zentrum(tl(liste),wo)
else (#1(wo));
(* blatt(punkt,graph,1);
Diese Funktion liefert die Blaetter eines Graphen. *)
fun blatt(nr:int,baum:ebene,i:int) =
if i<=length(baum)
then
if ((nr = (#1(nth(baum,i-1)))) orelse (nr = (#2(nth(baum,i-1)))))
then nth(baum,i-1)
else blatt(nr,baum,(i+1))
else (0,0,0);
fun ausgabei(MINSORT(KANALBAUER(baum:ebene))=
(baum,(zentrum(gewliste(baum,punkteliste(baum)),(0,0))));
in ausgabei(baum) end;
(*
Bei dieser Programentwicklung stritten und klopten sich:
Dirk Bußler (sucht äußerst spannende Graphen)
Kay Dittberner (ist auf der verzweifelten Suche nach der Kloake)
Thomas Fromm (archiviert dumme Sprüche für die Nachfolgenden)
Thomas Neumann (sucht den Dirk mit den äußerst spannenden Graphen)
Daniel Stebner (mag keine Zyklen)
*)
