Seeing is Slicing: Observation Based Slicing of Picture Description Languages

This page is supplementary to the paper entitled "Seeing is Slicing: Observation Based Slicing of Picture Description Languages" ([PDF] [BIB]), which appeared at SCAM 2014.

Abstract

Program slicing has seen a plethora of applications and variations since its introduction over thirty years ago. The dominant method for computing slices involves significant complex source-code analysis to model the dependences in the code. A recently introduced alternative, Observation-Based Slicing (ORBS), sidesteps this complexity by observing candidate slices. ORBS has several other strengths, including the ability to slice multi-language systems.

However, ORBS remains rooted in tradition as it captures semantics by comparing sequence of values. This raises the question of whether it is possible to extend slicing beyond its traditional semantic roots. While a few existing projects have done this, the extension is a significant undertaking.

If it is possible to build on the ORBS platform to more easily generalize slicing to languages with non-traditional semantics, then there is the potential to vastly increase the range of programming languages to which slicing can be applied. ORBS supports this by reducing the problem to that of of generalizing how semantics are captured. Taking Picture Description Languages (PDLs) as a case study, the challenges and effectiveness of such a generalization are considered. The results show that not only is it possible to generalize the ORBS algorithm, but the resulting slices are capable of removing from 27% to 98% of the code with an average of 85%. Finally a qualitative look at the slices finds the technique very effective, at times producing minimal slices.

Experimental Setup

Subject Diagrams

We use four TikZ/PGF diagrams from a public online repository of exemplar diagrams: cone, hydrogen, raindrop, and shapes. In addition, we also consider a PIC diagram, which is taken from a paper describeing how to perform program slicing using the System Dependence Graph.

Full Results

This section contains both the PDL code and the resulting diagrams for the original and the slices.

Subject Language Size (LoC) Origin
cone TikZ/PGF 74 http://www.texample.net/tikz/examples/3d-cone/
hydrogen TikZ/PGF 61 http://www.texample.net/tikz/examples/hydrogen-splitting/
raindrop TikZ/PGF 45 http://www.texample.net/tikz/examples/raindrop/
shapes TikZ/PGF 25 http://www.texample.net/tikz/examples/node-shapes/
slice PIC 262 http://dl.acm.org/citation.cfm?id=53994

Subject: cone

Original code is available from here.

Original Diagram and Slices

Diagram

Code

\begin{tikzpicture}[join=round]
    \tikzstyle{conefill} = [fill=blue!20,fill opacity=0.8]
    \tikzstyle{ann} = [fill=white,font=\footnotesize,inner sep=1pt]
    \tikzstyle{ghostfill} = [fill=white]
         \tikzstyle{ghostdraw} = [draw=black!50]
    \filldraw[conefill](-.775,1.922)--(-1.162,.283)--(-.274,.5)
                        --(-.183,2.067)--cycle;
    \filldraw[conefill](-.183,2.067)--(-.274,.5)--(.775,.424)
                        --(.516,2.016)--cycle;
    \filldraw[conefill](.516,2.016)--(.775,.424)--(1.369,.1)
                        --(.913,1.8)--cycle;
    \filldraw[conefill](-.913,1.667)--(-1.369,-.1)--(-1.162,.283)
                        --(-.775,1.922)--cycle;
    \draw(1.461,.107)--(1.734,.127);
    \draw[arrows=<->](1.643,1.853)--(1.643,.12);
    \filldraw[conefill](.913,1.8)--(1.369,.1)--(1.162,-.283)
                        --(.775,1.545)--cycle;
    \draw[arrows=->,line width=.4pt](.274,-.5)--(0,0)--(0,2.86);
    \draw[arrows=-,line width=.4pt](0,0)--(-1.369,-.1);
    \draw[arrows=->,line width=.4pt](-1.369,-.1)--(-2.1,-.153);
    \filldraw[conefill](-.516,1.45)--(-.775,-.424)--(-1.369,-.1)
                        --(-.913,1.667)--cycle;
    \draw(-1.369,.073)--(-1.369,2.76);
    \draw(1.004,1.807)--(1.734,1.86);
    \filldraw[conefill](.775,1.545)--(1.162,-.283)--(.274,-.5)
                        --(.183,1.4)--cycle;
    \draw[arrows=<->](0,2.34)--(-.913,2.273);
    \draw(-.913,1.84)--(-.913,2.447);
    \draw[arrows=<->](0,2.687)--(-1.369,2.587);
    \filldraw[conefill](.183,1.4)--(.274,-.5)--(-.775,-.424)
                        --(-.516,1.45)--cycle;
    \draw[arrows=<-,line width=.4pt](.42,-.767)--(.274,-.5);
    \node[ann] at (-.456,2.307) {$r_0$};
    \node[ann] at (-.685,2.637) {$r_1$};
    \node[ann] at (1.643,.987) {$h$};
    \path (.42,-.767) node[below] {$x$}
        (0,2.86) node[above] {$y$}
        (-2.1,-.153) node[left] {$z$};
    % Second version of the cone
    \begin{scope}[xshift=3.5cm]
    \filldraw[ghostdraw,ghostfill](-.775,1.922)--(-1.162,.283)--(-.274,.5)
                                   --(-.183,2.067)--cycle;
    \filldraw[ghostdraw,ghostfill](-.183,2.067)--(-.274,.5)--(.775,.424) 
                                   --(.516,2.016)--cycle;
    \filldraw[ghostdraw,ghostfill](.516,2.016)--(.775,.424)--(1.369,.1)
                                   --(.913,1.8)--cycle;
    \filldraw[ghostdraw,ghostfill](-.913,1.667)--(-1.369,-.1)--(-1.162,.283)
                                   --(-.775,1.922)--cycle;
    \filldraw[ghostdraw,ghostfill](.913,1.8)--(1.369,.1)--(1.162,-.283)
                                   --(.775,1.545)--cycle;
    \filldraw[ghostdraw,ghostfill](-.516,1.45)--(-.775,-.424)--(-1.369,-.1)
                                   --(-.913,1.667)--cycle;
    \filldraw[ghostdraw,ghostfill](.775,1.545)--(1.162,-.283)--(.274,-.5)
                                   --(.183,1.4)--cycle;
    \filldraw[fill=red,fill opacity=0.5](-.516,1.45)--(-.775,-.424)--(.274,-.5)
                                         --(.183,1.4)--cycle;
    \fill(-.775,-.424) circle (2pt);
    \fill(.274,-.5) circle (2pt);
    \fill(-.516,1.45) circle (2pt);
    \fill(.183,1.4) circle (2pt);
    \path[font=\footnotesize]
            (.913,1.8) node[right] {$i\hbox{$=$}0$}
            (1.369,.1) node[right] {$i\hbox{$=$}1$};
    \path[font=\footnotesize]
            (-.645,.513) node[left] {$j$}
            (.228,.45) node[right] {$j\hbox{$+$}1$};
    \draw (-.209,.482)+(-60:.25) [yscale=1.3,->] arc(-60:240:.25);
    \fill[black,font=\footnotesize]
                    (-.516,1.45) node [above] {$P_{00}$}
                    (-.775,-.424) node [below] {$P_{10}$}
                    (.183,1.4) node [above] {$P_{01}$}
                    (.274,-.5) node [below] {$P_{11}$};
    \end{scope}
