summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/algorithm2e/doc/algorithm2e_exIR.tex
diff options
context:
space:
mode:
Diffstat (limited to 'macros/latex/contrib/algorithm2e/doc/algorithm2e_exIR.tex')
-rw-r--r--macros/latex/contrib/algorithm2e/doc/algorithm2e_exIR.tex40
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}