text:
% % Terminology collection
% irreducible - несводимый
% single entry single exit (SESE) regions of the control flow graph
% dominators
% control regions
% dominates n and b postdominates
% depth-first traversal
% we can simply visit nodes in reverse depth-first order and maintain a stack of brackets
% connecting the node to an ancestor
% lower endpoint
% brackets originating in the same subtree

% The new bracket originates from the node whose children are being merged, and extends up to the highest node whose brackets come from more than one of the branches. To add this new backedge requires keeping track (at each node in the tree) of the highest node reached by any backedge below this point. The destination of the new backedge from a node is the second"=highest of the node’s children’s highest backedges. This could be found by examination of the bracket sets, but the highest"=ending backedge is not necessarily related to the first bracket in each set (the highest"=originating), so a full search of the bracket set would be necessary.

% control dependent
% Nodes or edges
% reducible graphs
% dominance frontiers
% quick propagation graph
% use of the PST allows structure and sparsity to be exploited simultaneously
% unique entry and exit edges
% multiple edges to the entry node from outside the region, as well as out of the exit node
% bracket
% undirected graph

%% bare_conf.tex
%% V1.4b
%% 2015/08/26
%% by Michael Shell
%% See:
%% http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.8b or later) with an IEEE
%% conference paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/pkg/ieeetran
%% and
%% http://www.ieee.org/

%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE!
%% User assumes all risk.
%% In no event shall the IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%*************************************************************************

% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. The IEEE's font choices and paper sizes can   ***
% *** trigger bugs that do not appear when using other class files.       ***                          ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/

\documentclass[conference]{IEEEtran}
% Some Computer Society conferences also require the compsoc mode option,
% but others use the standard conference format.
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[conference]{../sty/IEEEtran}

\usepackage{algorithm2e}

 % Перевод плагина
\SetKwInput{KwData}{Input parameters}
\SetKwInput{KwResult}{Result}
\SetKwInput{KwIn}{Input data}
\SetKwInput{KwOut}{Output Data}
\SetKwIF{If}{ElseIf}{Else}{if}{then}{else\ if}{else}{end\ of\ condition}
\SetKwFor{While}{while}{execute}{end\ of\ loop}
\SetKw{KwTo}{to}
\SetKw{KwRet}{return}
\SetKw{Return}{return}
\SetKwBlock{Begin}{begin\ block}{end\ block}
\SetKwSwitch{Switch}{Case}{Other}{Check\ a\ value}{and\ execute}{a\ case}{otherwise}{end\ of\ case}{end\ of\ value\ check}
\SetKwFor{For}{loop}{execute}{end\ of\ loop}
\SetKwFor{ForEach}{for\ each}{execute}{end\ of\ loop}
\SetKwRepeat{Repeat}{repeat}{while}
\SetAlgorithmName{Algorithm}{algorithm}{List of algorithms}

% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)

% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/pkg/ifpdf
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.

% *** CITATION PACKAGES ***
%
%\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of the IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off
% such as if a citation ever needs to be enclosed in parenthesis.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 5.0 (2009-03-20) and later if using hyperref.sty.
% The latest version can be obtained at:
% http://www.ctan.org/pkg/cite
% The documentation is contained in the cite.sty file itself.

% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation
% can be obtained at:
% http://www.ctan.org/pkg/graphicx
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found at:
% http://www.ctan.org/pkg/epslatex
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). The IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex

% *** MATH PACKAGES ***
%
%\usepackage{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics.
%
% Note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/pkg/amsmath

% *** SPECIALIZED LIST PACKAGES ***
%
%\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as the IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/pkg/algorithms
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/pkg/algorithmicx

% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/pkg/array

% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.

% *** SUBFIGURE PACKAGES ***
%\ifCLASSOPTIONcompsoc
%  \usepackage[caption=false,font=normalsize,labelfont=sf,textfont=sf]{subfig}
%\else
%  \usepackage[caption=false,font=footnotesize]{subfig}
%\fi
% subfig.sty, written by Steven Douglas Cochran, is the modern replacement
% for subfigure.sty, the latter of which is no longer maintained and is
% incompatible with some LaTeX packages including fixltx2e. However,
% subfig.sty requires and automatically loads Axel Sommerfeldt's caption.sty
% which will override IEEEtran.cls' handling of captions and this will result
% in non-IEEE style figure/table captions. To prevent this problem, be sure
% and invoke subfig.sty's "caption=false" package option (available since
% subfig.sty version 1.3, 2005/06/28) as this is will preserve IEEEtran.cls
% handling of captions.
% Note that the Computer Society format requires a larger sans serif font
% than the serif footnote size font used in traditional IEEE formatting
% and thus the need to invoke different subfig.sty package options depending
% on whether compsoc mode has been enabled.
%
% The latest version and documentation of subfig.sty can be obtained at:
% http://www.ctan.org/pkg/subfig

% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure.
% Be aware that LaTeX2e kernels dated 2015 and later have fixltx2e.sty's
% corrections already built into the system in which case a warning will
% be issued if an attempt is made to load fixltx2e.sty as it is no longer
% needed.
% The latest version and documentation can be found at:
% http://www.ctan.org/pkg/fixltx2e

%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/pkg/stfloats
% Do not use the stfloats baselinefloat ability as the IEEE does not allow
% \baselineskip to stretch. Authors submitting work to the IEEE should note
% that the IEEE rarely uses double column equations and that authors should try
% to avoid such use. Do not be tempted to use the cuted.sty or midfloat.sty
% packages (also by Sigitas Tolusis) as the IEEE does not format its papers in
% such ways.
% Do not attempt to use stfloats with fixltx2e as they are incompatible.
% Instead, use Morten Hogholm'a dblfloatfix which combines the features
% of both fixltx2e and stfloats:
%
% \usepackage{dblfloatfix}
% The latest version can be found at:
% http://www.ctan.org/pkg/dblfloatfix

% *** PDF, URL AND HYPERLINK PACKAGES ***
%
\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version and documentation can be obtained at:
% http://www.ctan.org/pkg/url
% Basically, \url{my_url_here}.

% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )

% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}

