Nekaj operacij za Pajka

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 N₁ = (V₁,L₁) in N₂ = (V₂,L₂). Naj bo še name(v) ime/oznaka točke v.

Operacija match(N₁,N₂) ustvari razbitje p na V₁ z vrednostmi p[i]=j , če je name(v_i) = name(u_j), v_i ∈ V₁ in u_j ∈ V₂; oziroma p[i]=0, če name(v_i) ∉ V₂.

Možna hitra izvedba operacije. Pare (u_j,j) damo v kopico H po ključih u_j. Nato

for v_i ∈ V_i do p[i] = find(v_i,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

t_int[i] = max(w(u,v) : p[u]=p[v]=i)

t_ext[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
  vrne dve razbitji (polozaje oznak prvega omrezja v drugem in polozaje oznak drugega omrezja v prvem)
• Operations / Network+Partition / Internal/External Cluster / [Min Line Value / Max Line Value]
  vrne dva vektorja (Internal in External)

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