Random Walks in Graphen
Wir simulieren einen Random Walk in einem Graphen. Dabei startet man in einem vorgegebenen Knoten. In jedem Schritt wird zufällig eine aus diesem Knoten ausgehende Kante gewählt, die dann zum benachbarten Knoten verfolgt wird. Dies wird n-mal Iteriert. Die Wahrscheinlichkeiten, mit denen die ausgehenden Kanten gewählt werden können dabei über Kantengewichte bestimmt werden.
Das Ergebnis der Simulation wird Graphisch dargestellt, in dem die Kanten entsprechend der Häufigkeit, mit der sie gewählt wurden unterschiedlich dick und farbig markiert werden.
Die Umsetzung dieser Simulation erfolgt in zwei Schritten.
Zunächst schreiben wir im Initialisierungs-Bereich einige benötigte Funktionen zur Simulation und Visualisierung:
Nun bestimmen wir im Bereich Draw noch den Wert der Animation, den wir aus unserem "Schieberegler" bestimmen:
und weisen den Button im Inspector an, die Simulation zu starten, sobald er gedrückt wird:
Das Ergebnis der Simulation wird Graphisch dargestellt, in dem die Kanten entsprechend der Häufigkeit, mit der sie gewählt wurden unterschiedlich dick und farbig markiert werden.
Die Umsetzung dieser Simulation erfolgt in zwei Schritten.
Zunächst schreiben wir im Initialisierungs-Bereich einige benötigte Funktionen zur Simulation und Visualisierung:
importurl("http://www.math.tu-berlin.de/didaktik/visage/software/applets/visage.vgl");
animation=1;
displayvisits(objects,size):={
visits=apply(objects,getMark(#,"visits"));
n=sum(visits);
mean=n/length(objects);
min = min(visits);
max = max(visits);
forall(1..length(objects),i,
v=visits_i;
o=objects_i;
o.color=if(v<mean,
[1.0-(v-min)/(mean-min+1),0,(v-min)/(mean-min+1)],
[0,1.0-(max-v)/(max-mean+1),(max-v)/(max-mean+1)]);
o.size=1+((size-1)*v)/max;
);
};
blink(olist,n):={
oldcolor=apply(olist,#.color);
repeat(n,
forall(olist,#.color=[1,1,1]);
repaint();
forall(1..length(olist),(olist_#).color=oldcolor_#);
repaint();
);
};
randomedge(edges,byweight):={
if(byweight,
weights=apply(edges,getweight(#));
number=random(sum(weights));
w=0;
edge=edges_1;
forall(1..length(edges),i,
if(w<=number & number<=w+weights_i,
edge=edges_i;
);
w=w+weights_i;
);
,
index=ceil(random(length(edges)));
edge=edges_index;
);
edge;
};
randomWalk():={
nodes=allvertices();
edges=alledges();
// reset graphics
forall(nodes,#.color=[0,1,0];#.size=5);
forall(edges,#.color=[0,0,1];#.size=2);
repaint();
iterations=parse(Text1.val);
actualnode=element(Text3.val);
walk=[actualnode];
forall(nodes,setMark(#,"visits",0));
forall(edges,setMark(#,"visits",0));
repeat(iterations,
outedges=incidentedges(actualnode);
if(length(outedges)>0,
edge=randomedge(outedges,true);
setMark(edge,"visits",getMark(edge,"visits")+1);
if(animation>=3,
blink([edge,actualnode],5);
);
exit=incidentvertices(edge)--[actualnode];
,
exit=actualnode;
);
setMark(exit_1,"visits",getMark(exit_1,"visits")+1);
actualnode=exit_1;
walk=walk:>actualnode;
if(animation>=2,
displayvisits(nodes,10);
displayvisits(edges,7);
repaint();
);
);
if(animation>=1,
displayvisits(nodes,10);
displayvisits(edges,7);
,
println(apply(walk,#.label));
println(apply(1..length(nodes),[(nodes_#).label,getMark(nodes_#,"visits")]));
);
};
Nun bestimmen wir im Bereich Draw noch den Wert der Animation, den wir aus unserem "Schieberegler" bestimmen:
// Level of Animation:
animation=round(3*(LOA.x-LOAL.x)/(LOAR.x-LOAL.x));
LOA.x=LOAL.x+(LOAR.x-LOAL.x)*animation/3;
Text5.val="Level of animation: "+animation;
und weisen den Button im Inspector an, die Simulation zu starten, sobald er gedrückt wird:
randomWalk();