% FIXME Remove, when got ready to publish
\usepackage[usenames,dvipsnames,svgnames,table]{xcolor}
\definecolor{rclr}{rgb}{0.5,0.1,0.1}
\definecolor{eclr}{rgb}{0,0.5,0.5}
\colorlet{acolor}{blue}
\colorlet{rcolor}{red}
\definecolor{ncolor}{rgb}{0.5,0.5,0.1}
\newcommand{\aaa}[2][acolor]{\noindent\textcolor{eclr}%
{+\ [}\textcolor{#1}{#2}\textcolor{eclr}{]}}
\newcommand{\rrr}[2][rcolor]{\noindent%
\textcolor{eclr}{-\ [}\textcolor{#1}{#2}\textcolor{eclr}{]}}
\newcommand{\nnn}[2][ncolor]{\noindent%
\textcolor{eclr}{!\ [}\textcolor{#1}{#2}\textcolor{eclr}{]}}

\begin{document}
%
% paper title
% Titles are generally capitalized except for words such as a, an, and, as,
% at, but, by, for, in, nor, of, on, or, the, to and up, which are usually
% not capitalized unless they are the first or last word of the title.
% Linebreaks \\ can be used within to get better formatting as desired.
% Do not put math or special symbols in the title.
\title{Control Flow Graph Visualization in\\ Compiled Software Engineering}

% author names and affiliations
% use a multiple column layout for up to three different
% affiliations
\author{\IEEEauthorblockN{Andrey Mikhailov${}^{*}$, Aleksey Hmelnov${}^{*}$, Evgeny Cherkashin${}^{*\;**}$ and Igor Bychkov${}^{*}$}
\IEEEauthorblockA{${}^{*}$Matrosov Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences, \\
${}^{**}$National Research Irkutsk State Technical University,\\
Irkutsk, Russian Federation\\
\texttt{\{mikhailov,alex,eugeneai,bychkov\}@icc.ru}}
}
% conference papers do not typically use \thanks and this command
% is locked out in conference mode. If really needed, such as for
% the acknowledgment of grants, issue a \IEEEoverridecommandlockouts
% after \documentclass

% for over three affiliations, or if they all won't fit within the width
% of the page, use this alternative format:
%
%\author{\IEEEauthorblockN{Michael Shell\IEEEauthorrefmark{1},
%Homer Simpson\IEEEauthorrefmark{2},
%James Kirk\IEEEauthorrefmark{3},
%Montgomery Scott\IEEEauthorrefmark{3} and
%Eldon Tyrell\IEEEauthorrefmark{4}}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}School of Electrical and Computer Engineering\\
%Georgia Institute of Technology,
%Atlanta, Georgia 30332--0250\\ Email: see http://www.michaelshell.org/contact.html}
%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
%Email: homer@thesimpsons.com}
%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
%Telephone: (800) 555--1212, Fax: (888) 555--1212}
%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}}

% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}

% make the title area
\maketitle

% As a general rule, do not put math, special symbols or citations
% in the abstract
\begin{abstract}
Engineering of the compiled software is an important task in software engineering.  One of the stages of the engineering technologies is a construction and analysis of a control flow graphs, which reflect a general structure of algorithms.  The paper presents a technique for analyzing and visualizing the control flow graph of a compiled software.  The analysis is based on semantically equivalent transformations of the original graph resulting in an abstract node that contains a hierarchy of isolated regions, which then associated with predefined templates resulting a graphical representation.  The templates and additional signature data allow one to recognize the high-level programming structures and user statements to construct a flow-chart notation of the original program.

%%%% It is important stages in reverse engineering.
\end{abstract}

% no keywords

% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle

\section{Introduction}

Reverse engineering of compiled software (programs after processing its source code by a compiler) is an important task in software engineering as it allows one to solve a wide variety of software quality assessment problems, such as productivity of compiled code, quality of compiler and system libraries, peculiarities of hardware architectures the program running on.  Reverse engineering is also used for regain the access to legacy code, whose source counterpart is already lost, and for investigation of virus and malicious program behavior.  One of the helpful stages of reverse engineering techniques is a construction and analysis of so-called control flow graph that reflects a general structure of corresponding algorithms.  Artificial intelligence techniques such as pattern recognition and rewrite rule engines have extensive use in the analysis.

The control flow graph is a natural representation that can be automatically figured out from the source code or its compiled binaries.  The graph is used by compiler as an intermediate structure for optimizing transformations.  The source code text contains all the necessary information of program behavior.  Its analysis usually is a complex task even with technological support of nowadays integrated development environments, which make the analysis significantly easier.

Binary code analysis is a more complex task, and it requires a complex IT knowledge.  Special software such as disassemblers and decompilers are used to partially automatize control flow analysis and visualization.  The decompiling a binary runtime is in principle an impracticable task: the reconstructed high-level code is more difficult in understanding as compared to its assembler representation.  The visual analysis of the control flow graph is an alternate way.  There are a number of visual representation and processing software, which are relatively universal, such as uDraw (daVinci)~\cite{10}, VCG~\cite{14}, Graphlet~\cite{12}, GraVis~\cite{13}, Graph Drawing Server~\cite{9}, graphViz~\cite{11}, VisualGraph~\cite{15}.  These systems have a rich general toolkit but visualization and analysis of control flow graph requires a special processing routines. Algorithms of graph visualization are developed since 60th~\cite{7}.  The results of P.~Eades~\cite{5}, T.~Kamada and S.~Kawai~\cite{q1} considered to be classical in this research field, they deal with universal approaches to graph visualization problems.

The control flow graph is directed and usually visualized by means of layers~\cite{4}.  The process consists of four stages:
\begin{itemize}
\item [] \textbf{Distribution of graph nodes between layers.} Each node is assigned a rank.  All directed edges can connect nodes from a lower rank to a higher one.  Obviously, nodes of the same rank cannot be connected.  Rank distribution of the nodes is performed with various techniques, the simplest one is based on path length calculation in depth-first graph traversal procedure.
\item []\textbf{Defining order on the nodes in a layer.} The nodes of a layer are ordered according to principle of minimization of intersections of edges.  Method of median~\cite{8} is most widely used as a technique for solving the problem.
\item []\textbf{Figuring out of the node coordinates in a layer.} Each node of each layer is assigned a coordinate so as the graph will correspond to predefined aesthetic criteria.
\item []\textbf{Edge drawing.} On this stage the edges are drawn according to rules of visualization, for example, edges can be indirect lines.
\end{itemize}

The paper describes a technique and software tools for analyzing and visualizing the control flow graph of a compiled binaries.  The analysis is based on semantically equivalent transformations of the original graph resulting in a singular abstract node that contains a hierarchy of isolated regions (subgraphs).  The regions are associated with predefined templates to form resulting graphical representation.  The templates and additional signature data for library modules allow one to recognize the regions as high-level programming language structures and statements to construct, e.g., flow-chart notation of the original program.\enlargethispage{-2.5em}

\section{Theoretical basis of control flow\\ graph visualization}

An directed graph $G(V,E)$ is a \emph{control flow graph} if the following restrictions hold:
\begin{enumerate}
\item graph $G$ does not contain multiple edges between the same nodes;
\item node $start\in V$ is the entrance to the graph (\emph{start node});
\item node $end \in V$ is the exit from the graph (\emph{terminal node});
\item each node $v \in V$ is accessible from $start$;
\item node $end$ is accessible from each node $v \in V$.
\end{enumerate}
If a control flow graph has more than one terminal node, the terminal nodes are connected to one new fictitious terminal node.

We will use additional notions taken from \cite{sese} and used further in the paper.  A node $x$ is a \emph{dominator} of $y$ ($x\quad dom\quad y$) in a directed graph, if any path from $start$ to $y$ includes $x$.  A node $x$ is a \emph{postdominator} of $y$ ($x\quad pdom\quad y$), if any path from $y$ to $end$ includes $x$.  By convention, a node dominates and postdominates itself.  A node $x$ is an \emph{immediate dominator} of $y$ ($x\quad idom\quad y$), if $x\quad dom\quad y$ and there are no such $p$ that $x\quad dom\quad p$ and $p\quad dom\quad y$.  A node $x$ is an \emph{immediate postdominator} of $y$ ($x\quad pidom\quad y$), if $x\quad pdom\quad y$ and there are no such $p$ that $x\quad pdom\quad p$ and $p\quad pdom\quad y$.

Let $a$ and $b$ be a pair of distinct edges in a control flow graph.  The ordered pair of $a$ and $b$ will be denoted as $\langle a,b \rangle$.  If 1) $a$ dominates $b$, 2) $b$ postdominates $a$, and c) every cycle containing $a$ also contains $b$ (and vice versa), then the pair $\langle a,b \rangle$ is referred to as a \emph{single entry single exit region} (SESE region).  In the SESE region, $a$ is the entry edge and $b$ is the exit edge.

The first condition ensures that every path from $start$ (of the whole graph) into the region passes through the entry edge $a$.  The second condition ensures that every path from inside the region to $end$ passes through the exit edge $b$.  The third condition implements two constraints: every path from inside the region to $a$ point ‘above’ $a$ passes through the exit $b$, and every path from a point ‘below’ $b$ to a point inside the region passes through the entrance $a$, i.e., these path go around the SESE region.

Two SESE regions in a control flow graph must be either folded or do not overlap (contain no common nodes) \cite{sese}.  Structural analysis on the base of recognition of SESE regions commonly used for efficient construction of an intermediate image in a so called \emph{static single assignment} (SSA) form, as well as in data flow analysis.  SESE regions are also organized in \emph{program structure trees} (PST), which represent the control flow graph as hierarchy of folded regions (SESE regions and individual nodes folding tree).  Each of the PST tree nodes denote a procedure consisting of other procedures and individual operators.

A control flow graph subgraph having one entry and one exit nodes is referred to as \emph{two terminal region} (TT region).  TT regions emphasize the points of control flow convergence and the following divergence (Fig.~\ref{fig:TTRegion}).  The requirement condition of TT region recognition are weaker as compared to SESE regions, so all the SESE regions are TT regions but not vice versa.
\begin{figure}[tb]
	\centering
		\includegraphics[width=0.4\linewidth]{Pic/TTRegion.eps}
	\caption{A two terminal region}
	\label{fig:TTRegion}
\end{figure}

For the structural programming language, TT region corresponds to a branching operator or a cycle.  Our approach to the control flow graph visualization is based on recognition of TT regions and classification them into finite set of variants concerned with various control flow operators of the original high-level programming language.  TT regions of program graph of control flow replaced with abstract nodes (folded) form an analysis basis of visualization.

\subsection{Quality criteria of the control flow graph visualization}
\label{sec:qcrit}

A display of the nodes and the edges of a graph on a surface (or in a 3d-space) is referred to as a \emph{graph layout}.  A graph can be visualized using various layouts (Fig.~\ref{fig:VisExample}), and different layouts are defined by sets of display rules and criteria of result assessment.

\begin{figure}[b]
	\centering
		\includegraphics[width=0.4\textwidth]{Pic/Pic1.eps}
	\caption{Various layouts of the same graph}
	\label{fig:VisExample}
\end{figure}

The main quality criterion of a control graph visualization is the correspondence of the constructed image to the nature of the visualized informational object.  The quality assessment depends on various structural and semantic characteristics of the object.  Three basic feature sets are emphasized specially among the criteria: \emph{visual arrangement}, \emph{aesthetics}, \emph{restrictions}.
\begin{itemize}
\item []\textbf{Visual arrangement} is the main set of rules that a graph representation must obey to be acceptable as a desired result.  For example, to visualize programs as a flowchart, layout engine must obey agreement rules, which represent all the graph nodes as flowchart symbols and the edges as polylines consisting only with vertical and horizontal sections.  In a general case, an visual arrangement can be sufficiently complex and include a lot of details related to the target representation.
\item []\textbf{Aesthetics} is a subset of the criteria that defines attributes of the constructed image, which must be obeyed as much as possible to improve visibility.  A widely used aesthetic criteria are the following: minimizing a number of edge intersections, minimizing a number of foldings, minimizing the occupation area, maximizing the resolution, minimizing the total edge length, unification of edge lengths, minimizing the number of foldings on an edge, foldings unification, maximizing a symmetry of graph representation, etc. % минимизация коэффициента сторон.
\item []\textbf{Restrictions} are a subset of the criteria that define layout rules for peculiar elements and subgraphs of the constructed image.  The most common used criteria are \emph{the center} that define whether the root node must be placed at the center of the image, \emph{externality} that define the necessity to place a node outside a region, \emph{cluster} defines that a number of nodes to be placed together near to each other, \emph{sequence} defines the order of nodes placement during drawing paths (left to right, top-bottom).
\end{itemize}

A control flow graph reconstructed from a binaries consists of operator block nodes, starting node, and an non-empty set of finish nodes, as well as edges correspond to the transfer of control.  A natural image of the control flow graph is a flowchart diagram.  For the flow charts we define the following visual arrangement for its nodes (Fig.~\ref{fig:blocks}):
\begin{itemize}
\item []\textbf{Operator shape} represents a node where the control flow passed only one direction.
\item []\textbf{Decision shape} corresponds to conditional operators in high-level programming languages; in a control flow graph it is a node, where flow control splits up.
\item []\textbf{Cycle edge shapes} denote two graph nodes, one is for beginning of the cycle and one for its end, the cycle body is located between these shapes.
\item []\textbf{Starting and terminal shapes} mark the entrance and the exit from a function or a program.
\end{itemize}

\begin{figure}[b]
  \centering
  \begin{minipage}[b]{0.24\linewidth}
    \center{\includegraphics[width=0.35\textwidth]{Pic/BlocksA.eps} \\ \footnotesize\emph{a})\\ operation}
  \end{minipage}
  \hfill
  \begin{minipage}[b]{0.24\linewidth}
    \center{\includegraphics[width=0.35\textwidth]{Pic/BlocksB.eps} \\ \footnotesize\emph{b})\\ decision}
  \end{minipage}
  \begin{minipage}[b]{0.24\linewidth}
    \center{\includegraphics[width=0.5\textwidth]{Pic/BlocksC.eps} \\ \footnotesize\emph{c})\\ cycle edges}
  \end{minipage}
  \begin{minipage}[b]{0.24\linewidth}
    \center{\includegraphics[width=0.35\textwidth]{Pic/BlocksD.eps} \\ \footnotesize\emph{d})\\ start/termination}
  \end{minipage}

  \caption{Types of shapes used in flow charts}
  \label{fig:blocks}
