12. maj 2013 /
Zamisel za operacijo sem dobil v R-ju, kjer se je izkazala za precej koristno. V Pajku ima več uporab. Na primer, z njo zaobidemo potrebo po sprotnem vzdrževanju vzporednih podatkovnih objektov pri zaporednih izrezih - za dobljeno končno omrežje ustvarimo pripadajoče razbitje in ga uporabimo za izrez potrebnih vzporednih objektov.
Imejmo omrežji N1 = (V1,L1) in N2 = (V2,L2). Naj bo še name(v) ime/oznaka točke v.
Operacija match(N1,N2) ustvari razbitje p na V1 z vrednostmi p[i]=j , če je name(vi) = name(uj), vi ∈ V1 in uj ∈ V2; oziroma p[i]=0, če name(vi) ∉ V2.
Možna hitra izvedba operacije. Pare (uj,j) damo v kopico H po ključih uj. Nato
for vi ∈ Vi do p[i] = find(vi,H)
find vrne vrednost, ki pripada posameznemu ključu, ali pa 0, če ključa ne najde.
Operacijo match lahko uporabimo tudi pri definiciji operacij matchUnion in matchIntersect.
11. maj 2013
N = (V,L,p,w), kjer je p razbitje in stikalo internal/external.
Iščemo vektor(ja) na zalogi vrednosti razbitja p
tint[i] = max(w(u,v) : p[u]=p[v]=i)
text[i] = max(w(u,v) : p[u]=i ∨ p[v]=i)
Postopek
t <- -∞ for (u,v) ∈ L do i <- p[u]; j <- p[v] if internal then if i=j then if t[i] < w(u,v) then t[i] <- w(u,v) else if t[i] < w(u,v) then t[i] <- w(u,v) if t[j] < w(u,v) then t[j] <- w(u,v)
Pri tej operaciji je lahko problem zelo velika, a pretežno neuporabljena, zaloga vrednosti. Obstajata dve rešitvi - uporabnik naj uporablja operacijo nad stisnjenimi razbitji; druga možnost je, da poleg vektorja dobimo še razbitje - operacijo opravimo na stisnjenem razbitju, razbitje q[i] = k pa pove, da i-ti skupini v stisnjenem razbitju ustreza skupina k v začetnem razbitju.
Podobno operacijo lahko definiramo za min.
Subject: RE: Sunbelt From: "Mrvar, Andrej" <Andrej.Mrvar@fdv.uni-lj.si> Date: Tue, May 14, 2013 11:19 To: "vladimir.batagelj@fmf.uni-lj.si" <vladimir.batagelj@fmf.uni-lj.si>
Sem dodal:
Networks / Match Vertex Labels
Operations / Network+Partition / Internal/External Cluster / [Min Line Value / Max
Line Value]
http://mrvar.fdv.uni-lj.si/aa/pajek32-4g.exe
http://mrvar.fdv.uni-lj.si/aa/pajek64.exe
ali
http://mrvar2.fdv.uni-lj.si/aa/pajek32-4g.exe
http://mrvar2.fdv.uni-lj.si/aa/pajek64.exe
Lp. Andrej