\end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[join=round]
    \tikzstyle{ann} = [fill=white,font=\footnotesize,inner sep=1pt]
    \tikzstyle{ghostfill} = [fill=white]
         \tikzstyle{ghostdraw} = [draw=black!50]
    \node[ann] at (-.456,2.307) {$r_0$};
    \path (.42,-.767) node[below] {$x$}
        (-2.1,-.153) node[left] {$z$};
    \begin{scope}[xshift=3.5cm]
    \filldraw[ghostdraw,ghostfill](-.775,1.922)--(-1.162,.283)--(-.274,.5)
                                   --(-.183,2.067)--cycle;
    \filldraw[ghostdraw,ghostfill](-.183,2.067)--(-.274,.5)--(.775,.424) 
                                   --(.516,2.016)--cycle;
    \filldraw[ghostdraw,ghostfill](-.913,1.667)--(-1.369,-.1)--(-1.162,.283)
                                   --(-.775,1.922)--cycle;
    \filldraw[ghostdraw,ghostfill](.913,1.8)--(1.369,.1)--(1.162,-.283)
                                   --(.775,1.545)--cycle;
    \filldraw[ghostdraw,ghostfill](-.516,1.45)--(-.775,-.424)--(-1.369,-.1)
                                   --(-.913,1.667)--cycle;
    \filldraw[ghostdraw,ghostfill](.775,1.545)--(1.162,-.283)--(.274,-.5)
                                   --(.183,1.4)--cycle;
    \filldraw[fill=red,fill opacity=0.5](-.516,1.45)--(-.775,-.424)--(.274,-.5)
                                         --(.183,1.4)--cycle;
    \fill(-.775,-.424) circle (2pt);
    \fill(.274,-.5) circle (2pt);
    \fill(-.516,1.45) circle (2pt);
    \fill(.183,1.4) circle (2pt);
    \path[font=\footnotesize]
            (.913,1.8) node[right] {$i\hbox{$=$}0$}
            (1.369,.1) node[right] {$i\hbox{$=$}1$};
    \path[font=\footnotesize]
            (-.645,.513) node[left] {$j$}
            (.228,.45) node[right] {$j\hbox{$+$}1$};
    \draw (-.209,.482)+(-60:.25) [yscale=1.3,->] arc(-60:240:.25);
    \fill[black,font=\footnotesize]
                    (-.516,1.45) node [above] {$P_{00}$}
                    (-.775,-.424) node [below] {$P_{10}$}
                    (.183,1.4) node [above] {$P_{01}$}
                    (.274,-.5) node [below] {$P_{11}$};
    \end{scope}
\end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[join=round]
    \tikzstyle{conefill} = [fill=blue!20,fill opacity=0.8]
    \tikzstyle{ann} = [fill=white,font=\footnotesize,inner sep=1pt]
    \filldraw[conefill](-.775,1.922)--(-1.162,.283)--(-.274,.5)
                        --(-.183,2.067)--cycle;
    \filldraw[conefill](-.183,2.067)--(-.274,.5)--(.775,.424)
                        --(.516,2.016)--cycle;
    \filldraw[conefill](.516,2.016)--(.775,.424)--(1.369,.1)
                        --(.913,1.8)--cycle;
    \filldraw[conefill](-.913,1.667)--(-1.369,-.1)--(-1.162,.283)
                        --(-.775,1.922)--cycle;
    \draw(1.461,.107)--(1.734,.127);
    \draw[arrows=<->](1.643,1.853)--(1.643,.12);
    \filldraw[conefill](.913,1.8)--(1.369,.1)--(1.162,-.283)
                        --(.775,1.545)--cycle;
    \draw[arrows=->,line width=.4pt](.274,-.5)--(0,0)--(0,2.86);
    \draw[arrows=-,line width=.4pt](0,0)--(-1.369,-.1);
    \draw[arrows=->,line width=.4pt](-1.369,-.1)--(-2.1,-.153);
    \filldraw[conefill](-.516,1.45)--(-.775,-.424)--(-1.369,-.1)
                        --(-.913,1.667)--cycle;
    \draw(-1.369,.073)--(-1.369,2.76);
    \draw(1.004,1.807)--(1.734,1.86);
    \filldraw[conefill](.775,1.545)--(1.162,-.283)--(.274,-.5)
                        --(.183,1.4)--cycle;
    \draw[arrows=<->](0,2.34)--(-.913,2.273);
    \draw(-.913,1.84)--(-.913,2.447);
    \draw[arrows=<->](0,2.687)--(-1.369,2.587);
    \filldraw[conefill](.183,1.4)--(.274,-.5)--(-.775,-.424)
                        --(-.516,1.45)--cycle;
    \draw[arrows=<-,line width=.4pt](.42,-.767)--(.274,-.5);
    \node[ann] at (-.456,2.307) {$r_0$};
    \node[ann] at (-.685,2.637) {$r_1$};
    \node[ann] at (1.643,.987) {$h$};
    \path (.42,-.767) node[below] {$x$}
        (0,2.86) node[above] {$y$}
        (-2.1,-.153) node[left] {$z$};