\end{figure}

In this paper, we consider a layout algorithm that visualizes control flow according to criteria defined for flowcharts.

\section{Control flow graph visualization}
\label{sec:cfg-vis}

Nowadays programming languages in most cases contain a standard set of high-level control flow operators (\texttt{if-then}, \texttt{if-then-else}, \texttt{for}, \texttt{while}, etc.).  These operators produce their specific subgraphs during compilation.  For example, \texttt{if-then} operator produces a graph depicted in Fig.~\ref{fig:IfSt}, where \texttt{then} part could correspond to another control subgraph.
\begin{figure}[htbp]
	\centering
		\includegraphics[width=0.11\textwidth]{Pic/Pic2.eps}
	\caption{Subgraph of \texttt{if-then} operator}
	\label{fig:IfSt}
\end{figure}

One can describe a corresponding subgraphs for all flow control operators of all standard high-level languages.  Each generated subgraph is described as a template.  The control operators are revealed and reconstructed in whole flow control graph by means of recognition of the templates in the graph and folding the recognized structure into an abstract node.  The edges terminating at and originating from the abstract node are reconnected accordingly.  The reconstruction process is repeated until either the graph folds into one abstract node, and in this case the graph is referred to as \emph{reducible}, or there is a subgraph that does not correspond to any of the templates.  In the last case the graph is called \emph{inreducible}, and the subgraph that was not recognized is named \emph{undeterminate}.

Structural high-level programming language compilers produce only reducible flow control graphs.  This will hold for most of other languages as long as \texttt{goto} operator is not used explicitly or implicitly.  There are two approaches for overcoming the problem of folding impossibility:
\begin{enumerate}
\item Perform riddance operation over undeterminate subgraphs.  The essential disadvantage of the approach is the necessity of addition and deletion of nodes and edges in the graph, this is not allowed in control flow graph model visualization.
\item Recognize the undeterminate subgraph and replace it with an abstract node.
\end{enumerate}

\subsection{Algorithm of control flow graph structuring}
\label{sec:algor-contr-flow}

The developed algorithm is based on structural analysis technique proposed in~\cite{17} that suggests recognizing subgraph of a predefined form with templates and replacing them with an abstract node, then edge endpoints reassignation is performed accordingly.  Template application is carried out according to depth-first order until the graph folds into one abstract node.  A tree of dominators is constructed.  The tree is used for edge classification and cycle recognition.  The result quality strongly depends on template application order.  The algorithm is as follows:

\begin{algorithm}[h]
\caption{Algorithm of control flow graph structuring}
\label{alg:struct}
\SetAlgoLined %% Connects logical parts with lines
\KwData{G, D, P}
\KwResult{An abstract node containing a hierarchy of folded subgraphs}
%\While{$|E| \neq 0$ и $|V| \neq 1$}{
	\ForEach{$v \in D$ in a backward breadth-first order}{
		\ForEach{$p \in Children(v)$}{
			\If{$p\quad pidom\quad v$}{
				$S \leftarrow Children(v) \setminus p $ \\
				\If{$Classify\_Region(S) \neq \textit{undeterminated}$}{
					$Apply\_Template(S)$
				}\Else{
					$Hierarchical\_Layout(S \cup p)$ \\
					$Recognize\_Undeterminanted\_Region(S)$
				}
				$Modify(G,D,P)$
			}
		}
	}
%}
\end{algorithm}

% Построим дерево доминиаторов $D$ и постдоминаторов $P$ для графа $G(E,V)$.
% In order to construct a tree of dominator $D$ and postdominator $P$.

If a program has no predefined terminating nodes, the nodes is figured out by means of the following procedure.  Firstly, the edges are categorized as \emph{forward}, \emph{backward}, and \emph{cross} directed.  Among nodes connected with forward edges, there will be at least one that has no source edge.  If we found the only node, then the node is the termination.  Otherwise all such nodes are connected with edges to an additional fictitious termination node.  The obtained graph is correct as the termination node is accessed from any node of the graph.

Traversing of the dominator tree is done in a reverse breadth-first order, i.e. from leaves to the root, placing graph nodes in a \texttt{stack} structure.  A region having the deepest folding level (TT region) is determined on each iteration of the algorithm according to the rule $p$~$pidom$~$v$: the postdominator of node $v$ of $S$ is the terminal node, where the control flow passing $v$ converges.  This node is not added to the recognized region as it could be terminal node of other region of the graph.

%line 280 Cannot understand the essence.

As soon as a set of nodes of a TT region is recognized, the region is categorized with templates (Fig.~\ref{fig:Regions}), which are sequentially applied to it.  If the region corresponds to a template it is considered to be \emph{determined} otherwise \emph{undetermined}.

For the determined regions a new abstract node is constructed.  The node embodies its subgraphs, and bounding rectangle of the region calculated according to rules defined in the template.  The Hierarchical layout engine is applied to the undetermined regions followed by figuring out the bounding rectangle with respect to the node coordinates.  The undetermined region is replaced with new abstract node.

Finally, we obtain one abstract region, having no input and output edges.  The region will contain all the hierarchy of folded subroutines.  The bounding rectangle is figured out for the region.  All graph nodes will be located inside this rectangle.

