SN-Evolution-Cut: PS: Ausgebaut.

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 70a7c42..2a8eff5 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -2134,7 +2134,7 @@ Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen.
           35 & 93 & 13 \\
           \rowcolor{green!10}
           36 & 92 & 13 \\
           35 & 93 & 13 \\
           \rowcolor{green!10}
           36 & 92 & 13 \\

-         \rowcolor{green!10!white!95!black}
+          \rowcolor{green!10!white!95!black}

           37 & 92 & 13 \\
           38 & 93 & 13 \\
     \hline
           37 & 92 & 13 \\
           38 & 93 & 13 \\
     \hline


@@ -2572,8 +2572,26 @@ effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
 
 \subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
 
 
 \subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
 

+Eine weitere interessante Eingabe für \textsc{SN-Evolution-Cut} ist das
+\emph{Pairwise-Sorting}-Netzwerk \ps{n}, das \textit{Ian
+Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
+definiert. Einerseits wurde in Abschnitt~\ref{sect:anzahl_schnittmuster}
+gezeigt, dass es für \ps{n} sehr viele \emph{unterschiedliche} Schnittmuster
+gibt. Andererseits sind die Sortiernetzwerke, die nach \textit{Parberrys}
+Methode erzeugt werden, genauso schnell und effizient wie das
+\emph{Odd-Even-Mergesort}-Netzwerk, wenn die Leitungszahl $n = 2^d$ eine
+Zweierpotenz ist.
+

 % Effizienz
 
 % Effizienz
 

+Für viele Kombinationen von \ps{n} und $k$ sind die Sortiernetzwerke, die
+\textsc{SN-Evolution-Cut} ausgibt, weniger effizient als das entsprechende
+\ps{m}-Netzwerk. Für einige Kombinationen werden jedoch auch effizientere
+Netzwerke generiert, beispielsweise für $m = 11$ und $m = 20$. Die Effizienz
+der Sortiernetzwerke, die \textsc{SN-Evolution-Cut} auf Basis des
+\emph{Pairwise-Sorting}-Netzwerks berechnet, ist tabellarisch in
+Tabelle~\ref{tbl:ec-ps-efficiency} dargestellt. 
+

 \begin{table}
   \begin{center}
     \rowcolors{2}{black!5}{}
 \begin{table}
   \begin{center}
     \rowcolors{2}{black!5}{}


@@ -2613,6 +2631,14 @@ effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
 
 % Beispiel Effizienz
 
 
 % Beispiel Effizienz
 

+Zwei Ergebnisse, die effizienter als die entsprechenden
+\emph{Pairwise-Sorting}-Netzwerke sind, zeigt
+Abbildung~\ref{fig:ec-ps-efficient_networks}. Sie erreichen die
+Geschwindigkeit und Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks mit der
+entsprechenden Leitungszahl. Bei größeren Netzwerken, beispielsweise $m = 19$,
+ist dies mit der in Tabelle~\ref{tbl:ec-ps-efficiency} dargestellten Größe der
+Schnittmuster noch nicht zu beobachten.
+

 \begin{figure}
   \centering
   \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 10~Schichten. Das
 \begin{figure}
   \centering
   \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 10~Schichten. Das


@@ -2629,8 +2655,87 @@ effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
   \label{fig:ec-ps-efficient_networks}
 \end{figure}
 
   \label{fig:ec-ps-efficient_networks}
 \end{figure}
 

+% Wie viele Schnitte man braucht.
+
+Bei welchen Parametern \textsc{SN-Evolution-Cut} effiziente
+19-Sortiernetzwerke findet, ist Tabelle~\ref{tbl:ec-ps-19} zu entnehmen. Für
+$n = 31$, $k = 12$ und $n = 32$, $k = 13$ werden 19-Sortiernetzwerke mit der
+selben Effizienz und Geschwindigkeit wie \oes{19} erzeugt. Das
+19-Sortiernetzwerk, das auf diese Art und Weise aus \ps{32} erzeugt wurde, ist
+in Abbildung~\ref{fig:19-ec-from-ps32} dargestellt.
+
+\begin{table}
+  \begin{center}
+    \rowcolors{2}{black!5}{}
+    \begin{tabular}{|r|r|r|}
+    \hline
+    $n$ & Komp. & Schichten \\
+    \hline
+          20 &  97 & 15 \\
+          21 &  96 & 15 \\
+          22 &  96 & 15 \\
+          23 &  97 & 14 \\
+          24 &  96 & 14 \\
+          25 &  93 & 14 \\
+          26 &  92 & 14 \\
+          27 &  94 & 14 \\
+          28 &  94 & 14 \\
+          29 &  92 & 14 \\
+          30 &  92 & 14 \\
+          \rowcolor{green!10!white!95!black}
+          31 &  91 & 14 \\
+          \rowcolor{green!10}
+          32 &  91 & 14 \\
+          33 & 101 & 15 \\
+          34 & 104 & 15 \\
+          35 & 106 & 15 \\
+          36 & 107 & 15 \\
+          37 & 106 & 15 \\
+          38 & 102 & 15 \\
+    \hline
+     \ps{19} &  97 & 15 \\
+    \oes{19} &  91 & 14 \\
+    \hline
+    \end{tabular}
+  \end{center}
+  \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die
+    von \textsc{SN-Evolution-Cut} aus \ps{n}, $n = 20, \dots, 38$ erzeugt
+    wurden.}
+  \label{tbl:ec-ps-19}
+\end{table}
+
+\begin{figure}
+  \begin{center}
+    \input{images/19-ec-from-ps32.tex}
+  \end{center}
+  \caption{Sortiernetzwerk mit 19~Leitungen und 91~Komparatoren in
+    14~Schichten. Das Netzwerk wurde von dem Algorithmus
+    \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk
+    $\operatorname{PS}(32)$ erzeugt.}
+  \label{fig:19-ec-from-ps32}
+\end{figure}
+
+An den Daten in Tabelle~\ref{tbl:ec-ps-19} fällt auf, dass die Effizienz und
+Geschwindigkeit der Ergebnisse für $n > 32$ schlechter werden. Das
+\emph{Pairwise-Sorting}-Netzwerk ist Leitungszahlen, die Zweierpotenzen sind,
+besonders effizient und schnell. Um der Vermutung nachzugehen, dass der
+\textsc{SN-Evolution-Cut}-Algorithmus für $\ps{n = 2^d}$ besonders effiziente
+Schnittmuster findet, wurde \textsc{SN-Evolution-Cut} mit \ps{32} und $k = 1
+\dots 16$ gestartet. Die Ergebnisse sind in Tabelle~\ref{tbl:ec-ps-32}
+zusammengefasst. \todo{Tabelle einfügen.}
+

 % Geschwindigkeit
 
 % Geschwindigkeit
 