\end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[join=round]
        (0,2.86) node[above] {$y$}
\end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[join=round]
    \draw[arrows=->,line width=.4pt](-1.369,-.1)--(-2.1,-.153);
    \path (.42,-.767) node[below] {$x$}
        (0,2.86) node[above] {$y$}
        (-2.1,-.153) node[left] {$z$};
\end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[join=round]
    \draw[arrows=-,line width=.4pt](0,0)--(-1.369,-.1);
        (-2.1,-.153) node[left] {$z$};
    \begin{scope}[xshift=3.5cm]
    \filldraw[fill=red,fill opacity=0.5](-.516,1.45)--(-.775,-.424)--(.274,-.5)
                                         --(.183,1.4)--cycle;
    \draw (-.209,.482)+(-60:.25) [yscale=1.3,->] arc(-60:240:.25);
    \fill[black,font=\footnotesize]
                    (.183,1.4) node [above] {$P_{01}$}
                    (.274,-.5) node [below] {$P_{11}$};
    \end{scope}
\end{tikzpicture}

					

Subject: hydrogen

Original code is available from here.

Original Diagram and Slices

Diagram

Code

\begin{tikzpicture}[ scale=0.4, level/.style={very thick} ]
    \tikzset{photon/.style={<->,decorate, decoration={snake}, draw=red,
      line width=0.4mm,>=triangle 60}}
    \tikzset{rotdis/.style={<->,decorate, draw=red,line width=0.4mm}}
    % Draw the energy levels.
    %  0 Field
    \draw[level] (3cm, 6cm) -- (5cm, 6cm)node at (3,6)[left]{$^{1}$S$_{1/2}$};
    \draw[level] ( 5cm, 6cm) -- ( 6cm, 7.5cm);
    \draw[level] ( 5cm, 6cm) -- ( 6cm, 0cm);
    \draw[level,blue] ( 6cm, 7.5cm) -- ( 10cm, 7.5cm)node[above]{1};
    \draw[level,blue] ( 6cm, 0cm) -- ( 10cm, 0cm)node[above]{0};
    \draw[-,very thick, dashed](5cm,6cm)--(10cm,6cm);
    \draw[rotdis] (7cm,7.5cm) -- (7cm,6cm)node[right,midway]{$1/4$ A$_{H}$};
    \draw[rotdis] (7cm,6cm) -- (7cm,0cm)node[right,midway]{$3/4$ A$_{H}$};
    \draw[blue] (10.cm,9cm)node{F};
    \draw[](8cm,-1cm)node{0 Feld N\"aherung};
    \draw[](8cm,17cm)node[font=\large]{\underline{0-Feld}};
   %  weak field Field
    \draw[level,blue] ( 13cm, 7.5cm) -- ( 17cm, 7.5cm)node[right]{\ 0};
    \draw[level,blue] ( 13cm, 8.2cm) -- ( 17cm, 8.2cm)node[right]{\ 1};
    \draw[level,blue] ( 13cm, 6.8cm) -- ( 17cm, 6.8cm)node[right]{-1};
    \draw[level,blue] ( 13cm, 0cm) -- ( 17cm, 0cm)node[above]{0};
    \draw[level] ( 12cm, 7.5cm) -- ( 12.8cm, 7.5cm);
    \draw[-,very thick, dashed] ( 12cm, 6cm) -- ( 17cm, 6cm);
    \draw[](15cm,17cm)node[font=\large]{\underline{Zeeman}};
   % Breit Rabi
     \draw[level] ( 19.5cm, 6.8cm) -- ( 21cm, 6.8cm); 
     \draw[level] ( 19.5cm, 7.5cm) -- ( 21cm, 7.5cm); 
     \draw[level] ( 19.5cm, 8.2cm) -- ( 21cm, 8.2cm); 
     \draw[level] ( 19.5cm, 0cm) -- ( 21cm, 0cm); 
     \draw[level,blue]  ( 21cm, 6.8cm) -- (25cm,-1cm); 
     \draw[level,blue]  ( 21cm, 7.5cm) -- (25cm,12cm);  
     \draw[level,blue]  ( 21cm, 8.2cm) -- (25cm,15cm);  
     \draw[level,blue] ( 21cm, 0cm)  --(25cm,-4cm);  
     \draw[-,very thick, dashed] ( 19.5cm, 6cm) -- ( 25cm, 6cm);
     \draw[](22cm,17cm)node[font=\large]{\underline{Breit Rabi}};
    % Paschen Back
    \draw[level,blue] ( 25cm, -1cm) -- ( 29cm,-1cm); 
     \draw[level,blue] ( 25cm, 12cm) -- ( 29cm, 12cm); 
     \draw[level,blue] ( 25cm, 15cm) -- ( 32cm, 15cm); 
     \draw[level,blue] ( 25cm, -4cm) -- ( 32cm, -4cm); 
     \draw[photon] ( 31.5cm, -4cm) -- ( 31.5cm, 15cm); 
     \draw[photon] ( 28.cm, -1cm) -- ( 28.cm, 12cm); 
     \draw[level,green!50!black,dashed] ( 25cm, 13.5cm) -- ( 28cm, 13.5cm); 
     \draw[level,green!50!black,dashed] ( 25cm, -2.5cm) -- ( 28cm, -2.5cm);
     \draw[rotdis] (26cm,-2.5cm) -- (26cm,6cm)node at (26cm,4cm)[left]
      {$\frac{1}{2}g_{e}\mu_{B}B$};
    \draw[rotdis] (26cm,6cm) -- (26cm,13.5cm)node at (26cm,8cm)[left]
      {$\frac{1}{2}g_{e}\mu_{B}B$};
    \draw[rotdis] (28cm,-4cm) -- (28cm,-1cm)node[right,midway]{$1/2 A_{H}$};
    \draw[rotdis] (28cm,12cm) -- (28cm,15cm)node[right,midway]{$1/2 A_{H}$};
    \draw[](35cm,-4cm)node[font=\large]{ $0=-\nicefrac{1}{2}+\nicefrac{1}{2}$};
    \draw[](35cm,-1cm)node[font=\large]{$-1=-\nicefrac{1}{2}-\nicefrac{1}{2}$};
    \draw[](35cm,12cm)node[font=\large]{ $0=\nicefrac{1}{2}-\nicefrac{1}{2}$};
    \draw[](35cm,15cm)node[font=\large]{ $1=\nicefrac{1}{2}+\nicefrac{1}{2}$};
    \draw[](35cm,17cm)node[font=\large]{$m=m_{j}+m_{i}$};
    \draw[](28cm,17cm)node[font=\large]{\underline{Paschen Back}};
     \draw[<-, draw=green!50!black,line width=1mm](31.5cm,8cm)--(35cm,9cm)
      node[right,font=\large]{$\Delta m=1$};
    \draw[<-, draw=green!50!black,line width=1mm](28.cm,4cm)--(35cm,9cm);
  \end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[ scale=0.4, level/.style={very thick} ]
    \tikzset{rotdis/.style={<->,decorate, draw=red,line width=0.4mm}}
    \draw[level] ( 5cm, 6cm) -- ( 6cm, 7.5cm);
    \draw[level] ( 5cm, 6cm) -- ( 6cm, 0cm);
    \draw[level,blue] ( 6cm, 7.5cm) -- ( 10cm, 7.5cm)node[above]{1};
    \draw[level,blue] ( 6cm, 0cm) -- ( 10cm, 0cm)node[above]{0};
    \draw[-,very thick, dashed](5cm,6cm)--(10cm,6cm);
    \draw[rotdis] (7cm,7.5cm) -- (7cm,6cm)node[right,midway]{$1/4$ A$_{H}$};
    \draw[rotdis] (7cm,6cm) -- (7cm,0cm)node[right,midway]{$3/4$ A$_{H}$};
    \draw[](8cm,-1cm)node{0 Feld N\"aherung};
  \end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[ scale=0.4, level/.style={very thick} ]
    \draw[](8cm,17cm)node[font=\large]{\underline{0-Feld}};
    \draw[](15cm,17cm)node[font=\large]{\underline{Zeeman}};
     \draw[](22cm,17cm)node[font=\large]{\underline{Breit Rabi}};
    \draw[](35cm,17cm)node[font=\large]{$m=m_{j}+m_{i}$};
    \draw[](28cm,17cm)node[font=\large]{\underline{Paschen Back}};
  \end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[ scale=0.4, level/.style={very thick} ]
    \draw[level,blue] ( 13cm, 7.5cm) -- ( 17cm, 7.5cm)node[right]{\ 0};
    \draw[level,blue] ( 13cm, 8.2cm) -- ( 17cm, 8.2cm)node[right]{\ 1};
    \draw[level,blue] ( 13cm, 6.8cm) -- ( 17cm, 6.8cm)node[right]{-1};
    \draw[level,blue] ( 13cm, 0cm) -- ( 17cm, 0cm)node[above]{0};
    \draw[-,very thick, dashed] ( 12cm, 6cm) -- ( 17cm, 6cm);
  \end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[ scale=0.4, level/.style={very thick} ]
    \tikzset{photon/.style={<->,decorate, decoration={snake}, draw=red,
      line width=0.4mm,>=triangle 60}}
     \draw[photon] ( 31.5cm, -4cm) -- ( 31.5cm, 15cm); 
     \draw[photon] ( 28.cm, -1cm) -- ( 28.cm, 12cm); 
    \draw[](28cm,17cm)node[font=\large]{\underline{Paschen Back}};
     \draw[<-, draw=green!50!black,line width=1mm](31.5cm,8cm)--(35cm,9cm)
      node[right,font=\large]{$\Delta m=1$};
    \draw[<-, draw=green!50!black,line width=1mm](28.cm,4cm)--(35cm,9cm);
  \end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[ scale=0.4, level/.style={very thick} ]
    \draw[](35cm,12cm)node[font=\large]{ $0=\nicefrac{1}{2}-\nicefrac{1}{2}$};
    \draw[](35cm,15cm)node[font=\large]{ $1=\nicefrac{1}{2}+\nicefrac{1}{2}$};
  \end{tikzpicture}

					

Subject: raindrop

Original code is available from here.

Original Diagram and Slices

Diagram

Code

\begin{tikzpicture}[xscale=-1,
    ray/.style={decoration={markings,mark=at position .5 with {
      \arrow[>=latex]{>}}},postaction=decorate}
  ]
  \pgfmathsetlengthmacro{\r}{3cm}
  \pgfmathsetmacro{\f}{.7}
  \pgfmathsetlengthmacro{\arcradius}{.8cm}
  \pgfmathsetlengthmacro{\dotradius}{.6cm}
  \pgfmathsetlengthmacro{\arclabelradius}{1cm}
  \pgfmathsetmacro{\incidentangle}{asin(\f)}
  \coordinate (O) at (0, 0);
  \coordinate (A) at (\incidentangle:\r);
  \draw (O) circle (\r);
  \draw[ray] (A  -| \r*3, 0) -- (A);
  \draw[gray] (O) -- ($(O)!1.5!(A)$) node[pos=1.05] {$n$};
  \drawarcdelta{(A)}{0}{\incidentangle}{\arcradius-1pt}
  \drawlabeledarcdelta{(A)}{0}{\incidentangle}{\arcradius+1pt}
    {$i$}{\arclabelradius}
  \foreach \index/\color in {1.32/red, 1.34/blue} {
    \pgfmathsetmacro{\refractedangle}{asin(sin(\incidentangle) / \index)}
    \pgfmathsetmacro{\angleindrop}{180 - 2*\refractedangle}
    \coordinate (A') at (\incidentangle+\angleindrop:\r);
    \coordinate (A'') at (\incidentangle+2*\angleindrop:\r);
    \begin{scope}[opacity=.5, color=\color]
      \draw[ray] (A) -- (A');
      \draw[ray] (A') -- (A'');
      \draw[ray] (A'') -- ($(A'')+(2*\incidentangle+2*\angleindrop:2*\r)$);
      \draw (O) -- ($(O)!1.5!(A')$) node[pos=1.05] {$n$};
      \draw (O) -- ($(O)!1.5!(A'')$) node[pos=1.05] {$n$};
      \drawlabeledarcdelta{(A)}{\incidentangle+180}{-\refractedangle}
        {\arcradius}{$r$}{\arclabelradius}
      \drawarcdelta{(A')}{\incidentangle+\angleindrop+180}{\refractedangle}
        {\arcradius}
      \drawarcdelta{(A')}{\incidentangle+\angleindrop+180}{-\refractedangle}
        {\arcradius}
      \drawarcdelta{(A'')}{\incidentangle+2*\angleindrop+180}{\refractedangle}
        {\arcradius}
    \end{scope}
    \drawarcdelta{(A'')}{\incidentangle+2*\angleindrop}{\incidentangle}
      {\arcradius-1pt}
    \drawarcdelta{(A'')}{\incidentangle+2*\angleindrop}{\incidentangle}
      {\arcradius+1pt}
  }
  \draw[fill] (O) circle (1.5pt);
\end{tikzpicture}
					

Criterion

Slice

Code

\begin{tikzpicture}[xscale=-1,
    ray/.style={decoration={markings,mark=at position .5 with {
      \arrow[>=latex]{>}}},postaction=decorate}
  ]
  \pgfmathsetlengthmacro{\r}{3cm}
  \pgfmathsetmacro{\f}{.7}
  \pgfmathsetlengthmacro{\arcradius}{.8cm}
  \pgfmathsetlengthmacro{\arclabelradius}{1cm}
  \pgfmathsetmacro{\incidentangle}{asin(\f)}
  \coordinate (O) at (0, 0);
  \coordinate (A) at (\incidentangle:\r);
  \draw[ray] (A  -| \r*3, 0) -- (A);
  \draw[gray] (O) -- ($(O)!1.5!(A)$) node[pos=1.05] {$n$};
  \drawarcdelta{(A)}{0}{\incidentangle}{\arcradius-1pt}
  \drawlabeledarcdelta{(A)}{0}{\incidentangle}{\arcradius+1pt}
    {$i$}{\arclabelradius}
\end{tikzpicture}
					

Criterion

Slice

Code

\begin{tikzpicture}[xscale=-1,
    ray/.style={decoration={markings,mark=at position .5 with {
      \arrow[>=latex]{>}}},postaction=decorate}
  ]
  \pgfmathsetlengthmacro{\r}{3cm}
  \pgfmathsetmacro{\f}{.7}
  \pgfmathsetmacro{\incidentangle}{asin(\f)}
  \coordinate (O) at (0, 0);
  \coordinate (A) at (\incidentangle:\r);
  \draw[ray] (A  -| \r*3, 0) -- (A);
  \draw[gray] (O) -- ($(O)!1.5!(A)$) node[pos=1.05] {$n$};
\end{tikzpicture}
					

Criterion

Slice

Code

\begin{tikzpicture}[xscale=-1,
    ray/.style={decoration={markings,mark=at position .5 with {
      \arrow[>=latex]{>}}},postaction=decorate}
  ]
  \pgfmathsetlengthmacro{\r}{3cm}
  \pgfmathsetmacro{\f}{.7}
  \pgfmathsetmacro{\incidentangle}{asin(\f)}
  \coordinate (O) at (0, 0);
  \coordinate (A) at (\incidentangle:\r);
  \draw[ray] (A  -| \r*3, 0) -- (A);
  \draw[gray] (O) -- ($(O)!1.5!(A)$) node[pos=1.05] {$n$};
  \foreach \index/\color in {1.32/red, 1.34/blue} {
    \pgfmathsetmacro{\refractedangle}{asin(sin(\incidentangle) / \index)}
    \pgfmathsetmacro{\angleindrop}{180 - 2*\refractedangle}
    \coordinate (A') at (\incidentangle+\angleindrop:\r);
    \coordinate (A'') at (\incidentangle+2*\angleindrop:\r);
    \begin{scope}[opacity=.5, color=\color]
      \draw (O) -- ($(O)!1.5!(A')$) node[pos=1.05] {$n$};
      \draw (O) -- ($(O)!1.5!(A'')$) node[pos=1.05] {$n$};
    \end{scope}
  }
  \draw[fill] (O) circle (1.5pt);
\end{tikzpicture}
					

Criterion

Slice

Code

\begin{tikzpicture}[xscale=-1,
    ray/.style={decoration={markings,mark=at position .5 with {
      \arrow[>=latex]{>}}},postaction=decorate}
  ]
  \pgfmathsetlengthmacro{\r}{3cm}
  \pgfmathsetmacro{\f}{.7}
  \pgfmathsetlengthmacro{\arcradius}{.8cm}
  \pgfmathsetmacro{\incidentangle}{asin(\f)}
  \coordinate (O) at (0, 0);
  \coordinate (A) at (\incidentangle:\r);
  \draw (O) circle (\r);
  \draw[ray] (A  -| \r*3, 0) -- (A);
  \draw[gray] (O) -- ($(O)!1.5!(A)$) node[pos=1.05] {$n$};
  \foreach \index/\color in {1.32/red, 1.34/blue} {
    \pgfmathsetmacro{\refractedangle}{asin(sin(\incidentangle) / \index)}
    \pgfmathsetmacro{\angleindrop}{180 - 2*\refractedangle}
    \coordinate (A') at (\incidentangle+\angleindrop:\r);
    \coordinate (A'') at (\incidentangle+2*\angleindrop:\r);
    \begin{scope}[opacity=.5, color=\color]
      \draw[ray] (A') -- (A'');
      \draw[ray] (A'') -- ($(A'')+(2*\incidentangle+2*\angleindrop:2*\r)$);
      \draw (O) -- ($(O)!1.5!(A')$) node[pos=1.05] {$n$};
      \draw (O) -- ($(O)!1.5!(A'')$) node[pos=1.05] {$n$};
      \drawarcdelta{(A'')}{\incidentangle+2*\angleindrop+180}{\refractedangle}
        {\arcradius}
    \end{scope}
    \drawarcdelta{(A'')}{\incidentangle+2*\angleindrop}{\incidentangle}
      {\arcradius-1pt}
    \drawarcdelta{(A'')}{\incidentangle+2*\angleindrop}{\incidentangle}
      {\arcradius+1pt}
  }
  \draw[fill] (O) circle (1.5pt);
\end{tikzpicture}
					

Criterion

Slice

Code

\begin{tikzpicture}[xscale=-1,
  ]
  \pgfmathsetlengthmacro{\r}{3cm}
  \coordinate (O) at (0, 0);
  \draw (O) circle (\r);
\end{tikzpicture}
					

Subject: shapes

Original code is available from here.

Original Diagram and Slices

Diagram

Code

\begin{tikzpicture}[scale=2]
    \tikzstyle{ann} = [draw=none,fill=none,right]
    \matrix[nodes={draw, ultra thick, fill=blue!20},
        row sep=0.3cm,column sep=0.5cm] {
    \node[draw=none,fill=none] {Plain node}; &
    \node[rectangle] {Rectangle}; &
    \node[circle] {Circle};\\
    \node[ellipse] {Ellipse};&
    \node[circle split] {Circle \nodepart{lower} split};&
    \node[forbidden sign,text width=4em, text centered]
                    {Forbidden sign};\\
    \node[diamond] {Diamond};&
    \node[cross out] {Cross out};&
    \node[strike out] {Strike out};\\
    \node[regular polygon,regular polygon sides=5] {$n=5$};&
    \node[regular polygon,regular polygon sides=7] {$n=7$};&
    \node[regular polygon,regular polygon sides=9] {$n=9$};&
    \node[ann]{Regular polygon};\\
    \node[star,star points=4] {$p=4$};&
    \node[star,star points=7,star point ratio=0.8] {$p=7$};&
    \node[star,star points=10] {$p=9$};&
    \node[ann]{Star};\\
    };
\end{tikzpicture}


					

Criterion

Slice

Code

\begin{tikzpicture}[scale=2]
    \tikzstyle{ann} = [draw=none,fill=none,right]
    \matrix[nodes={draw, ultra thick, fill=blue!20},
        row sep=0.3cm,column sep=0.5cm] {
    \node[circle] {Circle};\\
    \node[ellipse] {Ellipse};&
    \node[circle split] {Circle \nodepart{lower} split};&
    \node[forbidden sign,text width=4em, text centered]
                    {Forbidden sign};\\
    \node[diamond] {Diamond};&
    \node[cross out] {Cross out};&
    \node[ann]{Regular polygon};\\
    \node[star,star points=4] {$p=4$};&
    \node[ann]{Star};\\
    };
\end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[scale=2]
    \tikzstyle{ann} = [draw=none,fill=none,right]
    \matrix[nodes={draw, ultra thick, fill=blue!20},
        row sep=0.3cm,column sep=0.5cm] {
    \node[ellipse] {Ellipse};&
    \node[circle split] {Circle \nodepart{lower} split};&
    \node[forbidden sign,text width=4em, text centered]
                    {Forbidden sign};\\
    \node[diamond] {Diamond};&
    \node[cross out] {Cross out};&
    \node[star,star points=10] {$p=9$};&
    \node[ann]{Star};\\
    };
\end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[scale=2]
    \matrix[nodes={draw, ultra thick, fill=blue!20},
        row sep=0.3cm,column sep=0.5cm] {
                    {Forbidden sign};\\
    \node[cross out] {Cross out};&
    \node[strike out] {Strike out};\\
    };
\end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[scale=2]
    \tikzstyle{ann} = [draw=none,fill=none,right]
    \matrix[nodes={draw, ultra thick, fill=blue!20},
        row sep=0.3cm,column sep=0.5cm] {
                    {Forbidden sign};\\
    \node[diamond] {Diamond};&
    \node[cross out] {Cross out};&
    \node[strike out] {Strike out};\\
    \node[regular polygon,regular polygon sides=5] {$n=5$};&
    \node[regular polygon,regular polygon sides=7] {$n=7$};&
    \node[regular polygon,regular polygon sides=9] {$n=9$};&
    \node[ann]{Regular polygon};\\
    \node[star,star points=4] {$p=4$};&
    \node[star,star points=7,star point ratio=0.8] {$p=7$};&
    \node[star,star points=10] {$p=9$};&
    \node[ann]{Star};\\
    };
\end{tikzpicture}

					

Criterion

Slice

Code

\begin{tikzpicture}[scale=2]
    \tikzstyle{ann} = [draw=none,fill=none,right]
    \matrix[nodes={draw, ultra thick, fill=blue!20},
        row sep=0.3cm,column sep=0.5cm] {
    \node[diamond] {Diamond};&
    \node[ann]{Regular polygon};\\
    \node[star,star points=7,star point ratio=0.8] {$p=7$};&
    \node[star,star points=10] {$p=9$};&
    \node[ann]{Star};\\
    };
\end{tikzpicture}

					

Subject: slice

Original code is available from here.

Original Diagram and Slices

Diagram

Code

.EQ
delim @@
.EN
.de FS          \" .FS  start figure
.if \\np .(z L
.hl
.sp -0.35v
.SZ 9 12
.Sz 9 12
..
.de FE          \" .FE <number> <title> <no space>  end figure
.sp -0.5
.hl
.sp -0.5
.fi
.SZ 9 12
\fBFigure \\$1.\fR  \\$2
.if !'\\$3'NS'..sp 1.4v
.if \\np .)z
.SZ 10 14
..
.de FD       \" .FD <number> <figure index entry>  start description of figure
.sp -0.5
.hl
.sp -0.5
.fi
.SZ 9 12
\fBFigure \\$1.\fR  
.ds en Figure \\$1: 
..
.PS
###
#
# fat arrow macros
#
# (1) vertical
# (2) slant from right to left
# (3) slant from left to right
#
# arg1: from
# arg2: to
# arg3: edge label
#
###
define fatarrowv    X
.ps +27
                arrow from $1 to $2
.ps -27
        move to 1/2 between $1 and $2
        move to Here - (.1,0)
        $3 at Here ljust
        X

define fatarrowrl   X
.ps +27
        arrow from $1 to $2
.ps -27
        move to 1/2 between $1 and $2
        move to Here + (-.05, .05)
        $3 at Here ljust
        X

define fatarrowlr   X
.ps +27
        arrow from $1 to $2
.ps -27
        move to 1/2 between $1 and $2
        move to Here + (.05, .05)
        $3 at Here ljust
        X

###
#
# arrow with cut macros
#
# (1) right-to-left diagonal
# (2) vertical
# (3) horizontal
#
###

define cutarrowrl   X   arrow from $1 to $2
            move to 1/2 between $1 and $2
            move to Here - (circlerad*.25, circlerad*.25)
            line from Here to Here + (circlerad*.5, circlerad*.5)
            X

define cutarrowv     X  arrow from $1 to $2
            move to 1/2 between $1 and $2
            move to Here - (circlerad*.25,0)
            line from Here to Here + (circlerad*.5,0)
            X

define cutarrowh     X  arrow from $1 to $2
            move to 1/2 between $1 and $2
            move to Here - (0,circlerad*.25)
            line from Here to Here + (0,circlerad*.5)
            X


###
#
# self-loop with cut macros: defined in terms of ygap, circlerad
#
# (1) self loop UNDER arg 1
#
###

define selfloopu    X   ellipse wid ellipsewid*.5 with .n at $1
            arrow from $1 - (ygap/15, ygap/40) to $1
            line from $1 - (0,ellipseht*.75) to $1 -(0,ellipseht*1.25)
            X

.PE


.FS
.nr F1 0
.mk F1
@gsize 9@\fBprogram\fP @Main@
    @i~:=~1@
    \fBwhile\fP @i~<~11@ \fBdo\fP
        @i~:=~i~+~1@
    \fBod\fP
\fBend\fP(@i@)
.sp |\n(F1u
.PS 6.0i 2.5i
savebh = boxht
savebw = boxwid
saveah = arrowht
saveaw = arrowwid
boxht = boxht / 9
arrowht = arrowht/6
arrowwid = arrowwid/4

###
#
# dependence edge key
#
###
Title: box "Edge Key" invis
boxwid = boxwid/8
ControlE: box with .nw at 1/2 between Title.sw and Title.s invis
ControlD: box with .ne at 1/2 between Title.s and Title.se invis
LoopiE: box with .nw at ControlE.sw invis
LoopiD: box with .ne at ControlD.se invis
LoopcE: box with .nw at LoopiE.sw invis
LoopcD: box with .ne at LoopiD.se invis
DeforderE: box with .nw at LoopcE.sw invis
DeforderD: box with .ne at LoopcD.se invis

.ps +27
arrow from ControlE.w to ControlE.e
.ps -27
"control dependence" at ControlD.w ljust
arrow from LoopiE.w to LoopiE.e
"loop-independent flow dependence" at LoopiD.w ljust
arrow from LoopcE.w to LoopcE.e
"|" at LoopcE.c
"loop-carried flow dependence" at LoopcD.w ljust
arrow from DeforderE.w to DeforderE.e dashed .01
"def-order dependence" at DeforderD.w ljust

###
#
# put a box around the edge key
#
###

Left: line from ControlE.nw + (-boxwid/4, boxht*1.5) to DeforderE.sw - (boxwid/4,boxht*.5)
Right: line from ControlD.ne + (boxwid*7.30, boxht*1.5) to DeforderD.se + (boxwid*7.30,-boxht*.5)
line from Left.top to Right.top
line from Left.bot to Right.bot

###
# push the edge key into the left corner
###
box wid boxwid*14 with .e at ControlE.w invis

boxht = savebh
boxwid = savebw
arrowwid = saveaw
arrowht = saveah
.PE
.PS
xgap = 1.5
ygap = .75

saveeh = ellipseht
saveew = ellipsewid

ellipseht = ellipseht*.6
ellipsewid = ellipsewid*1.4

Entry: ellipse "ENTRY"

###
# predicate and assignment statement vertices
###

ellipsewid = ellipsewid*.7

I1: ellipse "@i~:=~1@" at Entry - (.5*xgap, ygap)
While1: ellipse wid ellipsewid*1.4 "\fBwhile\fP @i~<~11@" at I1 + (xgap, 0)
I2: ellipse wid ellipsewid*1.1 "@i~:=~i~+~1@" at While1 + (xgap*.5, -ygap)

###
# final uses (below the rest of the graph)
###

IFinal: ellipse wid ellipsewid*1.2 "FinalUse(\fIi\fP)" at While1 + (xgap, 0)

###
#
# control edges
#
###
fatarrowrl( Entry.s, I1.n, "T")
fatarrowlr( Entry.s, While1.n, "T" )
fatarrowlr( Entry.s, IFinal.n, "T" )
fatarrowlr( While1.s, I2.n, "T" )


###
#
# loop-indep flow edges
#
###
arrow from I1.e to While1.w
arrow from I1.s to I2.w

###
# to final uses
###

arc -> cw rad arcrad*14 from I1.ne to IFinal.nw
arrow from I2.ne to IFinal.sw

###
#
# loop-dep flow edges
#
###
cutarrowv( I2.n, While1.e )
selfloopu(I2.s)

###
#
# def-order edges
#
###
arrow from I1.se to I2.nw dashed

ellipseht = saveeh
ellipsewid = saveew
.PE
.sp 2v
.FD <|pdg_slice_figure|> 
The graph and the corresponding program that result from slicing the program
dependence graph from Figure 1 with respect to the final-use vertex for
@i@.@gsize 10@
.FF SP "An HPR slice"

					

Criterion

Slice

Code

.EQ
delim @@
.EN


@gsize 9@\fBprogram\fP @Main@
    @i~:=~1@
    \fBwhile\fP @i~<~11@ \fBdo\fP
        @i~:=~i~+~1@
    \fBod\fP
\fBend\fP(@i@)

					

Criterion

Slice

Code

.PS
ellipseht = ellipseht*.6
ellipsewid = ellipsewid*1.4
Entry: ellipse "ENTRY"

					

Criterion

Slice

Code

.EQ
delim @@
.EN
@gsize 9@\fBprogram\fP @Main@
.PS
xgap = 1.5
ygap = .75
ellipseht = ellipseht*.6
ellipsewid = ellipsewid*1.4
Entry: ellipse "ENTRY"
ellipsewid = ellipsewid*.7
I1: ellipse "@i~:=~1@" at Entry - (.5*xgap, ygap)
While1: ellipse wid ellipsewid*1.4 "\fBwhile\fP @i~<~11@" at I1 + (xgap, 0)

					

Criterion

Slice

Code

.PS 6.0i 2.5i
boxht = boxht / 9
Title: box "Edge Key" invis
boxwid = boxwid/8
ControlE: box with .nw at 1/2 between Title.sw and Title.s invis
ControlD: box with .ne at 1/2 between Title.s and Title.se invis
LoopiE: box with .nw at ControlE.sw invis
LoopiD: box with .ne at ControlD.se invis
LoopcE: box with .nw at LoopiE.sw invis
LoopcD: box with .ne at LoopiD.se invis
DeforderE: box with .nw at LoopcE.sw invis
DeforderD: box with .ne at LoopcD.se invis
"control dependence" at ControlD.w ljust
"loop-independent flow dependence" at LoopiD.w ljust
"loop-carried flow dependence" at LoopcD.w ljust
"def-order dependence" at DeforderD.w ljust
Left: line from ControlE.nw + (-boxwid/4, boxht*1.5) to DeforderE.sw - (boxwid/4,boxht*.5)
Right: line from ControlD.ne + (boxwid*7.30, boxht*1.5) to DeforderD.se + (boxwid*7.30,-boxht*.5)
line from Left.top to Right.top
box wid boxwid*14 with .e at ControlE.w invis

					

Criterion

Slice

Code

.PS
define fatarrowlr   X
.ps +27
        arrow from $1 to $2
            X
xgap = 1.5
ygap = .75
ellipseht = ellipseht*.6
ellipsewid = ellipsewid*1.4
Entry: ellipse "ENTRY"
ellipsewid = ellipsewid*.7
I1: ellipse "@i~:=~1@" at Entry - (.5*xgap, ygap)
While1: ellipse wid ellipsewid*1.4 "\fBwhile\fP @i~<~11@" at I1 + (xgap, 0)
I2: ellipse wid ellipsewid*1.1 "@i~:=~i~+~1@" at While1 + (xgap*.5, -ygap)
IFinal: ellipse wid ellipsewid*1.2 "FinalUse(\fIi\fP)" at While1 + (xgap, 0)
fatarrowlr( Entry.s, IFinal.n, "T" )
arrow from I2.ne to IFinal.sw