\begin{figure}[b]
	\centering
		\includegraphics[width=0.49\textwidth]{Pic/Reg.eps}
	\caption{Applicable templates}
	\label{fig:Regions}
\end{figure}

\subsection{Layout engine}
\label{sec:raskladka-process}

The layout process is carried out recursively from top region down to lower regions.  For the top region initial coordinates is predefined.  If a region has a template with visualization rules, the rules are applied.  The layout example if \texttt{if-then-else} operator is given in Fig.~\ref{fig:IfThenElse}.

\begin{figure}[b]
	\centering
		\includegraphics[width=0.3\textwidth]{Pic/IfThenElse.eps}
	\caption{Visualizing template of \texttt{if-then-else} operator}
	\label{fig:IfThenElse}
\end{figure}

The coordinate computation rules for \texttt{if-then-else} operator is as follows:
\begin{itemize}
\item [] \texttt{if.x = x + abs(width - if.width) / 2};
\item [] \texttt{then.x = x  + wDist / 2, then.y = y + if.height + hDist};
\item [] \texttt{else.x = x - else.width - wDist / 2, else.y = y + if.height + hDist};
\end{itemize}
where \texttt{wDist} is a vertical distance between nodes, \texttt{hDist} is a horizontal distance.  These parameters is defined manually and reflect aesthetic criteria.  The visualizing rules are defined analogously for each template.  Thus, the layout engine consists of sequential applications of the visualizing rules to the folded regions.

\section{Implementation}
\label{sec:implementation}

The algorithm is implemented in the Java programming language.  The main application is named ``VisualGraph'' and implemented using authors' library ``JGraphX'' containing the subroutines of the algorithm.  The application uses hierarchical graph models for the control flow visualization using authors' and other known popular visualization algorithms.  The ``JGraphX'' library allows one to make images of control flow graphs by defining shapes and colors for nodes, drawing edges between nodes and corner points automatically and manually.

At present the library and application support some visual arrangement criteria from section \ref{sec:qcrit}.  Categorization of nodes in branching regions of the control flow graph requires that the graph will be attributive and contain assembler code of the main program blocks (lineal parts of code).  The control flow graph itself is obtained from assembler program semantics analysis by means of authors' FlexT based utilities \cite{flext}.

% An example of a floating figure using the graphicx package.
% Note that \label must occur AFTER (or within) \caption.
% For figures, \caption should occur after the \includegraphics.
% Note that IEEEtran v1.7 and later has special internal code that
% is designed to preserve the operation of \label within \caption
% even when the captionsoff option is in effect. However, because
% of issues like this, it may be the safest practice to put all your
% \label just after \caption rather than within \caption{}.
%
% Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
% option should be used if it is desired that the figures are to be
% displayed while in draft mode.
%
%\begin{figure}[!t]
%\centering
%\includegraphics[width=2.5in]{myfigure}
% where an .eps filename suffix will be assumed under latex,
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
%\caption{Simulation results for the network.}
%\label{fig_sim}
%\end{figure}

% Note that the IEEE typically puts floats only at the top, even when this
% results in a large percentage of a column being occupied by floats.

% An example of a double column floating figure using two subfigures.
% (The subfig.sty package must be loaded for this to work.)
% The subfigure \label commands are set within each subfloat command,
% and the \label for the overall figure must come after \caption.
% \hfil is used as a separator to get equal spacing.
% Watch out that the combined width of all the subfigures on a
% line do not exceed the text width or a line break will occur.
%
%\begin{figure*}[!t]
%\centering
%\subfloat[Case I]{\includegraphics[width=2.5in]{box}%
%\label{fig_first_case}}
%\hfil
%\subfloat[Case II]{\includegraphics[width=2.5in]{box}%
%\label{fig_second_case}}
%\caption{Simulation results for the network.}
%\label{fig_sim}
%\end{figure*}
%
% Note that often IEEE papers with subfigures do not employ subfigure
% captions (using the optional argument to \subfloat[]), but instead will
% reference/describe all of them (a), (b), etc., within the main caption.
% Be aware that for subfig.sty to generate the (a), (b), etc., subfigure
% labels, the optional argument to \subfloat must be present. If a
% subcaption is not desired, just leave its contents blank,
% e.g., \subfloat[].

% An example of a floating table. Note that, for IEEE style tables, the
% \caption command should come BEFORE the table and, given that table
% captions serve much like titles, are usually capitalized except for words
% such as a, an, and, as, at, but, by, for, in, nor, of, on, or, the, to
% and up, which are usually not capitalized unless they are the first or
% last word of the caption. Table text will default to \footnotesize as
% the IEEE normally uses this smaller font for tables.
% The \label must come after \caption as always.
%
%\begin{table}[!t]
%% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
% if using array.sty, it might be a good idea to tweak the value of
% \extrarowheight as needed to properly center the text within the cells
%\caption{An Example of a Table}
%\label{table_example}
%\centering
%% Some packages, such as MDW tools, offer better commands for making tables
%% than the plain LaTeX2e tabular which is used here.
%\begin{tabular}{|c||c|}
%\hline
%One & Two\\
%\hline
%Three & Four\\
%\hline
%\end{tabular}
%\end{table}

% Note that the IEEE does not put floats in the very first column
% - or typically anywhere on the first page for that matter. Also,
% in-text middle ("here") positioning is typically not used, but it
% is allowed and encouraged for Computer Society conferences (but
% not Computer Society journals). Most IEEE journals/conferences use
% top floats exclusively.
% Note that, LaTeX2e, unlike IEEE journals/conferences, places
% footnotes above bottom floats. This can be corrected via the
% \fnbelowfloat command of the stfloats package.

\section{A layout example}

Let's consider a result of our algorithm in comparison to one of hierarchic layout engines (Fig.~\ref{fig:image1}).  In the figure, our algorithm (\emph{b}) specially emphasizes the backward edge that corresponds to a loop.  The edge style is visually distinguishable from other edges.  The algorithm also marks the terminal nodes.  Such visualization features allow to recognize visually the regions of interest and other kinds of analysis.  In Fig.~\ref{fig:image1}\emph{a}, the edges are represented with straight plain lines (except edge connecting \texttt{v9} and \texttt{v5}).  This will ease of control transferring analysis as compared to the form in Fig.~\ref{fig:image1}\emph{б}. Note, that the proposed algorithm accounts not all the variants of control flow patterns and can be improved for example to support undetermined edges removal in a region.

%  а) иерархический, б) структурный
% fig
\begin{figure}[b]
	\begin{minipage}[b]{0.49\linewidth}
	\center{\includegraphics[width=0.75\textwidth]{Pic/Hgraph.pdf} \\\footnotesize \emph{a}) hierarchical}
	\end{minipage}
\hfill
\begin{minipage}[b]{0.49\linewidth}
	\center{\includegraphics[width=0.94\textwidth]{Pic/Sgraph.pdf} \\\footnotesize \emph{b}) structural}
	\end{minipage}
	\caption{Layouts of a control flow graph}
	\label{fig:image1}
\end{figure}

\section{Conclusion}
We have proposed and implemented a software tools realizing an approach to surface graph layout on the base of techniques of structural analysis.  The main difference of our approach as compared to the mentioned (in the paper) techniques is the usage of a set of matching rules, which are applied to the terminal nodes (a special subgraph) to recognize original control flow structures of high-level programming language.

