This shows you the differences between two versions of the page.
— |
notes:net:pajmatch [2015/07/16 21:59] (current) vlado created |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== Nekaj operacij za Pajka ====== | ||
+ | ===== Match ===== | ||
+ | |||
+ | 12. maj 2013 / | ||
+ | |||
+ | Zamisel za operacijo sem dobil v R-ju, kjer se je izkazala za precej [[notes:match|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**<sub>1</sub> = (V<sub>1</sub>,L<sub>1</sub>) in **N**<sub>2</sub> = (V<sub>2</sub>,L<sub>2</sub>). Naj bo še name(v) ime/oznaka točke v. | ||
+ | |||
+ | Operacija match(**N**<sub>1</sub>,**N**<sub>2</sub>) ustvari razbitje p na V<sub>1</sub> z vrednostmi p[i]=j , če je name(v<sub>i</sub>) = name(u<sub>j</sub>), v<sub>i</sub> ∈ V<sub>1</sub> in u<sub>j</sub> ∈ V<sub>2</sub>; oziroma p[i]=0, če name(v<sub>i</sub>) ∉ V<sub>2</sub>. | ||
+ | |||
+ | Možna hitra izvedba operacije. Pare (u<sub>j</sub>,j) damo v kopico H po ključih u<sub>j</sub>. Nato | ||
+ | |||
+ | **for** v<sub>i</sub> ∈ V<sub>i</sub> **do** p[i] = find(v<sub>i</sub>,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. | ||
+ | |||
+ | ===== Internal/External cluster max ===== | ||
+ | |||
+ | 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<sub>int</sub>[i] = max(w(u,v) : p[u]=p[v]=i) | ||
+ | |||
+ | t<sub>ext</sub>[i] = max(w(u,v) : p[u]=i ∨ p[v]=i) | ||
+ | |||
+ | Postopek | ||
+ | |||
+ | <code> | ||
+ | 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) | ||
+ | </code> | ||
+ | |||
+ | 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. | ||
+ | |||
+ | ===== Pajek/Andrej ===== | ||
+ | |||
+ | <code> | ||
+ | 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> | ||
+ | </code> | ||
+ | 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 |