+Die Schnittmuster, die \textsc{SN-Evolution-Cut} für das
+\emph{Pairwise-Sorting}-Netzwerk berechnet, können zu schnelleren
+Sortiernetzwerken als \ps{m} führen. Beispielsweise konnte aus \ps{24} ein
+18-Sortiernetzwerk erzeugt werden, das mit 13~Schichten zwei parallele
+Schritte im Vergleich zu \ps{18} einspart. Eine Darstellung dieses
+Sortiernetzwerks befindet sich in Abbildung~\ref{fig:18-ec-from-ps24}. Für
+andere $m$ wurde die Geschwindigkeit des \emph{Pairwise-Sorting}-Netzwerks
+nicht übertroffen und im Fall von $m = 16$ wurde die Geschwindigkeit nicht
+einmal erreicht.
+

 \begin{table}
   \begin{center}
     \rowcolors{2}{black!5}{}
 \begin{table}
   \begin{center}
     \rowcolors{2}{black!5}{}


@@ -2689,13 +2794,12 @@ Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war
 ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
 wie und warum es jede beliebige Eingabe sortiert.
 
 ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
 wie und warum es jede beliebige Eingabe sortiert.
 

-Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian
-Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
-definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit
-$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man
-ein Sortiernetzwerk, das die gleiche Anzahl Komparatoren und Schichten hat wie
-$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Eines dieser
-Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
+Bei dem \emph{Pairwise-Sorting}-Netzwerk $\ps{n=2^d}$ ist das anders. Startet
+man \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
+16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, das die gleiche
+Anzahl Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und
+$\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
+Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.

 
 \begin{figure}
   \begin{center}
 
 \begin{figure}
   \begin{center}


@@ -2708,7 +2812,7 @@ Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
   \label{fig:16-ec-from-ps32}
 \end{figure}
 
   \label{fig:16-ec-from-ps32}
 \end{figure}
 

-Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht
+Obwohl das \emph{Pairwise-Sorting}-Netzwerk den \emph{Odd-Even}-Mischer nicht

 einsetzt und auch nicht auf einem Mischer basiert, ist das
 \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
 Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
 einsetzt und auch nicht auf einem Mischer basiert, ist das
 \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
 Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In

