%%
%% $Id$
%%
%% Copyright 1989-2016 MINES ParisTech
%%
%% This file is part of PIPS.
%%
%% PIPS is free software: you can redistribute it and/or modify it
%% under the terms of the GNU General Public License as published by
%% the Free Software Foundation, either version 3 of the License, or
%% any later version.
%%
%% PIPS is distributed in the hope that it will be useful, but WITHOUT ANY
%% WARRANTY; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE.
%%
%% See the GNU General Public License for more details.
%%
%% You should have received a copy of the GNU General Public License
%% along with PIPS.  If not, see <http://www.gnu.org/licenses/>.
%%
\documentclass[a4paper]{article}
\usepackage{newgen_domain}
\usepackage[backref,pagebackref]{hyperref}

\title{PIPS: Interval Graph}
\author{Ronan KERYELL\\
\\
    CRI, Ecole des Mines de Paris}

\begin{document}

\maketitle

\sloppy

The interval graph is used at least in the hierarchical restructurer
of the control graph in PIPS. This file defines the data structures
used by the algorithm to build and represent the interval graphs
embedding control flow graph.


\section{Imported NewGen Types}

Since the interval graph is on the control graph, import the following
type:\\
\domain{Import control from "ri.newgen"}
{}

\section{The Interval Graph}

An interval graph is represented by a graph (from package ``graph''
with \verb|interval_vertex_label| decorations. The first interval of the
graph is the entry interval of the interval graph and the first
control node of an interval is the entry control node of the interval.

\subsection{Vertex Label of the Interval Graph}


Each interval node of the graph contains a list of corresponding nodes
in the control graph.

\domain{interval\_vertex\_label = controls:control*}
{}

\end{document}
