diff options
Diffstat (limited to 'macros/latex/contrib/algorithm2e/doc/algorithm2e_exIR.tex')
-rw-r--r-- | macros/latex/contrib/algorithm2e/doc/algorithm2e_exIR.tex | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/macros/latex/contrib/algorithm2e/doc/algorithm2e_exIR.tex b/macros/latex/contrib/algorithm2e/doc/algorithm2e_exIR.tex new file mode 100644 index 0000000000..1415f65e91 --- /dev/null +++ b/macros/latex/contrib/algorithm2e/doc/algorithm2e_exIR.tex @@ -0,0 +1,40 @@ +\begin{algorithm} +\DontPrintSemicolon +\KwData{$G=(X,U)$ such that $G^{tc}$ is an order.} +\KwResult{$G'=(X,V)$ with $V\subseteq U$ such that $G'^{tc}$ is an +interval order.} +\Begin{ + $V \longleftarrow U$\; + $S \longleftarrow \emptyset$\; + \For{$x\in X$}{ + $NbSuccInS(x) \longleftarrow 0$\; + $NbPredInMin(x) \longleftarrow 0$\; + $NbPredNotInMin(x) \longleftarrow |ImPred(x)|$\; + } + \For{$x \in X$}{ + \If{$NbPredInMin(x) = 0$ {\bf and} $NbPredNotInMin(x) = 0$}{ + $AppendToMin(x)$} + } + \nl\While{$S \neq \emptyset$}{\label{InRes1} + \nlset{REM} remove $x$ from the list of $T$ of maximal index\;\label{InResR} + \lnl{InRes2}\While{$|S \cap ImSucc(x)| \neq |S|$}{ + \For{$ y \in S-ImSucc(x)$}{ + \{ remove from $V$ all the arcs $zy$ : \}\; + \For{$z \in ImPred(y) \cap Min$}{ + remove the arc $zy$ from $V$\; + $NbSuccInS(z) \longleftarrow NbSuccInS(z) - 1$\; + move $z$ in $T$ to the list preceding its present list\; + \{i.e. If $z \in T[k]$, move $z$ from $T[k]$ to + $T[k-1]$\}\; + } + $NbPredInMin(y) \longleftarrow 0$\; + $NbPredNotInMin(y) \longleftarrow 0$\; + $S \longleftarrow S - \{y\}$\; + $AppendToMin(y)$\; + } + } + $RemoveFromMin(x)$\; + } + } +\caption{IntervalRestriction\label{IR}} +\end{algorithm} |