diff --git a/images/19-ec-from-ps32.tex b/images/19-ec-from-ps32.tex
new file mode 100644 (file)
index 0000000..6f91bfe
--- /dev/null
+++ b/images/19-ec-from-ps32.tex
@@ -0,0 +1,385 @@
+\begin{tikzpicture}[auto]
+\node[vertex] (v0) at (0.66,0.00) {};
+\node[vertex] (v1) at (0.66,8.95) {};
+\path[comp] (v0) -- (v1);
+
+\node[vertex] (v2) at (0.86,1.58) {};
+\node[vertex] (v3) at (0.86,3.68) {};
+\path[comp] (v2) -- (v3);
+
+\node[vertex] (v4) at (1.05,2.11) {};
+\node[vertex] (v5) at (1.05,3.16) {};
+\path[comp] (v4) -- (v5);
+
+\node[vertex] (v6) at (1.25,2.63) {};
+\node[vertex] (v7) at (1.25,5.79) {};
+\path[comp] (v6) -- (v7);
+
+\node[vertex] (v8) at (0.86,4.74) {};
+\node[vertex] (v9) at (0.86,6.32) {};
+\path[comp] (v8) -- (v9);
+
+\node[vertex] (v10) at (1.05,5.26) {};
+\node[vertex] (v11) at (1.05,9.47) {};
+\path[comp] (v10) -- (v11);
+
+\node[vertex] (v12) at (0.86,6.84) {};
+\node[vertex] (v13) at (0.86,7.89) {};
+\path[comp] (v12) -- (v13);
+
+\node[vertex] (v14) at (1.25,7.37) {};
+\node[vertex] (v15) at (1.25,8.42) {};
+\path[comp] (v14) -- (v15);
+
+\node[vertex] (v16) at (1.91,0.00) {};
+\node[vertex] (v17) at (1.91,7.89) {};
+\path[comp] (v16) -- (v17);
+
+\node[vertex] (v18) at (2.11,0.53) {};
+\node[vertex] (v19) at (2.11,3.68) {};
+\path[comp] (v18) -- (v19);
+
+\node[vertex] (v20) at (2.30,1.05) {};
+\node[vertex] (v21) at (2.30,8.95) {};
+\path[comp] (v20) -- (v21);
+
+\node[vertex] (v22) at (2.50,1.58) {};
+\node[vertex] (v23) at (2.50,5.79) {};
+\path[comp] (v22) -- (v23);
+
+\node[vertex] (v24) at (2.70,2.63) {};
+\node[vertex] (v25) at (2.70,4.74) {};
+\path[comp] (v24) -- (v25);
+
+\node[vertex] (v26) at (2.11,4.21) {};
+\node[vertex] (v27) at (2.11,9.47) {};
+\path[comp] (v26) -- (v27);
+
+\node[vertex] (v28) at (2.70,5.26) {};
+\node[vertex] (v29) at (2.70,8.42) {};
+\path[comp] (v28) -- (v29);
+
+\node[vertex] (v30) at (2.50,6.84) {};
+\node[vertex] (v31) at (2.50,7.37) {};
+\path[comp] (v30) -- (v31);
+
+\node[vertex] (v32) at (3.36,0.00) {};
+\node[vertex] (v33) at (3.36,5.26) {};
+\path[comp] (v32) -- (v33);
+
+\node[vertex] (v34) at (3.55,0.53) {};
+\node[vertex] (v35) at (3.55,2.11) {};
+\path[comp] (v34) -- (v35);
+
+\node[vertex] (v36) at (3.75,1.05) {};
+\node[vertex] (v37) at (3.75,4.21) {};
+\path[comp] (v36) -- (v37);
+
+\node[vertex] (v38) at (3.55,2.63) {};
+\node[vertex] (v39) at (3.55,6.84) {};
+\path[comp] (v38) -- (v39);
+
+\node[vertex] (v40) at (3.95,3.16) {};
+\node[vertex] (v41) at (3.95,3.68) {};
+\path[comp] (v40) -- (v41);
+
+\node[vertex] (v42) at (3.75,4.74) {};
+\node[vertex] (v43) at (3.75,7.37) {};
+\path[comp] (v42) -- (v43);
+
+\node[vertex] (v44) at (3.36,5.79) {};
+\node[vertex] (v45) at (3.36,6.32) {};
+\path[comp] (v44) -- (v45);
+
+\node[vertex] (v46) at (3.36,7.89) {};
+\node[vertex] (v47) at (3.36,8.42) {};
+\path[comp] (v46) -- (v47);
+
+\node[vertex] (v48) at (3.36,8.95) {};
+\node[vertex] (v49) at (3.36,9.47) {};
+\path[comp] (v48) -- (v49);
+
+\node[vertex] (v50) at (4.61,0.53) {};
+\node[vertex] (v51) at (4.61,1.05) {};
+\path[comp] (v50) -- (v51);
+
+\node[vertex] (v52) at (4.61,1.58) {};
+\node[vertex] (v53) at (4.61,5.26) {};
+\path[comp] (v52) -- (v53);
+
+\node[vertex] (v54) at (4.80,2.11) {};
+\node[vertex] (v55) at (4.80,4.21) {};
+\path[comp] (v54) -- (v55);
+
+\node[vertex] (v56) at (5.00,3.16) {};
+\node[vertex] (v57) at (5.00,8.95) {};
+\path[comp] (v56) -- (v57);
+
+\node[vertex] (v58) at (5.20,3.68) {};
+\node[vertex] (v59) at (5.20,9.47) {};
+\path[comp] (v58) -- (v59);
+
+\node[vertex] (v60) at (4.80,4.74) {};
+\node[vertex] (v61) at (4.80,6.84) {};
+\path[comp] (v60) -- (v61);
+
+\node[vertex] (v62) at (4.61,5.79) {};
+\node[vertex] (v63) at (4.61,7.89) {};
+\path[comp] (v62) -- (v63);
+
+\node[vertex] (v64) at (5.39,6.32) {};
+\node[vertex] (v65) at (5.39,8.42) {};
+\path[comp] (v64) -- (v65);
+
+\node[vertex] (v66) at (6.05,0.00) {};
+\node[vertex] (v67) at (6.05,1.58) {};
+\path[comp] (v66) -- (v67);
+
+\node[vertex] (v68) at (6.25,1.05) {};
+\node[vertex] (v69) at (6.25,2.11) {};
+\path[comp] (v68) -- (v69);
+
+\node[vertex] (v70) at (6.05,3.68) {};
+\node[vertex] (v71) at (6.05,8.95) {};
+\path[comp] (v70) -- (v71);
+
+\node[vertex] (v72) at (6.25,6.32) {};
+\node[vertex] (v73) at (6.25,7.89) {};
+\path[comp] (v72) -- (v73);
+
+\node[vertex] (v74) at (6.25,8.42) {};
+\node[vertex] (v75) at (6.25,9.47) {};
+\path[comp] (v74) -- (v75);
+
+\node[vertex] (v76) at (6.91,1.58) {};
+\node[vertex] (v77) at (6.91,5.79) {};
+\path[comp] (v76) -- (v77);
+
+\node[vertex] (v78) at (7.11,2.11) {};
+\node[vertex] (v79) at (7.11,3.16) {};
+\path[comp] (v78) -- (v79);
+
+\node[vertex] (v80) at (7.11,3.68) {};
+\node[vertex] (v81) at (7.11,4.21) {};
+\path[comp] (v80) -- (v81);
+
+\node[vertex] (v82) at (7.11,5.26) {};
+\node[vertex] (v83) at (7.11,6.32) {};
+\path[comp] (v82) -- (v83);
+
+\node[vertex] (v84) at (7.76,0.00) {};
+\node[vertex] (v85) at (7.76,1.58) {};
+\path[comp] (v84) -- (v85);
+
+\node[vertex] (v86) at (7.96,1.05) {};
+\node[vertex] (v87) at (7.96,2.11) {};
+\path[comp] (v86) -- (v87);
+
+\node[vertex] (v88) at (7.76,3.16) {};
+\node[vertex] (v89) at (7.76,3.68) {};
+\path[comp] (v88) -- (v89);
+
+\node[vertex] (v90) at (7.76,4.21) {};
+\node[vertex] (v91) at (7.76,8.95) {};
+\path[comp] (v90) -- (v91);
+
+\node[vertex] (v92) at (7.96,5.26) {};
+\node[vertex] (v93) at (7.96,5.79) {};
+\path[comp] (v92) -- (v93);
+
+\node[vertex] (v94) at (7.96,6.32) {};
+\node[vertex] (v95) at (7.96,7.89) {};
+\path[comp] (v94) -- (v95);
+
+\node[vertex] (v96) at (8.62,0.00) {};
+\node[vertex] (v97) at (8.62,4.74) {};
+\path[comp] (v96) -- (v97);
+
+\node[vertex] (v98) at (8.82,1.58) {};
+\node[vertex] (v99) at (8.82,6.84) {};
+\path[comp] (v98) -- (v99);
+
+\node[vertex] (v100) at (8.62,5.26) {};
+\node[vertex] (v101) at (8.62,7.37) {};
+\path[comp] (v100) -- (v101);
+
+\node[vertex] (v102) at (9.47,1.58) {};
+\node[vertex] (v103) at (9.47,2.63) {};
+\path[comp] (v102) -- (v103);
+
+\node[vertex] (v104) at (9.47,4.74) {};
+\node[vertex] (v105) at (9.47,5.26) {};
+\path[comp] (v104) -- (v105);
+
+\node[vertex] (v106) at (9.47,5.79) {};
+\node[vertex] (v107) at (9.47,6.84) {};
+\path[comp] (v106) -- (v107);
+
+\node[vertex] (v108) at (9.67,6.32) {};
+\node[vertex] (v109) at (9.67,7.37) {};
+\path[comp] (v108) -- (v109);
+
+\node[vertex] (v110) at (10.33,0.00) {};
+\node[vertex] (v111) at (10.33,1.58) {};
+\path[comp] (v110) -- (v111);
+
+\node[vertex] (v112) at (10.33,2.63) {};
+\node[vertex] (v113) at (10.33,4.74) {};
+\path[comp] (v112) -- (v113);
+
+\node[vertex] (v114) at (10.33,5.26) {};
+\node[vertex] (v115) at (10.33,5.79) {};
+\path[comp] (v114) -- (v115);
+
+\node[vertex] (v116) at (10.33,6.32) {};
+\node[vertex] (v117) at (10.33,6.84) {};
+\path[comp] (v116) -- (v117);
+
+\node[vertex] (v118) at (10.33,7.37) {};
+\node[vertex] (v119) at (10.33,7.89) {};
+\path[comp] (v118) -- (v119);
+
+\node[vertex] (v120) at (10.99,0.53) {};
+\node[vertex] (v121) at (10.99,4.74) {};
+\path[comp] (v120) -- (v121);
+
+\node[vertex] (v122) at (11.18,1.05) {};
+\node[vertex] (v123) at (11.18,5.26) {};
+\path[comp] (v122) -- (v123);
+
+\node[vertex] (v124) at (11.38,2.11) {};
+\node[vertex] (v125) at (11.38,5.79) {};
+\path[comp] (v124) -- (v125);
+
+\node[vertex] (v126) at (11.58,3.16) {};
+\node[vertex] (v127) at (11.58,6.32) {};
+\path[comp] (v126) -- (v127);
+
+\node[vertex] (v128) at (11.78,3.68) {};
+\node[vertex] (v129) at (11.78,6.84) {};
+\path[comp] (v128) -- (v129);
+
+\node[vertex] (v130) at (11.97,4.21) {};
+\node[vertex] (v131) at (11.97,7.37) {};
+\path[comp] (v130) -- (v131);
+
+\node[vertex] (v132) at (10.99,7.89) {};
+\node[vertex] (v133) at (10.99,8.95) {};
+\path[comp] (v132) -- (v133);
+
+\node[vertex] (v134) at (12.63,0.00) {};
+\node[vertex] (v135) at (12.63,1.05) {};
+\path[comp] (v134) -- (v135);
+
+\node[vertex] (v136) at (12.63,1.58) {};
+\node[vertex] (v137) at (12.63,2.11) {};
+\path[comp] (v136) -- (v137);
+
+\node[vertex] (v138) at (12.63,2.63) {};
+\node[vertex] (v139) at (12.63,3.16) {};
+\path[comp] (v138) -- (v139);
+
+\node[vertex] (v140) at (12.63,3.68) {};
+\node[vertex] (v141) at (12.63,4.74) {};
+\path[comp] (v140) -- (v141);
+
+\node[vertex] (v142) at (12.83,4.21) {};
+\node[vertex] (v143) at (12.83,5.26) {};
+\path[comp] (v142) -- (v143);
+
+\node[vertex] (v144) at (12.63,5.79) {};
+\node[vertex] (v145) at (12.63,7.89) {};
+\path[comp] (v144) -- (v145);
+
+\node[vertex] (v146) at (12.83,6.32) {};
+\node[vertex] (v147) at (12.83,8.42) {};
+\path[comp] (v146) -- (v147);
+
+\node[vertex] (v148) at (13.49,0.53) {};
+\node[vertex] (v149) at (13.49,1.58) {};
+\path[comp] (v148) -- (v149);
+
+\node[vertex] (v150) at (13.68,1.05) {};
+\node[vertex] (v151) at (13.68,2.63) {};
+\path[comp] (v150) -- (v151);
+
+\node[vertex] (v152) at (13.49,2.11) {};
+\node[vertex] (v153) at (13.49,3.68) {};
+\path[comp] (v152) -- (v153);
+
+\node[vertex] (v154) at (13.68,3.16) {};
+\node[vertex] (v155) at (13.68,4.21) {};
+\path[comp] (v154) -- (v155);
+
+\node[vertex] (v156) at (13.49,4.74) {};
+\node[vertex] (v157) at (13.49,5.79) {};
+\path[comp] (v156) -- (v157);
+
+\node[vertex] (v158) at (13.68,5.26) {};
+\node[vertex] (v159) at (13.68,6.32) {};
+\path[comp] (v158) -- (v159);
+
+\node[vertex] (v160) at (13.49,6.84) {};
+\node[vertex] (v161) at (13.49,7.89) {};
+\path[comp] (v160) -- (v161);
+
+\node[vertex] (v162) at (13.68,7.37) {};
+\node[vertex] (v163) at (13.68,8.42) {};
+\path[comp] (v162) -- (v163);
+
+\node[vertex] (v164) at (14.34,0.00) {};
+\node[vertex] (v165) at (14.34,0.53) {};
+\path[comp] (v164) -- (v165);
+
+\node[vertex] (v166) at (14.34,1.05) {};
+\node[vertex] (v167) at (14.34,1.58) {};
+\path[comp] (v166) -- (v167);
+
+\node[vertex] (v168) at (14.34,2.11) {};
+\node[vertex] (v169) at (14.34,2.63) {};
+\path[comp] (v168) -- (v169);
+
+\node[vertex] (v170) at (14.34,3.16) {};
+\node[vertex] (v171) at (14.34,3.68) {};
+\path[comp] (v170) -- (v171);
+
+\node[vertex] (v172) at (14.34,4.21) {};
+\node[vertex] (v173) at (14.34,4.74) {};
+\path[comp] (v172) -- (v173);
+
+\node[vertex] (v174) at (14.34,5.26) {};
+\node[vertex] (v175) at (14.34,5.79) {};
+\path[comp] (v174) -- (v175);
+
+\node[vertex] (v176) at (14.34,6.32) {};
+\node[vertex] (v177) at (14.34,6.84) {};
+\path[comp] (v176) -- (v177);
+
+\node[vertex] (v178) at (14.34,7.37) {};
+\node[vertex] (v179) at (14.34,7.89) {};
+\path[comp] (v178) -- (v179);
+
+\node[vertex] (v180) at (14.34,8.42) {};
+\node[vertex] (v181) at (14.34,8.95) {};
+\path[comp] (v180) -- (v181);
+
+\path[edge] (0,0.00) -- (15.00,0.00);
+\path[edge] (0,0.53) -- (15.00,0.53);
+\path[edge] (0,1.05) -- (15.00,1.05);
+\path[edge] (0,1.58) -- (15.00,1.58);
+\path[edge] (0,2.11) -- (15.00,2.11);
+\path[edge] (0,2.63) -- (15.00,2.63);
+\path[edge] (0,3.16) -- (15.00,3.16);
+\path[edge] (0,3.68) -- (15.00,3.68);
+\path[edge] (0,4.21) -- (15.00,4.21);
+\path[edge] (0,4.74) -- (15.00,4.74);
+\path[edge] (0,5.26) -- (15.00,5.26);
+\path[edge] (0,5.79) -- (15.00,5.79);
+\path[edge] (0,6.32) -- (15.00,6.32);
+\path[edge] (0,6.84) -- (15.00,6.84);
+\path[edge] (0,7.37) -- (15.00,7.37);
+\path[edge] (0,7.89) -- (15.00,7.89);
+\path[edge] (0,8.42) -- (15.00,8.42);
+\path[edge] (0,8.95) -- (15.00,8.95);
+\path[edge] (0,9.47) -- (15.00,9.47);
+\end{tikzpicture}