A probation of the developed algorithms was performed on CPU2000 test set\footnote{https://www.spec.org/cpu2000/ --- Standard Performance Evaluation Corporation.  SPEC CPU2000 is a test set for assessment of the performance of a central processing unit. The test are used for compiler quality evaluation.}.  The following results are obtained:
\begin{itemize}
\item 197.parser (Syntactic parser of a natural language);
\item 252.eon (Ray tracing).
\end{itemize}

The automation of the flow control analysis allows an engineer to devote more efforts for description of the templates increasing both the personal productivity and detail level of the software description.

The results of the control flow graph analysis could be used in construction of Model driven engineering (MDE)~\cite{mda} software development tools.  The nowadays approaches to MDE is based on change propagation between various models of the software, e.g., source code generation from UML and BPMN2.0, and (in backward direction) refactoring the high-level models according to local source code modification.  Comparing results of control flow graph analysis could determine initial change of the structure of the source code, then the change is propagated to the higher-level models.  This is however a very complex fundamental problem containing both deduction and induction logical inferences.

% conference papers do not normally have an appendix

% use section* for acknowledgment
\section*{Acknowledgment}

The development partially support by Russian Foundation of Fundamental Research, grant No 16-07-00411, ``Technologies Development for Dynamic Planning of Service Compositions Execution in a Cloud Environment''.

% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://mirror.ctan.org/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
%\bibliographystyle{IEEEtran}
% argument is your BibTeX string definitions and bibliography database(s)
%\bibliography{IEEEabrv,../bib/paper}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
\begin{thebibliography}{9}

\bibitem{10} M.~Frohlich, M.~Werner, \emph{Demonstration of the Interactive Graph Visualization System daVinci}, LNCS~894, 1995,~P.~266--269.

\bibitem{14} G.~Sander, \emph{Graph loyout through the VCG tool}, LNCS~894, 1995, P.~194--205.

\bibitem{12} M.~Himsolt, \emph{Graphlet System (System Demonstration)}, LNCS~1990, 1996. P.~233--240.

\bibitem{13} H.~Lauer, M.~Ettrich, K.~Soukup, \emph{GraVis System Demonstration}, LNCS~1353, 1997, P.~344--349.

\bibitem{9} S.~Bridgeman, A.~Garg, R.~Tamassia, \emph{A Graph Drawing and Translation Service on the WWW}, LNCS~1190, 1996, P.~45--52.

\bibitem{11} E.~R.~Gasner, S.~C.~North, \emph{An Open Graph Visualization System and its Applications to Software Engineering}, \url{http://www.graphviz.org/Documentation/GN99.pdf}

\bibitem{15} T.~A.~Zolotukhin, \emph{Graph Visualization with Programming System ``Visual Graph''}, Computer Science in Science and Education, 2012, P.~135--148. (in~Russian)

\bibitem{18} A.~A.~Mikhailov, \emph{Control Flow Graph Analysis in Decompilation of Object Files dcuil}, Vestnik of Novosibirsk State University, Computer Science Technologies Series, 2014, Vol.~12, Issue~2, P.~74--79. (in~Russian)

\bibitem{1} V.~N.~Kasyanov, \emph{Visualizing Information on the Base of Graph Models}, Computational Technologies, 1999. Vol.~11, No.~11, P.~1123--1135. (in~Russian)

\bibitem{7} W.~T.~Tutte, \emph{How to Draw a Graph}, Proc. of London Math. Society. 1963. 13(52),  P.~743--768.

\bibitem{5} P.~A.~Eades, \emph{A Heuristic for Graph Drawing}, Congressus Numerantium, 1984, 42,  P.~149--160.

\bibitem{q1} T.~Kamada, S.~Kawai, \emph{An Algorithm for Drawing General Undirected Graphs}, Inform. Process. Lett, 1989, 31, P.~7--15.

\bibitem{4} P.~Eades, L.~Xuemin, \emph{How to Draw a Directed Graph}, Visual Languages, 1989, IEEE Workshop on, IEEE, 1989, P.~13--17.

\bibitem{8} P.~Eades, N.~C.~Wormald, \emph{The Median Heuristic for Drawing 2--Layered Networks}, Technical Report 69, Dept. of Computer Science, University of Queensland, 1986.

\bibitem{16} A.~V.~Aho, R.~Sethi, J.~D.~Ullman, \emph{Compilers: Principles, Techniques, And Tools}, Addison Wesley, 1986.  MLA

\bibitem{17} C.~Cifuentes, \emph{Structuring Decompiled Graphs. Compiler Construction}, Springer Berlin Heidelberg, 1996, P.~91--105.

\bibitem{3} R.~Johnson,D.~Pearson, and K.~Pingali, \emph{Finding regions fast: Single entry single exit and control regions in linear time}. Tech. rep., Cornell University, Ithaca, NY, 1993

\bibitem{sese} R.~Johnson, D.~Pearson, K.~Pingali, \emph{The Program Structure Tree: Computing Control Regions in Linear Time}, In PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, New York, NY, USA, 1994. ACM. p.~171--185. \url{http://iss.ices.utexas.edu/Publications/Papers/PLDI1994.pdf} (access data: 12.02.2016)

\bibitem{flext} A.~Hmelnov, S.~Vassilyev, \emph{Data description language FlexT: flexible types for description of static data}, Proceedings of CSCC'99 Multiconference. P.~1371-1376 URL:\url{http://www.wseas.us/e-library/conferences/athens1999/Papers/137.pdf} (access date: 12.01.2016)
\bibitem{mda} E.~A.~Cherkashin, V.~V.~Paramonov, et al, \emph{Model Driven Architecture is a Complex System}. E-Society Journal Research and Applications 2 (2), 15--23.

%\bibitem{IEEEhowto:kopka}
%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%  0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.

\end{thebibliography}

% that's all folks
\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:


text:
\documentclass{article}
%\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}

\makeatletter
\def\BState{\State\hskip-\ALG@thistlm}
\makeatother

\begin{document}

  \title{Continuous optimisation: \\
    \large The basu's problem}
  \author{PALLAMIDESSI Joseph, ERSFELD Thomas}
  \maketitle

  \section{Introduction} % (fold)
  \label{sec:Intr}
    \paragraph{} % (fold)
    \label{par:}
    The goal of this project is to provide a set of the 22 constants to the
    function derived from article\cite{} to fit a gaussian function of $\mu=1.5$ and
    $\phi=0.2$.

    %Gaussian
    % paragraph  (end)
  % section Intr (end)

  \section{Implementation} % (fold)
  \label{sec:Implementation}
    \subsubsection{Genome definition} % (fold)
    \label{ssub:Genome definition}

      \paragraph{} % (fold)
      \label{par:}
        The genome is defined as an array of 22 doubles, so each value is mapped to a
        specific product value as explained by the following table:
      % paragraph  (end)
      \\
      \\
      \scalebox{0.7}{
        \begin{tabular}{ |c |c |c |c |c |c |c |c |c |c |c |c}
          \hline
          1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline
          kTR1 & KA1 &nA1&dmRNA1&kTL1&dLaclI&KTL1'&dCI&kTR2 & KR2 &nR2    \\
          \hline
        \end{tabular}
      }
      \\
      \\
      \scalebox{0.7}{
        \begin{tabular}{ |c |c |c |c |c |c |c |c |c |c |c |c}
          \hline
          12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22  \\ \hline
          dmRNA2 & kTL2 & dLacl & kTR3 & KR3 & nR3 & KR3' & nR3' & dmRNA3 & kTL3 & dGFP  \\
          \hline
        \end{tabular}
      }

      % The table

      \paragraph{} % (fold)
      \label{par:}
        For the result of this report we will refer to each cell of the array
        (ie. parameter that we tried to optimize) as genes.
      % paragraph  (end)

    % subsubsection Genome definition (end)
    \subsubsection{Initialization} % (fold)
    \label{ssub:initialization}

      \paragraph{} % (fold)
      \label{par:}
        For each gene, we defined its bounds as given by this project subject.
        Here is a quick reminder:
      % paragraph  (end)

      \begin{figure}
      \begin{small}
        \begin{tabular}{ | c |c | c |}
          \hline
            Parameter & min & max \\ \hline
            kTR1 &            0,001           &    1000000   \\ \hline
            KA1 &             0,0001          &    1000 \\ \hline
            nA1 &             1               &    4 \\ \hline
            dmRNA1 &          0,001           &    0,1 \\ \hline
            kTL1 &            0,0000001       &    0,00001 \\ \hline
            dLaclI &          0,0001          &    0,01 \\ \hline
            KTL1' &           0,0000001       &    0,00001 \\ \hline
            dCI &             0,0001          &    0,01 \\ \hline
            kTR2 &            0,001           &    1000000 \\ \hline
            KR2 &             0,0001          &    1000 \\ \hline
            nR2 &             1               &    4 \\ \hline
            dmRNA2 &          0,001           &    0,1 \\ \hline
            kTL2 &            0,0000001       &    0,00001 \\ \hline
            dLacl &           0,0001          &    0,01 \\ \hline
            kTR3 &            0,001           &    1000000 \\ \hline
            KR3 &             0,0001          &    1000 \\ \hline
            nR3 &             1               &    4 \\ \hline
            KR3' &            0,0001          &    1000 \\ \hline
            nR3' &            1               &    4 \\ \hline
            dmRNA3 &          0,001           &    0,1 \\ \hline
            kTL3 &            0,0000001       &    0,00001 \\ \hline
            dGFP &            0,0001          &    0,01i   \\
            \hline
        \end{tabular}
      \end{small}
      \end{figure}
      % table of bounds

    % subsubsection initialization (end)

    \subsubsection{Evaluation} % (fold)
    \label{ssub:Evaluation}

      \paragraph{} % (fold)
      \label{par:}
        We decided to use a sample of the target function and the function to optimize
        with a sampling rate of 100, in the hope of having a very close approximation.
        The fitness function used is a Root-mean-square deviation of the two vectors
        resulting from the sampling.
        \\
        \\
        RMSD = $\sqrt{\frac{\sum_{t=1}^n (x_{1,t} - x_{2,t})^2}{n}}$
      % paragraph  (end)

    % subsubsection Evaluation (end)

    \subsubsection{Crossover} % (fold)
    \label{ssub:Crossover}

      \paragraph{} % (fold)
      \label{par:}

        Since we are dealing with real value parameters, the crossover function
        is a simple barycentric one, which is commonly found in a lot of continous
        optimization genetic algorithms.
      % paragraph  (end)

      \begin{algorithm}
      \caption{Barycentric crossover}\label{pseudo1}
      \begin{algorithmic}[1]
      \Procedure{Crossover}{}
      \ForAll{gene in Genome}
        \State $alpha\gets random(0.,1.)$
        \State $Child.gene\gets alpha * Parent1.gene + (1. - alpha) * Parent2.gene$
      \EndFor
      \EndProcedure
      \end{algorithmic}
      \end{algorithm}

    % subsubsection Crossover (end)

    \subsubsection{Mutator} % (fold)
    \label{ssub:Mutator}

      \paragraph{} % (fold)
      \label{par:}
        Once again a simple technique was used. Given a constant mutation parameter,
        for each gene of the genome a chance is given to add or substract a random value
        within this mutation limit. We then avoid genes values going outside of their
        bounds by capping the values by the genes value bounds.
      % paragraph  (end)

      \begin{algorithm}
      \caption{Mutator operator}\label{pseudo2}
      \begin{algorithmic}[2]
      \Procedure{Mutator}{}
      \ForAll{gene in Genome}
        \If {$tossCoin(mutation_per_gene)$}
          \State $alpha\gets random(-0.5, 0.5)$
          \State $Individual.gene\gets Individual.gene + alpha * Individual.gene$
          \State $Individual.gene\gets MAX(Individual.gene, gene.min)$
          \State $Individual.gene\gets MIN(Individual.gene, gene.max)$
        \EndIf
      \EndFor
      \EndProcedure
      \end{algorithmic}
      \end{algorithm}

    % subsubsection Mutator (end)
  % section Implementation (end)

  \section{Preliminary results} % (fold)
  \label{sec:Preliminaty Result}

    \paragraph{} % (fold)
    \label{par:}
      To much of our surprise, when we ran the optimization with an ahl concentration
      from 0.0001 to 10, the resulting function was quite bad. So bad, in fact, that
      we quickly realized that the optimized function was constant to the average of
      the gaussian values.
    % paragraph  (end)

    \paragraph{} % (fold)
    \label{par:}
      By empirecally modifying the range of ahl, we discover that given the basu's
      function definition, there was no way that with only one set of parameters we would
      obtain a good approximation on the whole definition range specified in the
      subject (i.e [0.0001,10]).
    % paragraph  (end)

    \paragraph{} % (fold)
    \label{par:}
      However we did have some pretty good results on smaller definition range,
      fortunately, for the most interesting range of [1,1.8] as demonstrated by the
      following figure.
    % paragraph  (end)

    \includegraphics[scale=0.3]{basu_best}

  % section Result (end)

   \section{Results} % (fold)
   \label{sec:Result}
   \paragraph{} % (fold)

     \label{par:}
       Here are the observed results, averaged on 30 runs:
     % paragraph  (end)

    \begin{figure}
    \begin{small}
    \begin{tabular}{lrrr}
      Parameter &  \\
      \hline
      Nb of generations & 2000 \\
      Population size & 2048  \\
      Crossover probability & 1 \\
      Mutation probability & 0.02\\
      Surviving parents & 100\%  \\
      Surviving offspring & 100\% \\
      Elitism & Strong \\
      Elite & 1 \\ \hline
      \emph{Result} & 1.17e+00 \\
      \hline
      \end{tabular}
      \caption{Parameters for basu optimisation}
    \end{small}
    \end{figure}
   % section Result (end)

   \section{Further analysis and development} % (fold)
   \label{sec:section name}
   \paragraph{} % (fold)
   \label{par:}

   % paragraph  (end)
     In the end, we felt that multiple sets of parameters, by breaking the problem
     definition range into several continuous ones, must be used in order to have
     a good approximation of the target function.

   % section section name (end)

\end{document}

ext: tex

max_stars_repo_name: pallamidessi/Courses

max_issues_repo_name: pallamidessi/Courses

max_forks_repo_name: pallamidessi/Courses


text:
\section{Dataset Statistics}\label{appendix:dataset}

% Please add the following required packages to your document preamble:
% \usepackage{booktabs}
\begin{table}[h!]
	\centering
	\begin{tabular}{@{}p{0.7\textwidth}l@{}}
		\toprule
		Statistic & Value\\ \midrule
		Total images & 18,000 \\
		Maximum image dimensions & $\left(6528 \times 5248\right)$ \\
		Minimum image dimensions & $\left(640 \times 480\right)$ \\
		Number of different dimensions & 156 \\
		Percent of images with curbs & 84.21667\% \\
		Percent of images with curb cuts & 44.79444\% \\
		Average proportion of image that are curbs & 0.81557\% \\
		Average proportion of images that contain curbs that are curbs & 0.96842\% \\
		Average proportion of image that are curb cuts & 0.08869\% \\
		Average proportion of images that contain curb cuts that are curb cuts & 0.19799\% \\
		Images with curb cuts but without curbs & 30 \\
		Usable Images (contains both curbs and curb cuts) & 15160 \\\bottomrule
	\end{tabular}
	\caption{General dataset statistics}
	\label{tab:appendix-dataset}
\end{table}


text:
\section*{Other Features of {\tt libSBOL}}
So far, we have demonstrated how one can build the CRISPR-based repression module ~\cite{kiani2014crispr} using {\tt libSBOL}. In this section, we present other major methods in the library's API.

\subsection*{Retrieving an Existing Object}
Often, we need getter methods to retrieve a previously created object. You can easily retrieve top level objects from a document by calling a templated ``get'' method using the class of the target object as the template argument. For example, if we want to get the \lstinline+cas9_generic+ protein \sbol{ComponentDefinition} object, we can use the \lstinline+get<ComponentDefinition>+ method shown below (lines 1-4) by providing the display ID of the object. By default this retrieves the latest version of an object. Alternatively, one may pass a full URI as an argument to the getter, which may be necessary when retrieving previous versions of an object.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
ComponentDefinition &cas9_generic1 = doc.get<ComponentDefinition>("cas9_generic");
\end{lstlisting}
\end{minipage}

\subsection*{Manipulating Optional Fields}
Objects may include optional fields. These are indicated in the UML specification as properties having 0 or more possible values. For example, the role property of a ComponentDefinition is optional while the molecular type field is required. Optional properties can only be set after the object is created. The following code creates a DNA component which is designated as a promoter:

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
ComponentDefinition& TargetPromoter = *new ComponentDefinition("TargetPromoter", BIOPAX_DNA, "1.0.0");
TargetPromoter.roles.set(SO_PROMOTER)
\end{lstlisting}
\end{minipage}

In addition, properties have a get method. To view the value of a property:

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
cout << TargetPromoter.roles.get() << endl;
// This returns the string "http://identifiers.org/so/SO:0000167" which is the Sequence Ontology term for a promoter.
\end{lstlisting}
\end{minipage}

Note also that some properties may contain more than one value. In the specification diagrams, an asterisk symbol next to a property indicates that the property may hold an arbitrary number of values. For example, a ComponentDefinition may be assigned multiple roles. To append a new value to the values already assigned:

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
TargetPromoter.roles.add(SO "0000568");
\end{lstlisting}
\end{minipage}

To get multiple values back from a property, it is necessary to iterate over the property:

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
// Iterate through a property to get multiple values
for (auto i_role = reaction_participant.roles.begin(); i_role != reaction_participant.roles.end(); i_role++)
{
    string role = *i_role;
    cout << role << endl;
}
\end{lstlisting}
\end{minipage}

An important thing to remember is that the set method will always overwrite the first value of a property, while the add method will always append a new value. To remove a value, one may use the remove method. Currently the remove method requires a numerical index, though this will likely change in the future.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
TargetPromoter.roles.remove(0);
\end{lstlisting}
\end{minipage}

The number of values contained by a property can be obtained by calling the size method.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
TargetPromoter.roles.size();
\end{lstlisting}
\end{minipage}

The only exceptions where these methods are not available are the following three fields in the \lstinline+Identified+ class: \lstinline+persistentIdentity+, \lstinline+displayId+, and
\lstinline+version+.  These fields cannot be edited, since they are crucial to maintaining
compliant SBOL objects (see Section~11.2 ``Compliant SBOL Objects'' of the~\href{http://sbolstandard.org/downloads/specification-data-model-2-0/}{Specification
  (Data Model 2.0)} for more details).

\subsection*{Creating and Editing References}

Some SBOL objects point to other objects by way of references. For example, ComponentDefinitions point to their corresponding Sequences. Properties of this type should be set with the URI of the related object.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
ComponentDefinition& EYFPGene = *new ComponentDefinition("EYFPGene", BIOPAX_DNA);
Sequence& seq = *new Sequence("EYFPSequence", "atgnnntaa", SBOL_ENCODING_IUPAC);
EYFPGene.sequences.set(seq.identity.get());
\end{lstlisting}
\end{minipage}

\subsection*{Creating Extension Classes}
In order to allow representation of data that can not currently be represented
by the SBOL data model or data that are outside the scope of SBOL,
SBOL offers developers the ability to embed custom data. These data are exchanged unmodified between software tools that adopt SBOL employing {\tt libSBOL} or its sister libraries such as {\tt libSBOLj}. {\tt LibSBOL} employs custom extension classes in order to embed data. Extension classes are defined like any other C++ class, as long as the user adheres to some simple patterns. The extension class approach differs slightly from the custom annotation mechanism used by {\tt libSBOLj}, but the end result is the same. The following snippet illustrates an extension class for biological parts compatible with the iGEM parts registry (\url{http://parts.igem.org}).

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
#include "sbol.h"

using namespace sbol;
using namespace std;

// These constants determine the appearance of nodes in the output file
#define EXTENSION_NS "http://igem.org#"   // Must end in a hash or forward-slash
#define EXTENSION_CLASS "iGEMCDef"        // Name of the class in XML output
#define EXTENSION_PREFIX "igem"           // Namespace prefix in XML output

class iGEMComponentDefinition : public ComponentDefinition  // Derive an extension class
{

public:
    TextProperty partStatus;
    TextProperty notes;
    TextProperty source;
    URIProperty results;

    // Define the constructor. Put required fields in the argument list. Each required field must have a default value specified, even if only an empty string.
    iGEMComponentDefinition(std::string uri = "", std::string partStatus = "Under construction") :

        // Call public base class constructor
        ComponentDefinition(uri),

        // Initialize member properties. The second argument must ALWAYS be 'this'.
        partStatus(EXTENSION_NS "partStatus", this, partStatus),  // The field is initialized to the value "Under construction"
        notes(EXTENSION_NS "notes", this),                        // The optional field is not initialized with any value
        source(PURL_URI "source", this),                        // Dublin Core namespace is already defined as part of the SBOL Core
        results(EXTENSION_NS "results", this)
    {
        // Register the extension class.
        register_extension_class < iGEMComponentDefinition >(EXTENSION_NS, EXTENSION_PREFIX, EXTENSION_CLASS);
    };

    // Destructor
    ~iGEMComponentDefinition() {};
};

\end{lstlisting}
\end{minipage}

An extension class requires an extension namespace, a class name, and a required namespace prefix (which is just a shorthand symbol for the namespace in the output file). In the example above, the extension class iGEMCDef will be defined in the namespace http://igem.org, or simply `igem'. Note that a properly formed namespace MUST end with `/' or `\#'.

In line 9 the extension class is derived from the core SBOL class ComponentDefinition. This means that new properties defined in the extension class will be serialized as annotations under the ComponentDefinition class. In addition, entirely new TopLevel extension classes can be defined, but this is covered in the next section.

Lines 13-16 define the extension properties. Each object in SBOL 2.0 can be annotated by having any number of
extension properties of type \lstinline+TextProperty+, \lstinline+URIProperty+, \lstinline+IntProperty+, or \lstinline+ReferencedObject+ objects that store data in the form of name/value property pairs. In addition, extension classes can be assembled into composite data structures using \lstinline+OwnedObject+ properties (not shown).

Line 19 defines the constructor signature. Like all SBOL classes, the first argument to an extension class should be a URI that identifies the new object. Also, as a best practice consistent with the rest of the core SBOL constructors, the remaining arguments should be required fields. All fields MUST have a default value specified such that a default constructor (see \url{http://en.cppreference.com/w/cpp/language/default_constructor}) is defined.

Lines 25-28 initialize the member properties. These also follow a simple pattern. The first argument is the URI of the property, which consists of the extension namespace followed by the property name as it appears in the serialized XML file. The second argument MUST always be \lstinline+this+. In the optional third argument, an initial value for the property is specified. In this example, only the required argument partStatus is assigned an initial value. All the other properties are left blank by default.

Finally, the extension class is registered in the data model. The class interface can now be used like any other SBOL core class, and can be written to and parsed from an SBOL file. The following code demonstrates this.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
int main()
{
    Document& doc = *new Document();
    setHomespace("http://sys-bio.org");

    iGEMComponentDefinition& cd = *new iGEMComponentDefinition("My_component", "Available");
    cd.notes.set("This component works in E. coli");
    cd.source.set("This component was isolated from B. subtilis");
    cd.results.set("http://synbiohub.org/igem/results/Works");
    doc.add < iGEMComponentDefinition > (cd);
    doc.write("igem_example.xml");
}
\end{lstlisting}
\end{minipage}

The extension class appears in the serialized RDF/XML as a ComponentDefinition with  custom annotations embedded:

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
<?xml version="1.0" encoding="utf-8"?>
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/"
   xmlns:igem="http://igem.org#"
   xmlns:prov="http://www.w3.org/ns/prov#"
   xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
   xmlns:sbol="http://sbols.org/v2#">
  <sbol:ComponentDefinition rdf:about="http://sys-bio.org/ComponentDefinition/My_component/1.0.0">
    <igem:notes>This component works in E. coli</igem:notes>
    <igem:partStatus>Available</igem:partStatus>
    <igem:results rdf:resource="http://synbiohub.org/igem/results/Works"/>
    <dcterms:source>This component was isolated from B. subtilis</dcterms:source>
    <sbol:displayId>My_component</sbol:displayId>
    <sbol:persistentIdentity rdf:resource="http://sys-bio.org/ComponentDefinition/My_component"/>
    <sbol:type rdf:resource="http://www.biopax.org/release/biopax-level3.owl#DnaRegion"/>
    <sbol:version>1.0.0</sbol:version>
  </sbol:ComponentDefinition>
</rdf:RDF>
\end{lstlisting}
\end{minipage}

\subsection*{Sharing and Distributing Extensions}
Simple extensions, such as those described above can be distributed as simple header files. Simply by including the header file with any application that links libSBOL, users can read and write extension classes and use basic accessor methods. In more advanced cases, extensions may include .cpp implementation files. In these cases, it is possible to distribute extensions as binary files. An example command line for how to compile an extension called libdummy on Mac OSX is below:

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
$ g++ -dynamiclib -std=c++11 -I/usr/local/include/sbol -I/usr/local/include/raptor2 -L/usr/local/lib -lraptor2 -lsbol dummy_extension.cpp -o libdummy.dylib
\end{lstlisting}
\end{minipage}

\subsection*{Accessing Annotations Without an Extension}
Extensions provide a means for users to quickly extend the SBOL Core data model and API. However, even if you don't have a particular extension installed, a user can still access extension data and custom annotations embedded in a file. The downside is that the user won't gain the full advantage of interfacing with the new class through an object-oriented API. Instead, the user has to access annotations using special methods in the base class. In the following example code snippet, the user interfaces with the iGEMComponentDefinition extension class by using its ComponentDefinition base class.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
doc.read("igem_example.xml");
ComponentDefinition& cd = doc.componentDefinitions["My_component"];
cout << cd.getPropertyValue(EXTENSION_NS "partStatus") << endl;
cout << cd.getPropertyValue(EXTENSION_NS "notes") << endl;
cout << cd.getPropertyValue(PURL_URI "source") << endl;
cout << cd.getPropertyValue(EXTENSION_NS "results") << endl;
\end{lstlisting}
\end{minipage}

\subsection*{Creating a TopLevel Extension Class}
Custom data can also be embedded at the top level of an SBOL document. The purpose of a top level extension class is to contain a set of annotations that are independent of any other class of SBOL object. To define a new top level class, simply derive from the TopLevel class. When deriving new classes from TopLevel class, a constant URI that defines the extension class must be specified. This URI specifies the namespace and name of the XML node for the serialized data. In this example, the Datasheet class contains two properties, a TextProperty that contains transcription data and a ReferencedObject which contains a reference to the iGEMComponentDefinition that the Datasheet describes.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
class Datasheet : public TopLevel
{
public:
    TextProperty transcription_rate;
    ReferencedObject part;

    // Define the constructor. Put required fields in the argument list. Each required field must have a default value specified, even if only an empty string.
    Datasheet(std::string uri = "") :

        // Call the TopLevel constructor. Note that the first argument to the TopLevel constructor is a constant URI that defines the class. The second argument defines URIs for new object instances
        TopLevel(EXTENSION_NS "Datashee", uri),
        transcription_rate(EXTENSION_NS "transcription_rate", this),
        part(EXTENSION_NS "part", EXTENSION_NS "iGEMCDef", this)
    {
        // Register the extension class.
        register_extension_class < Datasheet >(EXTENSION_NS, EXTENSION_PREFIX, "Datasheet");
    };

    // Destructor
    ~Datasheet() {};
};

int main()
{
    Document& doc = *new Document();
    setHomespace("http://sys-bio.org");
    Datasheet& data = *new Datasheet("test");
    data.transcription_rate.set("0.75");
    data.part.set("http://sys-bio.org/ComponentDefinition/My_component/1.0.0");
    doc.add < Datasheet > (data);
    doc.write("datasheet.xml");
}
\end{lstlisting}
\end{minipage}

\subsection*{Creating and Editing Child Objects}
Some SBOL objects can be composed into hierarchical parent-child relationships. In the specification diagrams, these relationships are indicated by black diamond arrows. For example ComponentDefinitions are parents of SequenceAnnotations.

If operating in SBOL-compliant mode, you will almost always want to use the create method rather than constructors in order to create a child object. The create method constructs and adds the SequenceAnnotation in a single function call. The create method ALWAYS takes one argument–-the displayId of the new object. Some values may be initialized with default values. Refer to documentation of specific constructors to learn which parameters are assigned default values. After object creation, these fields and optional fields may be changed.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
SequenceAnnotation& point_mutation = TargetPromoter.annotations.create("point_mutation");
\end{lstlisting}
\end{minipage}

In SBOL-compliant mode, directly adding a child to a parent object is prohibited, in order to maintain URI persistence between them. In `open-world mode' the library makes no assumptions about how URIs are formed and leaves URI generation entirely up to the user.  In this case child objects can be directly created using constructors and added to the parent. Use \lstinline+toggleSBOLCompliance()+ if you prefer to generate your own URIs and operate in open-world mode. In future developments, constructors may be opened up for use in SBOL-compliant mode as well.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
SequenceAnnotation& point_mutation = *new SequenceAnnotation("point_mutation");
TargetPromoter.annotations.add(point_mutation);
\end{lstlisting}
\end{minipage}

\subsection*{Serialization}
The library supports reading and writing data encoded in RDF/XML format.All file I/O operations are performed on the Document object. The read and write methods are used for reading and writing files in SBOL format.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
Document& doc = *new Document();
doc.read("CRISPR_example.xml");
doc.write("CRISPR_example.xml");
\end{lstlisting}
\end{minipage}

The complete repression model described in this tutorial is provided in the libSBOL source code in the examples directory. This example is self-contained in that you can run it to generate the RDF/XML output. Note that SBOL does not provide the specification of a mathematical model directly. It is possible, however, to generate a mathematical model using SBML~\cite{SBML} and the procedure described in~\cite{roehner2015generating}. Then, the SBOL document can reference this generated SBML model.

\subsection*{Copying Objects}
The library can make copies of \sbol{TopLevel} objects using the templated \lstinline+copy+ methods.  This method takes a number of optional arguments. If no arguments are specified, a copy is made and the version is incremented. An object can be copied from one Document to another by passing a pointer to the target Document as the first argument. In addition, the object can be copied to a new namespace, which is specified as the optional second argument. Finally, a custom version tag can be specified in the third argument. The following code snippet demonstrates how the copy method may be used to copy a ComponentDefinition to a new namespace and Document.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
ComponentDefinition& venus = old_doc.get<ComponentDefinition>('venus_yfp');
ComponentDefinition& venus_copy = venus.copy<ComponentDefinition>(&new_doc, "http://igem.org");
new_doc.write("copy_example.xml");
\end{lstlisting}
\end{minipage}

\subsection*{Validation}
The library also supports validation of RDF/XML file to ensure that it conforms with SBOL specification. Validation is performed on a Document object over online validator. To run it, simply run validate() on a Document object. The returned string will contain the results of validation.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
cout << doc.validate() << endl;
\end{lstlisting}
\end{minipage}

Validation is also run when a SBOL file is created through \lstinline+write()+ function. The output of validation is returned as a string when Document.write() function is executed. Keep in mind that the file will be generated regardless of whether it passes the validation step or not.

\vspace{\abovedisplayskip}
\begin{minipage}{0.95\textwidth}
\begin{lstlisting}
std:string response = doc.write(std::string("CRISPR_example.xml"));
cout << response << endl;
\end{lstlisting}
\end{minipage}

max_stars_repo_name: kirichoi/libSBOL

max_issues_repo_name: kirichoi/libSBOL

max_forks_repo_name: kirichoi/libSBOL


text:
\section{Feasibility study}

\subsection{Interests:}
A University would be interested in the application of a stored value card
system within and around the grounds because of the huge benefits it can
provide to both staff and students. The benefits of the stored-value card
system can be outlined by:

\items High level of security: resulting from advanced levels of user or
terminal authentication, standardised use of PIN and passwords to eliminate
chances of misuse. Our system provides you with a complete audit trail for all
card holder and merchant accounts. It also gives you the ability to track
purchasing habits to better understand your clientele and target your marketing
efforts on the most profitable customers.

\subitems Reduces the risk of theft.

\items Convenience: quicker transactions, no need for notes or coins.

\subitems Students like the convenience of using the card without having to
worry about needing cash on hand.

\subitems The cards can also double as student ID cards, eliminating the need
for students to carry and keep track of multiple cards.

\subitems Storage of personal data, e.g. medical records.

\items Cost effectiveness: easy to maintain and assess.

\subitems Students like the fact that a lost or stolen card can be cancelled.
Any unspent value on the card can be transferred over to the replacement card.
Your organisation sets the card replacement policy.

\subitems Minimise new student processing time.

\items Multi functional: can be used for a wide variety of functions.

\subitems Parents like the peace of mind of knowing that funds placed on a
stored-value card cannot be spent for things that it was not intended for. The
stored-value cards can only be used at merchants that are a part of the
program. Therefore, your organisation controls the scope of the program.
Agreements with participating merchants can also specify items that the card
cannot be used to purchase.

\subitems The program can be limited to on-campus locations or expanded to
include independent, off-campus merchants.

\subitems We can work with you to create multiple "card products" so that you
can separate your clientele into groups such as faculty, staff, students,
tutors, etc $\ldots$

\subsection{Applications:}

Applications for the stored value card throughout and around the university
grounds would include such things as:

\items Alternative to, or replacement for cash: termed electronic purses. The
cards could be linked to the individuals account to the university. The account
would be either a debit or credit to an applied limit. Purchases could be
automatically deducted form that person's account at the place of purchase at
real time and an accurate account of all purchases via a statement produced
monthly or quarterly. The cards could also be linked to other shops in and
around the campus such as local businesses.

\subitems Student and Staff security passes to buildings and computers. For
rooms with expensive equipment such as computer rooms and media labs this would
be effective in reducing theft especially during later hours. This application
would also be used to restrict access to unauthorised students. For example not
allowing students into staff areas. Restricting access to computers in cases
where the student is not part of the faculty or school.

\subitems Library card. Stored value cards would replace the current library
card, allowing students to access the library, place books on hold, reserve
books, loan books, access and use the photocopying machines and printers. All
with the one card.

\subitems Roll call. Cards could also be used to tract student attendance to
both lectures and tutorials. Lecturers could easily track attendance and
amount of time spent in lecturers to help fairly award participation marks and
help in determining scores in borderline mark cases.

\subitems Paying for car parking. The card could allow access and track
parking and allow the user to only pay for the parking that is used at a fair
rate.

\subitems Loyalty and shopper discount program cards, the card would be able to
track university usage at shops and develop loyalty programs for services that
are used by students.

\subitems Storage of personal data, e.g. medical records, this could be used in
emergencies and could greatly help authorities in cases where the information
provided could save someone's life.

\subitems Storage of an individual's personal and biometric information such as
facial geometry, finger/thumb prints, voice patterns, identifying
characteristics, electronic signatures, written signature, and so on;

\subitems Storage of a person's user interface preferences e.g. speech or
large print display on an Automatic Teller Machine.

max_stars_repo_name: felx/detritus

max_issues_repo_name: felx/detritus

max_forks_repo_name: felx/detritus