From dddb01e2bbb4b360cee39610832675d7294d86e4 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Sun, 1 Mar 2015 19:21:59 +0100 Subject: [PATCH] dp --- thesis2/3.methods.tex | 18 ++-- thesis2/appoverview.eps | 148 +++++++++++++------------- thesis2/backend.eps | 166 ++++++++++++++--------------- thesis2/nddawg.eps | 160 ++++++++++++++-------------- thesis2/nodelistexample.eps | 204 ++++++++++++++++++------------------ thesis2/thesis.bib | 24 +++++ 6 files changed, 375 insertions(+), 345 deletions(-) diff --git a/thesis2/3.methods.tex b/thesis2/3.methods.tex index 4fd871d..be8c4b4 100644 --- a/thesis2/3.methods.tex +++ b/thesis2/3.methods.tex @@ -86,11 +86,9 @@ characters from the entry. The first algorithm to generate DAWGs from words was proposed by Hopcroft et al\cite{Hopcroft1971}. It is an incremental approach in generating the graph. Meaning that entry by entry the graph will be expanded. Hopcrofts algorithm has the constraint of lexicographical -ordering. Later on Daciuk et al.\cite{Daciuk2000} improved on the original -algorithm and their algorithm is the algorithm we used to minimize our DAWGs. A -minimal graph is a graph $G$ for which there is no graph $G'$ that has less -paths and $\mathcal{L}(G)=\mathcal{L}(G')$ where $\mathcal{L}(G)$ is the set -of all words present in the DAWG. +ordering. Later on Daciuk et al.\cite{Daciuk1998}\cite{Daciuk2000} improved on +the original algorithm and their algorithm is the algorithm we used to generate +minimal DAWGs from the node lists. \subsection{Algorithm} The algorithm of building DAWGs is an iterative process that goes roughly in @@ -259,5 +257,13 @@ choice. \caption{Example non determinism} \end{figure} -\subsection{How to choose path} +\subsection{Minimality and non-determinism} +The Myhill-Nerode theorem~\cite{Hopcroft1979} states that for every number of +graphs accepting the same language there is a single graph with the least +amount of states. Mihov\cite{Mihov1998} has proven that the algorithm is +minimal in its original form. Our program converts the node-lists to DAWGs that +can possibly contain non deterministic nodes and therefore one can argue about +the minimality. Due to the nature of the determinism this is not the case. The +non determinism is only visible when matching the data and not in the real +graph since in the real graph we ... diff --git a/thesis2/appoverview.eps b/thesis2/appoverview.eps index c6f30bb..2149cdc 100644 --- a/thesis2/appoverview.eps +++ b/thesis2/appoverview.eps @@ -2,7 +2,7 @@ %%Creator: graphviz version 2.38.0 (20140413.2041) %%Title: %3 %%Pages: 1 -%%BoundingBox: 36 36 766 153 +%%BoundingBox: 36 36 642 153 %%EndComments save %%BeginProlog @@ -179,211 +179,211 @@ def %%EndSetup setupLatin1 %%Page: 1 1 -%%PageBoundingBox: 36 36 766 153 +%%PageBoundingBox: 36 36 642 153 %%PageOrientation: Portrait 0 0 1 beginpage gsave -36 36 730 117 boxprim clip newpath +36 36 606 117 boxprim clip newpath 1 1 set_scale 0 rotate 40 40 translate % User gsave 1 setlinewidth 0 0 0 nodecolor -32.5 91 32.49 18 ellipse_path stroke +27.3 91 27.1 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -15.5 87.3 moveto 34 (User) alignedtext +14.3 87.3 moveto 26 (User) alignedtext grestore % Frontend gsave 1 setlinewidth 0 0 0 nodecolor -154.5 91 53.89 18 ellipse_path stroke +132.3 91 42.49 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -121 87.3 moveto 67 (Frontend) alignedtext +107.8 87.3 moveto 49 (Frontend) alignedtext grestore % User->Frontend gsave 1 setlinewidth 0 0 0 edgecolor -newpath 65.38 91 moveto -73.71 91 82.04 91 90.38 91 curveto +newpath 54.78 91 moveto +63.1 91 71.43 91 79.75 91 curveto stroke 0 0 0 edgecolor -newpath 90.54 94.5 moveto -100.54 91 lineto -90.54 87.5 lineto +newpath 79.9 94.5 moveto +89.9 91 lineto +79.9 87.5 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 90.54 94.5 moveto -100.54 91 lineto -90.54 87.5 lineto +newpath 79.9 94.5 moveto +89.9 91 lineto +79.9 87.5 lineto closepath stroke grestore % Backend gsave 1 setlinewidth 0 0 0 nodecolor -295.5 91 51.19 18 ellipse_path stroke +251.3 91 41.69 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -264 87.3 moveto 63 (Backend) alignedtext +227.3 87.3 moveto 48 (Backend) alignedtext grestore % Frontend->Backend gsave 1 setlinewidth 0 0 0 edgecolor -newpath 208.47 91 moveto -216.85 91 225.23 91 233.61 91 curveto +newpath 174.6 91 moveto +182.91 91 191.21 91 199.52 91 curveto stroke 0 0 0 edgecolor -newpath 233.83 94.5 moveto -243.83 91 lineto -233.83 87.5 lineto +newpath 199.65 94.5 moveto +209.65 91 lineto +199.65 87.5 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 233.83 94.5 moveto -243.83 91 lineto -233.83 87.5 lineto +newpath 199.65 94.5 moveto +209.65 91 lineto +199.65 87.5 lineto closepath stroke grestore % Crawler gsave 1 setlinewidth 0 0 0 nodecolor -512.5 91 48.19 18 ellipse_path stroke +425.3 91 38.99 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -483.5 87.3 moveto 58 (Crawler) alignedtext +403.3 87.3 moveto 44 (Crawler) alignedtext grestore % Backend->Crawler gsave 1 setlinewidth 0 0 0 edgecolor -newpath 346.92 91 moveto -379.07 91 420.55 91 453.96 91 curveto +newpath 292.97 91 moveto +317.92 91 349.75 91 375.95 91 curveto stroke 0 0 0 edgecolor -newpath 454.05 94.5 moveto -464.04 91 lineto -454.04 87.5 lineto +newpath 376.05 94.5 moveto +386.05 91 lineto +376.05 87.5 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 454.05 94.5 moveto -464.04 91 lineto -454.04 87.5 lineto +newpath 376.05 94.5 moveto +386.05 91 lineto +376.05 87.5 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -355.62 97.8 moveto 100 (Crawler spec.) alignedtext +301.6 97.8 moveto 76 (Crawler spec.) alignedtext grestore % Database gsave 1 setlinewidth 0 0 0 nodecolor -668.5 91 53.89 18 ellipse_path stroke +555.3 91 42.79 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -635 87.3 moveto 67 (Database) alignedtext +530.3 87.3 moveto 50 (Database) alignedtext grestore % Crawler->Database gsave 1 setlinewidth 0 0 0 edgecolor -newpath 561 91 moveto -574.6 91 589.61 91 603.99 91 curveto +newpath 464.3 91 moveto +476.22 91 489.54 91 502.23 91 curveto stroke 0 0 0 edgecolor -newpath 604.31 94.5 moveto -614.31 91 lineto -604.31 87.5 lineto +newpath 502.23 94.5 moveto +512.23 91 lineto +502.23 87.5 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 604.31 94.5 moveto -614.31 91 lineto -604.31 87.5 lineto +newpath 502.23 94.5 moveto +512.23 91 lineto +502.23 87.5 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -569.57 97.8 moveto 36 (XML) alignedtext +472.85 97.8 moveto 31 (XML) alignedtext grestore % Source gsave 1 setlinewidth 0 0 0 nodecolor -512.5 18 42.79 18 ellipse_path stroke +425.3 18 35.19 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -487.5 14.3 moveto 50 (Source) alignedtext +406.3 14.3 moveto 38 (Source) alignedtext grestore % Crawler->Source gsave 1 setlinewidth 0 0 0 edgecolor -newpath 506.62 72.81 moveto -505.78 64.79 505.55 55.05 505.92 46.07 curveto +newpath 419.46 73.17 moveto +418.6 65.16 418.35 55.36 418.71 46.32 curveto stroke 0 0 0 edgecolor -newpath 509.41 46.25 moveto -506.64 36.03 lineto -502.43 45.75 lineto +newpath 422.21 46.42 moveto +419.42 36.2 lineto +415.23 45.93 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 509.41 46.25 moveto -506.64 36.03 lineto -502.43 45.75 lineto +newpath 422.21 46.42 moveto +419.42 36.2 lineto +415.23 45.93 lineto closepath stroke grestore % Source->Frontend gsave 1 setlinewidth 0 0 0 edgecolor -newpath 473.92 26.34 moveto -420.37 36.57 320.5 55.8 235.5 73 curveto -226.8 74.76 217.58 76.66 208.61 78.53 curveto +newpath 393.97 26.42 moveto +350.48 36.74 269.36 56.08 200.3 73 curveto +192.98 74.79 185.23 76.71 177.68 78.59 curveto stroke 0 0 0 edgecolor -newpath 207.69 75.15 moveto -198.61 80.62 lineto -209.12 82 lineto +newpath 176.78 75.21 moveto +167.93 81.03 lineto +178.48 82 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 207.69 75.15 moveto -198.61 80.62 lineto -209.12 82 lineto +newpath 176.78 75.21 moveto +167.93 81.03 lineto +178.48 82 lineto closepath stroke grestore % Source->Crawler gsave 1 setlinewidth 0 0 0 edgecolor -newpath 518.36 36.03 moveto -519.21 44.03 519.45 53.77 519.08 62.75 curveto +newpath 431.18 36.2 moveto +432.02 44.27 432.25 54.08 431.87 63.1 curveto stroke 0 0 0 edgecolor -newpath 515.59 62.59 moveto -518.38 72.81 lineto -522.57 63.08 lineto +newpath 428.37 62.95 moveto +431.14 73.17 lineto +435.35 63.45 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 515.59 62.59 moveto -518.38 72.81 lineto -522.57 63.08 lineto +newpath 428.37 62.95 moveto +431.14 73.17 lineto +435.35 63.45 lineto closepath stroke grestore endpage diff --git a/thesis2/backend.eps b/thesis2/backend.eps index 13d73c8..5b6bd39 100644 --- a/thesis2/backend.eps +++ b/thesis2/backend.eps @@ -2,7 +2,7 @@ %%Creator: graphviz version 2.38.0 (20140413.2041) %%Title: %3 %%Pages: 1 -%%BoundingBox: 36 36 1215 152 +%%BoundingBox: 36 36 1045 152 %%EndComments save %%BeginProlog @@ -179,232 +179,232 @@ def %%EndSetup setupLatin1 %%Page: 1 1 -%%PageBoundingBox: 36 36 1215 152 +%%PageBoundingBox: 36 36 1045 152 %%PageOrientation: Portrait 0 0 1 beginpage gsave -36 36 1179 116 boxprim clip newpath +36 36 1009 116 boxprim clip newpath 1 1 set_scale 0 rotate 40 40 translate % q0 % HTML data gsave 1 setlinewidth 0 0 0 nodecolor -259.34 18 64.19 18 ellipse_path stroke +223.3 18 53.09 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -217.84 14.3 moveto 83 (HTML data) alignedtext +190.3 14.3 moveto 66 (HTML data) alignedtext grestore % q0->HTML data gsave 1 setlinewidth 0 0 0 edgecolor -newpath 54.42 18 moveto -86 18 140.15 18 184.72 18 curveto +newpath 54.2 18 moveto +81.07 18 123.86 18 159.54 18 curveto stroke 0 0 0 edgecolor -newpath 184.94 21.5 moveto -194.94 18 lineto -184.94 14.5 lineto +newpath 159.88 21.5 moveto +169.88 18 lineto +159.88 14.5 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 184.94 21.5 moveto -194.94 18 lineto -184.94 14.5 lineto +newpath 159.88 21.5 moveto +169.88 18 lineto +159.88 14.5 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -72 21.8 moveto 105 (From frontend) alignedtext +72 21.8 moveto 80 (From frontend) alignedtext grestore % q1 % Table rows gsave 1 setlinewidth 0 0 0 nodecolor -421.78 47 61.19 18 ellipse_path stroke +363.64 47 50.09 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -382.78 43.3 moveto 78 (Table rows) alignedtext +333.14 43.3 moveto 61 (Table rows) alignedtext grestore % HTML data->Table rows gsave 1 setlinewidth 0 0 0 edgecolor -newpath 313.77 27.66 moveto -328.28 30.28 344.12 33.14 359.06 35.84 curveto +newpath 269.21 27.42 moveto +282.16 30.13 296.41 33.12 309.8 35.92 curveto stroke 0 0 0 edgecolor -newpath 358.76 39.35 moveto -369.23 37.68 lineto -360.01 32.46 lineto +newpath 309.32 39.4 moveto +319.83 38.03 lineto +310.76 32.55 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 358.76 39.35 moveto -369.23 37.68 lineto -360.01 32.46 lineto +newpath 309.32 39.4 moveto +319.83 38.03 lineto +310.76 32.55 lineto closepath stroke grestore % Dictionary gsave 1 setlinewidth 0 0 0 nodecolor -944.77 44 59.59 18 ellipse_path stroke +802.47 44 48.19 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -906.77 40.3 moveto 76 (Dictionary) alignedtext +773.47 40.3 moveto 58 (Dictionary) alignedtext grestore % HTML data->Dictionary gsave 1 setlinewidth 0 0 0 edgecolor -newpath 315.88 9.2 moveto -346.7 5.05 385.77 1 420.78 1 curveto -420.78 1 420.78 1 811.92 1 curveto -844.37 1 879.2 12.92 904.91 24.21 curveto +newpath 270.55 9.45 moveto +297.35 5.22 331.78 1 362.64 1 curveto +362.64 1 362.64 1 686.53 1 curveto +715.05 1 745.18 12.76 767.43 23.98 curveto stroke 0 0 0 edgecolor -newpath 903.74 27.52 moveto -914.29 28.48 lineto -906.63 21.15 lineto +newpath 765.97 27.17 moveto +776.45 28.72 lineto +769.23 20.97 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 903.74 27.52 moveto -914.29 28.48 lineto -906.63 21.15 lineto +newpath 765.97 27.17 moveto +776.45 28.72 lineto +769.23 20.97 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -519.88 4.8 moveto 127 (Description fields) alignedtext +450.68 4.8 moveto 97 (Description fields) alignedtext grestore % Node lists gsave 1 setlinewidth 0 0 0 nodecolor -583.38 90 57.69 18 ellipse_path stroke +499.18 90 46.29 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -546.88 86.3 moveto 73 (Node lists) alignedtext +471.68 86.3 moveto 55 (Node lists) alignedtext grestore % Table rows->Node lists gsave 1 setlinewidth 0 0 0 edgecolor -newpath 467.66 59.09 moveto -486.83 64.26 509.34 70.32 529.32 75.71 curveto +newpath 401.48 58.86 moveto +417.49 64.02 436.38 70.1 453.21 75.52 curveto stroke 0 0 0 edgecolor -newpath 528.64 79.15 moveto -539.21 78.37 lineto -530.46 72.39 lineto +newpath 452.25 78.89 moveto +462.84 78.62 lineto +454.39 72.22 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 528.64 79.15 moveto -539.21 78.37 lineto -530.46 72.39 lineto +newpath 452.25 78.89 moveto +462.84 78.62 lineto +454.39 72.22 lineto closepath stroke grestore % Table rows->Dictionary gsave 1 setlinewidth 0 0 0 edgecolor -newpath 483.06 46.65 moveto -580.42 46.09 771.77 44.99 874.56 44.4 curveto +newpath 413.9 46.66 moveto +495.38 46.1 657.77 44.99 744.22 44.39 curveto stroke 0 0 0 edgecolor -newpath 874.85 47.9 moveto -884.83 44.34 lineto -874.81 40.9 lineto +newpath 744.4 47.89 moveto +754.38 44.32 lineto +744.36 40.89 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 874.85 47.9 moveto -884.83 44.34 lineto -874.81 40.9 lineto +newpath 744.4 47.89 moveto +754.38 44.32 lineto +744.36 40.89 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -664.88 48.8 moveto 91 (Original text) alignedtext +565.68 48.8 moveto 70 (Original text) alignedtext grestore % Dawg gsave 1 setlinewidth 0 0 0 nodecolor -810.92 90 37.09 18 ellipse_path stroke +685.53 90 31.7 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -790.42 86.3 moveto 41 (Dawg) alignedtext +669.03 86.3 moveto 33 (Dawg) alignedtext grestore % Node lists->Dawg gsave 1 setlinewidth 0 0 0 edgecolor -newpath 641.29 90 moveto -679.18 90 728.33 90 763.78 90 curveto +newpath 545.75 90 moveto +575.66 90 614.46 90 643.43 90 curveto stroke 0 0 0 edgecolor -newpath 763.85 93.5 moveto -773.85 90 lineto -763.85 86.5 lineto +newpath 643.62 93.5 moveto +653.62 90 lineto +643.62 86.5 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 763.85 93.5 moveto -773.85 90 lineto -763.85 86.5 lineto +newpath 643.62 93.5 moveto +653.62 90 lineto +643.62 86.5 lineto closepath stroke grestore % Dawg->Dictionary gsave 1 setlinewidth 0 0 0 edgecolor -newpath 841.51 79.68 moveto -857.27 74.18 877.06 67.27 895.02 61.01 curveto +newpath 712.04 79.79 moveto +725.95 74.22 743.53 67.19 759.41 60.83 curveto stroke 0 0 0 edgecolor -newpath 896.48 64.21 moveto -904.77 57.61 lineto -894.17 57.6 lineto +newpath 761.04 63.95 moveto +769.03 56.98 lineto +758.44 57.45 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 896.48 64.21 moveto -904.77 57.61 lineto -894.17 57.6 lineto +newpath 761.04 63.95 moveto +769.03 56.98 lineto +758.44 57.45 lineto closepath stroke grestore % Dictionary->q1 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 1004.81 44 moveto -1037.74 44 1077.71 44 1106.09 44 curveto +newpath 850.57 44 moveto +877.59 44 911.01 44 936.03 44 curveto stroke 0 0 0 edgecolor -newpath 1106.36 47.5 moveto -1116.36 44 lineto -1106.36 40.5 lineto +newpath 936.2 47.5 moveto +946.2 44 lineto +936.2 40.5 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 1106.36 47.5 moveto -1116.36 44 lineto -1106.36 40.5 lineto +newpath 936.2 47.5 moveto +946.2 44 lineto +936.2 40.5 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -1022.56 47.8 moveto 76 (To crawler) alignedtext +868.57 47.8 moveto 60 (To crawler) alignedtext grestore endpage showpage diff --git a/thesis2/nddawg.eps b/thesis2/nddawg.eps index 0600bb2..75fd55b 100644 --- a/thesis2/nddawg.eps +++ b/thesis2/nddawg.eps @@ -2,7 +2,7 @@ %%Creator: graphviz version 2.38.0 (20140413.2041) %%Title: %3 %%Pages: 1 -%%BoundingBox: 36 36 634 134 +%%BoundingBox: 36 36 604 134 %%EndComments save %%BeginProlog @@ -179,11 +179,11 @@ def %%EndSetup setupLatin1 %%Page: 1 1 -%%PageBoundingBox: 36 36 634 134 +%%PageBoundingBox: 36 36 604 134 %%PageOrientation: Portrait 0 0 1 beginpage gsave -36 36 598 98 boxprim clip newpath +36 36 568 98 boxprim clip newpath 1 1 set_scale 0 rotate 40 40 translate % n0 % q0 @@ -193,7 +193,7 @@ gsave 118 47 27 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -108.5 43.3 moveto 19 (q0) alignedtext +111 43.3 moveto 14 (q0) alignedtext grestore % n0->q0 gsave @@ -219,219 +219,219 @@ grestore gsave 1 setlinewidth 0 0 0 nodecolor -563.75 47 22.96 22.96 ellipse_path stroke +536.5 47 19.5 19.5 ellipse_path stroke 1 setlinewidth 0 0 0 nodecolor -563.75 47 27 27 ellipse_path stroke +536.5 47 23.5 23.5 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -554.25 43.3 moveto 19 (q4) alignedtext +529.5 43.3 moveto 14 (q4) alignedtext grestore % q1 gsave 1 setlinewidth 0 0 0 nodecolor -217 47 27 18 ellipse_path stroke +215 47 27 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -207.5 43.3 moveto 19 (q1) alignedtext +208 43.3 moveto 14 (q1) alignedtext grestore % q0->q1 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 145.25 47 moveto -155.82 47 168.18 47 179.6 47 curveto +newpath 145.21 47 moveto +155.28 47 166.96 47 177.81 47 curveto stroke 0 0 0 edgecolor -newpath 179.73 50.5 moveto -189.73 47 lineto -179.73 43.5 lineto +newpath 177.87 50.5 moveto +187.87 47 lineto +177.87 43.5 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 179.73 50.5 moveto -189.73 47 lineto -179.73 43.5 lineto +newpath 177.87 50.5 moveto +187.87 47 lineto +177.87 43.5 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -163 50.8 moveto 9 (a) alignedtext +163 50.8 moveto 7 (a) alignedtext grestore % q2 gsave 1 setlinewidth 0 0 0 nodecolor -341 72 27 18 ellipse_path stroke +329 72 27 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -331.5 68.3 moveto 19 (q2) alignedtext +322 68.3 moveto 14 (q2) alignedtext grestore % q1->q2 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 242.98 52.12 moveto -260.91 55.79 285.31 60.79 305.15 64.86 curveto +newpath 240.86 52.55 moveto +256.23 55.98 276.19 60.43 293.12 64.22 curveto stroke 0 0 0 edgecolor -newpath 304.55 68.31 moveto -315.05 66.89 lineto -305.96 61.45 lineto +newpath 292.69 67.7 moveto +303.21 66.47 lineto +294.22 60.87 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 304.55 68.31 moveto -315.05 66.89 lineto -305.96 61.45 lineto +newpath 292.69 67.7 moveto +303.21 66.47 lineto +294.22 60.87 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -274 65.8 moveto 10 (b) alignedtext +268.5 64.8 moveto 7 (b) alignedtext grestore % q5 gsave 1 setlinewidth 0 0 0 nodecolor -341 18 27 18 ellipse_path stroke +329 18 27 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -331.5 14.3 moveto 19 (q5) alignedtext +322 14.3 moveto 14 (q5) alignedtext grestore % q1->q5 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 242.69 41.13 moveto -260.71 36.85 285.39 30.98 305.38 26.23 curveto +newpath 240.3 40.71 moveto +255.9 36.67 276.39 31.36 293.64 26.9 curveto stroke 0 0 0 edgecolor -newpath 306.43 29.58 moveto -315.35 23.86 lineto -304.81 22.77 lineto +newpath 294.55 30.28 moveto +303.36 24.38 lineto +292.8 23.5 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 306.43 29.58 moveto -315.35 23.86 lineto -304.81 22.77 lineto +newpath 294.55 30.28 moveto +303.36 24.38 lineto +292.8 23.5 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -262 38.8 moveto 34 (<1>) alignedtext +260 38.8 moveto 24 (<1>) alignedtext grestore % q3 gsave 1 setlinewidth 0 0 0 nodecolor -465 72 27 18 ellipse_path stroke +443 72 27 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -455.5 68.3 moveto 19 (q3) alignedtext +436 68.3 moveto 14 (q3) alignedtext grestore % q2->q3 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 368.17 72 moveto -385.54 72 408.57 72 427.7 72 curveto +newpath 356.26 72 moveto +371 72 389.62 72 405.74 72 curveto stroke 0 0 0 edgecolor -newpath 427.87 75.5 moveto -437.87 72 lineto -427.87 68.5 lineto +newpath 405.91 75.5 moveto +415.91 72 lineto +405.91 68.5 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 427.87 75.5 moveto -437.87 72 lineto -427.87 68.5 lineto +newpath 405.91 75.5 moveto +415.91 72 lineto +405.91 68.5 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -386 75.8 moveto 34 (<1>) alignedtext +374 75.8 moveto 24 (<1>) alignedtext grestore % q3->q4 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 490.41 65.69 moveto -501.7 62.78 515.31 59.26 527.66 56.07 curveto +newpath 468.52 65.3 moveto +479.41 62.32 492.36 58.79 503.96 55.62 curveto stroke 0 0 0 edgecolor -newpath 528.86 59.37 moveto -537.67 53.48 lineto -527.11 52.59 lineto +newpath 505 58.96 moveto +513.72 52.95 lineto +503.15 52.21 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 528.86 59.37 moveto -537.67 53.48 lineto -527.11 52.59 lineto +newpath 505 58.96 moveto +513.72 52.95 lineto +503.15 52.21 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -510 63.8 moveto 9 (c) alignedtext +488 62.8 moveto 7 (c) alignedtext grestore % q6 gsave 1 setlinewidth 0 0 0 nodecolor -465 18 27 18 ellipse_path stroke +443 18 27 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -455.5 14.3 moveto 19 (q6) alignedtext +436 14.3 moveto 14 (q6) alignedtext grestore % q5->q6 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 368.17 18 moveto -385.54 18 408.57 18 427.7 18 curveto +newpath 356.26 18 moveto +371 18 389.62 18 405.74 18 curveto stroke 0 0 0 edgecolor -newpath 427.87 21.5 moveto -437.87 18 lineto -427.87 14.5 lineto +newpath 405.91 21.5 moveto +415.91 18 lineto +405.91 14.5 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 427.87 21.5 moveto -437.87 18 lineto -427.87 14.5 lineto +newpath 405.91 21.5 moveto +415.91 18 lineto +405.91 14.5 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -398 21.8 moveto 10 (b) alignedtext +382.5 21.8 moveto 7 (b) alignedtext grestore % q6->q4 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 489.92 25.17 moveto -501.4 28.61 515.37 32.8 527.99 36.58 curveto +newpath 468.04 25.62 moveto +479.02 29.1 492.16 33.26 503.92 36.99 curveto stroke 0 0 0 edgecolor -newpath 527.17 39.99 moveto -537.76 39.51 lineto -529.18 33.29 lineto +newpath 503.22 40.44 moveto +513.81 40.13 lineto +505.33 33.77 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 527.17 39.99 moveto -537.76 39.51 lineto -529.18 33.29 lineto +newpath 503.22 40.44 moveto +513.81 40.13 lineto +505.33 33.77 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -510 36.8 moveto 9 (c) alignedtext +488 37.8 moveto 7 (c) alignedtext grestore endpage showpage diff --git a/thesis2/nodelistexample.eps b/thesis2/nodelistexample.eps index 8d1afde..150122a 100644 --- a/thesis2/nodelistexample.eps +++ b/thesis2/nodelistexample.eps @@ -2,7 +2,7 @@ %%Creator: graphviz version 2.38.0 (20140413.2041) %%Title: %3 %%Pages: 1 -%%BoundingBox: 36 36 1149 97 +%%BoundingBox: 36 36 1077 91 %%EndComments save %%BeginProlog @@ -179,300 +179,300 @@ def %%EndSetup setupLatin1 %%Page: 1 1 -%%PageBoundingBox: 36 36 1149 97 +%%PageBoundingBox: 36 36 1077 91 %%PageOrientation: Portrait 0 0 1 beginpage gsave -36 36 1113 61 boxprim clip newpath +36 36 1041 55 boxprim clip newpath 1 1 set_scale 0 rotate 40 40 translate % n0 % n1 gsave 1 setlinewidth 0 0 0 nodecolor -118 26.75 27 18 ellipse_path stroke +118 23.5 27 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -108.5 23.05 moveto 19 (n1) alignedtext +111 19.8 moveto 14 (n1) alignedtext grestore % n0->n1 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 54.22 26.75 moveto -62.55 26.75 71.91 26.75 80.82 26.75 curveto +newpath 54.22 23.5 moveto +62.55 23.5 71.91 23.5 80.82 23.5 curveto stroke 0 0 0 edgecolor -newpath 80.97 30.25 moveto -90.97 26.75 lineto -80.97 23.25 lineto +newpath 80.97 27 moveto +90.97 23.5 lineto +80.97 20 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 80.97 30.25 moveto -90.97 26.75 lineto -80.97 23.25 lineto +newpath 80.97 27 moveto +90.97 23.5 lineto +80.97 20 lineto closepath stroke grestore % n9 gsave 1 setlinewidth 0 0 0 nodecolor -1078.75 26.75 22.96 22.96 ellipse_path stroke +1009.5 23.5 19.5 19.5 ellipse_path stroke 1 setlinewidth 0 0 0 nodecolor -1078.75 26.75 27 27 ellipse_path stroke +1009.5 23.5 23.5 23.5 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -1069.25 23.05 moveto 19 (n9) alignedtext +1002.5 19.8 moveto 14 (n9) alignedtext grestore % n2 gsave 1 setlinewidth 0 0 0 nodecolor -265 26.75 27 18 ellipse_path stroke +250 23.5 27 18 ellipse_path stroke 0 0 0 nodecolor 14 /Times-Roman set_font -255.5 23.05 moveto 19 (n2) alignedtext +243 19.8 moveto 14 (n2) alignedtext grestore % n1->n2 gsave 1 setlinewidth 0 0 0 edgecolor -newpath 145.26 26.75 moveto -168.36 26.75 202.2 26.75 227.85 26.75 curveto +newpath 145.31 23.5 moveto +164.69 23.5 191.29 23.5 212.7 23.5 curveto stroke 0 0 0 edgecolor -newpath 227.94 30.25 moveto -237.94 26.75 lineto -227.94 23.25 lineto +newpath 212.73 27 moveto +222.73 23.5 lineto +212.73 20 lineto closepath fill 1 setlinewidth solid 0 0 0 edgecolor -newpath 227.94 30.25 moveto -237.94 26.75 lineto -227.94 23.25 lineto +newpath 212.73 27 moveto +222.73 23.5 lineto +212.73 20 lineto closepath stroke 0 0 0 edgecolor 14 /Times-Roman set_font -163 30.55 moveto 57 (