From f1bd5ecf34086b304c06414d39f5dbd48dd2187d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 25 Jan 2007 13:17:04 +0100 Subject: [PATCH] Brouseni, lesteni a zametani kapitoly o dekompozicich. --- 9-decomp/9-decomp.tex | 43 +++++------ 9-decomp/mima.eps | 12 +-- 9-decomp/mima.vrr | 168 +++++++++++++++++++++--------------------- ga.bib | 2 +- 4 files changed, 113 insertions(+), 112 deletions(-) diff --git a/9-decomp/9-decomp.tex b/9-decomp/9-decomp.tex index 81fbf31..f3f2bed 100644 --- a/9-decomp/9-decomp.tex +++ b/9-decomp/9-decomp.tex @@ -18,8 +18,9 @@ komponent souvislosti neorientovan zda dva vrcholy le¾í v~té¾e komponentì. To se hodí v~mnoha algoritmech, kupøíkladu v~Kruskalovì algoritmu pro hledání minimální kostry. -\s{Triviální øe¹ení:} Ka¾dé tøídì pøiøadíme unikátní barvu, kterou obarvíme prvky tøídy. Operace \ -porovnává barvy, operace \ prvky jedné tøídy pøebarvuje. +\s{Triviální øe¹ení:} Prvky ka¾dé tøídy obarvíme unikátní barvou (identifikátorem +tøídy). Operace \ porovnává barvy, \ prvky jedné ze~sjednocovaných +tøíd pøebarvuje. Operace \ tak pracuje v~konstantním èase, \ mù¾e zabrat a¾ lineární èas. Mù¾eme si pomoci tím, ¾e v¾dy pøebarvíme {\I men¹í} ze~sluèovaných ekvivalenèních tøíd (budeme @@ -32,7 +33,7 @@ slo \s{Chytøej¹í øe¹ení:} Ka¾dou tøídu budeme reprezentovat zakoøenìným stromem s~hranami orientovanými smìrem ke~koøeni (jinými slovy pro ka¾dý prvek si pamatujeme jeho otce nebo ¾e je to koøen). \ nalezne koøeny stromù a porovná je, \ pøipojí koøen -jedné tøídy pod koøen druhé. Aby stromy nedegenerovaly, pøidáme dvì podmínky: +jedné tøídy pod koøen druhé. Aby stromy nedegenerovaly, pøidáme dvì pravidla: \itemize\ibull \:{\I Union by rank:} ka¾dý koøen $v$ si pamatuje svùj rank $r(v)$. Pokud spojujeme @@ -48,10 +49,10 @@ rovnou pod ko \s{Pozorování:} Samotné pravidlo Union by rank zajistí, ¾e strom ranku $r$ bude mít hloubku nejvý¹e $r$ a minimálnì $2^r$ vrcholù, tak¾e èasová slo¾itost operací -bude omezena $\O(\log n)$.% +bude omezena $\O(\log n)$ v~nejhor¹ím pøípadì.% \foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila.} -Ve~skuteènosti se popsaná struktura chová daleko lépe: +Amortizovanì se ale popsaná struktura chová daleko lépe: \s{Vìta:} (Tarjan, van Leeuwen \cite{tarjan84setunion}) Kombinace Union by rank a Path compression vede k~amortizované slo¾itosti obou operací $\O(\alpha(n))$, kde $\alpha$ je inverzní Ackermannova funkce.% @@ -63,10 +64,10 @@ p Dále nás bude zajímat speciální varianta Union-Find problemu, v~ní¾ dopøedu známe posloupnost Unionù, èili strom, který spojováním komponent vznikne.\foot{Kdy se to hodí? Tøeba v~Thorupovì lineárním algoritmu \cite{thorup:usssp} na~nejkrat¹í cesty nebo -v~Weiheho takté¾ lineárním algoritmu \cite{weihe:paths} na~hledání hranovì disjunktních +ve~Weiheho takté¾ lineárním algoritmu \cite{weihe:paths} na~hledání hranovì disjunktních cest v~rovinných grafech.} Jiná interpretace tého¾ (jen pozpátku) je dekrementální udr¾ování komponent -souvislosti lesa: na~poèátku je dán les a umíme smazat hranu a otestovat, zda jsou +souvislosti lesa: na~poèátku je dán les, umíme smazat hranu a otestovat, zda jsou dva vrcholy v~tém¾e stromu. Popí¹eme algoritmus, @@ -77,7 +78,7 @@ a \cite{alstrup98marked}. \s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakoøenìný strom $T$ o~$n$ vrcholech definujeme: \itemize\ibull -\:{\I Koøeny mikrostromù} $R$ budou nejvy¹¹í vrcholy, pod~nimi¾ je nejvý¹e $\log n$ listù +\:{\I Koøeny mikrostromù} budou nejvy¹¹í vrcholy v~$T$, pod~nimi¾ je nejvý¹e $\log n$ listù a které nejsou koøenem celého~$T$. \:{\I Mikrostromy} le¾í v~$T$ od~tìchto koøenù ní¾e. \:{\I Spojovací hrany} vedou z~koøenù mikrostromù do~jejich otcù. @@ -143,7 +144,7 @@ p \s{Algoritmus pro mikrostromy:} Po~kompresi cest má ka¾dý mikrostrom nejvý¹e $2\log n$ vrcholù, èili také nejvý¹e tolik hran. Hrany si oèíslujeme pøirozenými èísly, ka¾dou -mno¾inu hran pak mù¾eme reprezentovat $2\log n$-bitovým èíslem a mno¾inové operace +mno¾inu hran pak mù¾eme reprezentovat $(2\log n)$-bitovým èíslem a mno¾inové operace provádìt pomocí bitových v~konstantním èase. Pro ka¾dý mikrostrom si pøedpoèítáme pro v¹echny jeho vrcholy~$v$ mno¾iny~$P_v$ hran le¾ících @@ -160,12 +161,12 @@ p \>$\(x,y):$ \algo -\:$P \leftarrow P_x \mathop{\Delta} P_v$ (mno¾ina hran le¾ících na~cestì z~$x$ do~$y$). +\:$P \leftarrow P_x \mathop{\Delta} P_y$ (mno¾ina hran le¾ících na~cestì z~$x$ do~$y$). \:Pokud $P\setminus F=\emptyset$, le¾í $x$ a $y$ ve~stejnì komponentì, jinak ne. \endalgo -\s{Algoritmus pro celý problém:} Strom rozlo¾íme na~mikrostromy, makrostromy a spojovací -hrany. V~mikrostromech i makrostromech zkomprimujeme cesty. Pro cesty a mikrostromy pou¾ijeme +\s{Algoritmus pro celý problém:} Strom rozlo¾íme na~mikrostromy, makrostrom a spojovací +hrany. V~mikrostromech i makrostromu zkomprimujeme cesty. Pro cesty a mikrostromy pou¾ijeme vý¹e popsané struktury, pro ka¾dou spojovací hranu si budeme pamatovat jen znaèku, zda je pøítomna, a pro makrostrom pøebarvovací strukturu. @@ -190,7 +191,7 @@ zda je p \s{Analýza:} Operace \ trvá konstantní èas, proto¾e se rozlo¾í na~$\O(1)$ \ù v~dílèích strukturách a ka¾dý z~nich trvá konstantnì dlouho. V¹ech $n$ operací \ trvá $\O(n)$, jeliko¾ zpùsobí $\O(n)$ amortizovanì konstantních operací s~mikrostromy, spojovacími -hranami a cestami a $\O(n/\log n)$ operací s~makrostromy, které trvají $\O(\log n)$ amortizovanì +hranami a cestami a $\O(n/\log n)$ operací s~makrostromem, které trvají $\O(\log n)$ amortizovanì ka¾dá.% \foot{To je v~prùmìru $\O(1)$ na~operaci a dokonce i amortizovanì, pokud necháme inicializaci struktury, která je lineární, naspoøit potenciál $\O(n)$, ze~kterého budeme prùbì¾nì platit @@ -204,20 +205,20 @@ nejbli \h{Fredericksonova clusterizace} Mikro/makro-stromová dekompozice není jediný zpùsob, jak stromy rozkládat. Nìkdy -se hodí napøíklad následující my¹lenka: \cite{frederickson91ambivalent} +se hodí napøíklad následující my¹lenka: -\s{Definice:} (Fredericksonova clusterizace) Nech» $G$ je graf s~vrcholy stupòù nejvý¹e~3 +\s{Definice:} {\I (Fredericksonova clusterizace)} Nech» $G$ je graf s~vrcholy stupòù nejvý¹e~3 a $c\ge 1$. Pak $c$-clusterizací grafu $G$ nazveme libovolný rozklad -$G$ na~souvislé podgrafy (clustery) $C_1, C_2, \ldots, C_k$ takový, ¾e platí: +$G$ na~souvislé podgrafy {\I (clustery)} $C_1, C_2, \ldots, C_k$ takový, ¾e platí: \itemize\ibull -\:$\forall v \in V \exists ! i: v \in C_i$. -\:$\forall i: \vert C_i\vert \le c$. -\:$\forall i$ je vnìj¹í stupeò $C_i$ (tj. poèet hran, které vedou mezi $C_i$ a zbytkem grafu) -nejvý¹e~3. Navíc pokud je právì~3, je cluster triviální, èili $\vert C_i \vert = 1$. +\:Ka¾dý vrchol se nachází v~právì jednom clusteru (hrany mohou vést i mezi clustery). +\:Ka¾dý cluster má nejvý¹e~$c$ vrcholù. +\:Vnìj¹í stupeò ka¾dého clusteru (tj. poèet hran, které vedou mezi $C_i$ a zbytkem grafu) +je nejvý¹e~3. Navíc pokud je právì~3, je cluster triviální, èili $\vert C_i \vert = 1$. \:®ádné dva sousední clustery nelze spojit. \endlist -\s{Vìta:} (Frederickson) Ka¾dá $c$-clusterizace grafu $G$ má $\O(V(G)/c)$ clusterù. Existuje +\s{Vìta:} (Frederickson \cite{frederickson91ambivalent}) Ka¾dá $c$-clusterizace grafu $G$ má $\O(V(G)/c)$ clusterù. Existuje algoritmus, který jednu takovou najde v~lineárním èase. \proof První èást rozborem pøípadù, druhá hladovì pomocí DFS. \qed diff --git a/9-decomp/mima.eps b/9-decomp/mima.eps index fade593..a8296e8 100644 --- a/9-decomp/mima.eps +++ b/9-decomp/mima.eps @@ -1,7 +1,7 @@ %!PS-Adobe-3.0 EPSF-3.0 %%Title: mima %%Creator: VRR (http://vrr.ucw.cz/) -%%CreationDate: Wed Jan 24 22:35:30 2007 +%%CreationDate: Thu Jan 25 13:08:39 2007 %%Pages: 1 %%BoundingBox: 0 0 334 77 %%DocumentData: Clean7Bit @@ -1007,7 +1007,7 @@ cp st gr gs -0.000000 slw +0.100000 slw 0 slc 0 slj [] sdh @@ -1059,7 +1059,7 @@ cp st gr gs -0.000000 slw +0.100000 slw 0 slc 0 slj [] sdh @@ -1111,7 +1111,7 @@ cp st gr gs -0.000000 slw +0.100000 slw 0 slc 0 slj [] sdh @@ -1293,7 +1293,7 @@ cp st gr gs -0.000000 slw +0.100000 slw 0 slc 0 slj [] sdh @@ -1449,7 +1449,7 @@ cp st gr gs -0.000000 slw +0.100000 slw 0 slc 0 slj [] sdh diff --git a/9-decomp/mima.vrr b/9-decomp/mima.vrr index 82bded2..fc8b8a4 100644 --- a/9-decomp/mima.vrr +++ b/9-decomp/mima.vrr @@ -1,90 +1,90 @@ - (document 0.6 ( (filename "/hdb1/home/mj/tex/ga/10-decomp/mima.vrr") (name "Untitled 1")) ( + (document 0.6 ( (filename "/home/mares/tex/ga/9-decomp/mima.vrr") (name "Untitled 1")) ( (page ( (tex_footer "\\bye ") (tex_header "\\nopagenumbers\\vglue0pt ") (name "mima")) ( - (segment (coords 122.063011169434 -12.7523431777954) (coords 124.563011169434 -7.75234317779541) ( (id 140471432) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (coords 112.063011169434 -12.7523431777954) (coords 114.563011169434 -7.75234317779541) ( (id 140438448) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (coords 102.063011169434 -12.7523431777954) (coords 104.563011169434 -7.75234317779541) ( (id 140406592) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (coords 92.0630111694336 -12.7523431777954) (coords 94.5630111694336 -7.75234317779541) ( (id 140334216) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (coords 65.0 -10.0) (coords 70.0 -5.0) ( (id 139239184) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (coords 40.0 -10.0) (coords 45.0 -5.0) ( (id 139067968) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.300000011920929) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (coords 21.2842693328857 8.13515663146973) (coords 11.2842655181885 -6.86484384536743) ( (id 138656184) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 140471432) (coords 127.063011169434 -12.7523431777954) ( (id 140486320) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 140438448) (coords 117.063011169434 -12.7523431777954) ( (id 140450312) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 140438448) (coords 119.563011169434 -2.75234317779541) ( (id 140622488) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 140406592) (coords 107.063011169434 -12.7523431777954) ( (id 140328600) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 140334216) (coords 97.0630111694336 -12.7523431777954) ( (id 140352152) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 140334216) (coords 99.5630111694336 -2.75234317779541) ( (id 140577544) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (start 139239184) (coords 60.0 -15.0) ( (id 139377504) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (start 139239184) (coords 70.0 -15.0) ( (id 138519696) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 139239184) (coords 75.0 0.0) ( (id 139245960) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (coords 35.0 -15.0) (start 139067968) ( (id 139605896) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.300000011920929) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 139067968) (coords 50.0 0.0) ( (id 139108192) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.300000011920929) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (start 138656184) (coords 26.2842655181885 -6.86484384536743) ( (id 138731504) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (start 138656184) (coords 16.2842655181885 -6.86484384536743) ( (id 138680600) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 140622488) (coords 114.563011169434 2.24765682220459) ( (id 140729096) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 140577544) (end 140406592) ( (id 140591752) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (start 138519696) (coords 65.0 -15.0) ( (id 137618520) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (segment (start 139245960) (coords 75.0 -10.0) ( (id 139284744) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 139245960) (coords 80.0 5.0) ( (id 139256968) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.300000011920929) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 139108192) (coords 55.0 5.0) ( (id 139117576) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.300000011920929) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (start 138731504) (coords 31.2842655181885 -6.86484384536743) ( (id 138758920) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (start 138680600) (coords 21.2842655181885 -6.86484384536743) ( (id 138708872) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (start 140591752) (coords 104.563011169434 2.24765682220459) ( (id 140680200) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (start 139256968) (coords 80.0 -5.0) ( (id 139311752) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 139256968) (coords 85.0 10.0) ( (id 139244168) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.300000011920929) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 139256968) (coords 85.0 0.0) ( (id 139330440) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 139117576) (coords 60.0 10.0) ( (id 138822248) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 140680200) (coords 109.563011169434 7.24765682220459) ( (id 140751752) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 139244168) (coords 90.0 5.0) ( (id 139332104) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 140751752) (end 140729096) ( (id 140763440) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (start 140763440) (coords 109.563011169434 2.24765682220459) ( (id 140792000) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (segment (end 140792000) (coords 107.063011169434 -2.75234317779541) ( (id 140806424) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (coords 122.063011169434 -12.7523431777954) (coords 124.563011169434 -7.75234317779541) ( (id 137806000) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (coords 112.063011169434 -12.7523431777954) (coords 114.563011169434 -7.75234317779541) ( (id 137806632) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (coords 102.063011169434 -12.7523431777954) (coords 104.563011169434 -7.75234317779541) ( (id 137807400) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (coords 92.0630111694336 -12.7523431777954) (coords 94.5630111694336 -7.75234317779541) ( (id 137808168) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (coords 65.0 -10.0) (coords 70.0 -5.0) ( (id 137805712) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (coords 40.0 -10.0) (coords 45.0 -5.0) ( (id 137808648) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.300000011920929) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (coords 21.2842693328857 8.13515663146973) (coords 11.2842655181885 -6.86484384536743) ( (id 137809704) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137806000) (coords 127.063011169434 -12.7523431777954) ( (id 137810472) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137806632) (coords 117.063011169434 -12.7523431777954) ( (id 137811240) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137806632) (coords 119.563011169434 -2.75234317779541) ( (id 137806208) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137807400) (coords 107.063011169434 -12.7523431777954) ( (id 137812008) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137808168) (coords 97.0630111694336 -12.7523431777954) ( (id 137812776) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137808168) (coords 99.5630111694336 -2.75234317779541) ( (id 137813544) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (start 137805712) (coords 60.0 -15.0) ( (id 137806976) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (start 137805712) (coords 70.0 -15.0) ( (id 137814312) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137805712) (coords 75.0 0.0) ( (id 137815080) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (coords 35.0 -15.0) (start 137808648) ( (id 137815848) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.300000011920929) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137808648) (coords 50.0 0.0) ( (id 137816616) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.300000011920929) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (start 137809704) (coords 26.2842655181885 -6.86484384536743) ( (id 137807744) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (start 137809704) (coords 16.2842655181885 -6.86484384536743) ( (id 137817384) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137806208) (coords 114.563011169434 2.24765682220459) ( (id 137818152) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137813544) (end 137807400) ( (id 137818920) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (start 137814312) (coords 65.0 -15.0) ( (id 137819688) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (segment (start 137815080) (coords 75.0 -10.0) ( (id 137820456) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137815080) (coords 80.0 5.0) ( (id 137821224) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.300000011920929) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137816616) (coords 55.0 5.0) ( (id 137809280) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.300000011920929) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (start 137807744) (coords 31.2842655181885 -6.86484384536743) ( (id 137802544) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (start 137817384) (coords 21.2842655181885 -6.86484384536743) ( (id 137808376) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (start 137818920) (coords 104.563011169434 2.24765682220459) ( (id 137820664) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (start 137821224) (coords 80.0 -5.0) ( (id 137820832) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137821224) (coords 85.0 10.0) ( (id 137819128) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.300000011920929) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137821224) (coords 85.0 0.0) ( (id 137819296) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137809280) (coords 60.0 10.0) ( (id 137819896) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137820664) (coords 109.563011169434 7.24765682220459) ( (id 137820064) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137819128) (coords 90.0 5.0) ( (id 137813752) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137820064) (end 137818152) ( (id 137813936) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (start 137813936) (coords 109.563011169434 2.24765682220459) ( (id 137812216) (stroke-style (stroke-style dotted)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (segment (end 137812216) (coords 107.063011169434 -2.75234317779541) ( (id 137812400) (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) (top-level-group ( (name "top-level-group")) ( - (decorator-point (end 137618520) 0 1.0 0.0 ( (stroke-style (stroke-style dashed)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) 137618520 - (decorator-point (start 138708872) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (decorator-point (end 138758920) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 138731504) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 138708872) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 138680600) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 138656184) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 138822248) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (decorator-point (end 139117576) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (start 139117576) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 139067968) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 139605896) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (start 139605896) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 139332104) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 139244168) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (decorator-point (end 139330440) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (start 139330440) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (decorator-point (end 139311752) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (start 139311752) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (decorator-point (end 139284744) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 139239184) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (start 139239184) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 138519696) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 139377504) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (start 140591752) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 140680200) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (decorator-point (end 140751752) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (decorator-point (end 137819688) 0 1.0 0.0 ( (stroke-style (stroke-style dashed)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) 137819688 + (decorator-point (start 137808376) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (decorator-point (end 137802544) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137807744) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137808376) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137817384) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137809704) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137819896) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (decorator-point (end 137809280) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (start 137809280) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137808648) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137815848) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (start 137815848) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137813752) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137819128) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (decorator-point (end 137819296) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (start 137819296) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (decorator-point (end 137820832) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (start 137820832) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (decorator-point (end 137820456) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137805712) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (start 137805712) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137814312) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137806976) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (start 137818920) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137820664) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (decorator-point (end 137820064) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) (decorator-point (coords 112.063011169434 -2.75234317779541) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 140806424) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 140792000) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 140763440) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) - (decorator-point (start 140729096) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (start 140486320) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 140486320) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (start 140471432) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (start 140450312) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 140450312) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (start 140438448) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 140334216) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 140406592) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 140328600) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (start 140406592) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (end 140352152) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (decorator-point (start 140334216) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) - (segment (end 140792000) (coords 112.063011169434 -2.75234317779541) ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) 140806424 140792000 140763440 140751752 140729096 140680200 - (segment (end 140622488) (end 140471432) ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) 140622488 140591752 140577544 140486320 140471432 140450312 140438448 140328600 140406592 140352152 140334216 139605896 138519696 139377504 139332104 139330440 139311752 139284744 139244168 139256968 139245960 139239184 138822248 139117576 139108192 139067968 138758920 138731504 138708872 138680600 138656184)))))) \ No newline at end of file + (decorator-point (end 137812400) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137812216) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137813936) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) + (decorator-point (start 137818152) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (start 137810472) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137810472) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (start 137806000) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (start 137811240) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137811240) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (start 137806632) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137808168) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137807400) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137812008) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (start 137807400) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (end 137812776) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (decorator-point (start 137808168) 0 1.0 0.0 ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.0) (stroke-color (rgb 0 0 0)) (fill-color (rgb 0 0 0)) (invisible #f) (name "noname"))) + (segment (end 137812216) (coords 112.063011169434 -2.75234317779541) ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) 137812400 137812216 137813936 137820064 137818152 137820664 + (segment (end 137806208) (end 137806000) ( (stroke-style (stroke-style solid)) (stroke-cap (cap-style butt)) (stroke-join (join-style miter)) (stroke-width 0.100000001490116) (stroke-color (rgb 0 0 0)) (fill-color (rgb 255 255 255)) (invisible #f) (name "noname"))) 137806208 137818920 137813544 137810472 137806000 137811240 137806632 137812008 137807400 137812776 137808168 137815848 137814312 137806976 137813752 137819296 137820832 137820456 137819128 137821224 137815080 137805712 137819896 137809280 137816616 137808648 137802544 137807744 137808376 137817384 137809704)))))) \ No newline at end of file diff --git a/ga.bib b/ga.bib index 31c389a..792e03a 100644 --- a/ga.bib +++ b/ga.bib @@ -451,7 +451,7 @@ } @article{ weihe:paths, - title={{Edge-Disjoint (s, t)-Paths in Undirected Planar Graphs in Linear Time}}, + title={{Edge-Disjoint $(s,t)$-Paths in Undirected Planar Graphs in Linear Time}}, author={Weihe, K.}, journal={Journal of Algorithms}, volume={23}, -- 2.39.2