changeset 107:1c1985532139

A couple of real pseudocode examples. Examples are from the Wikipedia.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 04 May 2026 16:57:17 +0200
parents f6b46a379aba
children 6cebd3e7bc97
files docs/algorithm-dinic.description docs/algorithm-edmonds-karp.pseudocode docs/algorithm-ford-fulkerson.pseudocode docs/example-1.pseudocode docs/index.rst
diffstat 5 files changed, 190 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/algorithm-dinic.description	Mon May 04 16:57:17 2026 +0200
@@ -0,0 +1,11 @@
+// -*- coding: utf-8; indent-tabs-mode: nil -*-
+\ALGORITHM{Dinic's Algorithm} \WITH
+  \INPUT{A network \expr{G = ((V , E), c, s, t)}.}
+  \OUTPUT{An \expr{s–t} flow \expr{f} of maximum value.}
+\IS
+  \TEXT{1. Set \expr{f(e) = 0} for each \expr{e ∈ E}.
+  2. Construct \expr{G_L} from \expr{G_f} of \expr{G}.
+     If \expr{\text{dist}(t) = ∞}, stop and output \expr{f}.
+  3. Find a blocking flow \expr{f\'} in \expr{G_L}.
+  4. Augment flow \expr{f} by \expr{f\'} and go back to step 2.}
+\END ALGORITHM
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/algorithm-edmonds-karp.pseudocode	Mon May 04 16:57:17 2026 +0200
@@ -0,0 +1,47 @@
+// -*- coding: utf-8; indent-tabs-mode: nil -*-
+\ALGORITHM{Edmonds–Karp} \WITH
+    \INPUT{
+      \expr{graph}:  \expr{graph[v]} should be the list of edges coming out of vertex \expr{v} in the
+              original graph and their corresponding constructed reverse edges
+              which are used for push-back flow.
+              Each edge should have a capacity \expr{cap}, \expr{flow}, source \expr{s} and sink \expr{t} 
+              as parameters, as well as a pointer to the reverse edge \expr{rev}.
+      \expr{s}:      Source vertex
+      \expr{t}:      Sink vertex}
+    \OUTPUT{
+      \expr{flow}:  Value of maximum flow)}
+\IS
+    flow := 0
+    \REPEAT
+        /* Run a breadth-first search (bfs) to find the shortest s-t path.
+           We use 'pred' to store the edge taken to get to each vertex,
+           so we can recover the path afterwards. */
+        q := queue()
+        q.push(s)
+        pred := array(graph.length)
+        \WHILE not empty(q) and pred[t] = null \DO
+            cur := q.pop()
+            \FOR \text{Edge} e in graph[cur] \DO
+                \IF pred[e.t] = null and e.t != s and e.cap > e.flow \THEN
+                    pred[e.t] := e
+                    q.push(e.t)
+                \END IF
+            \END FOR
+        \END WHILE
+        \IF not (pred[t] = null) \THEN
+            /* We found an augmenting path.
+               See how much flow we can send */
+            df := ∞
+            \FOR (e := pred[t]; e != null; e := pred[e.s]) \DO
+                df := min(df, e.cap - e.flow)
+            \END FOR
+            /* And update edges by that amount */
+            \FOR (e := pred[t]; e != null; e := pred[e.s]) \DO
+                e.flow  := e.flow + df
+                e.rev.flow := e.rev.flow - df
+            \END FOR
+            flow := flow + df
+        \END IF
+    \UNTIL pred[t] = null      \REM i.e., until no augmenting path was found
+    \RETURN flow
+\END ALGORITHM {Edmonds–Karp}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/algorithm-ford-fulkerson.pseudocode	Mon May 04 16:57:17 2026 +0200
@@ -0,0 +1,19 @@
+// -*- coding: utf-8; indent-tabs-mode: nil -*-
+\ALGORITHM{Ford–Fulkerson} \WITH
+  \INPUTS{Given a network \expr{G = (V, E)} with flow capacity \expr{c}, a source node \expr{s}, and a sink node \expr{t}}
+  \OUTPUT{Compute a flow \expr{f} from \expr{s} to \expr{t} of maximum value}
+\IS
+  \TEXT{1. \expr{f(u, v) <- 0} for all edges \expr{(u, v)}
+
+  2. While there is a path \expr{p} from \expr{s} to \expr{t} in \expr{G_f},
+     such that \expr{c_f(u, v) > 0} for all edges \expr{(u, v) ∈ p}:
+
+     1. Find \expr{c_f(p) = min{c_f(u, v): (u, v) ∈ p\}}
+
+     2. For each edge \expr{(u, v) ∈ p}
+
+        1. \expr{f(u, v) <- f(u, v) + c_f(p)}   \expr{\rem Send flow along the path
+
+}	2. \expr{f(v, u) <- f(v, u) - c_f(p)}   \expr{\rem The flow might be "returned" later
+}}
+\END ALGORITHM {Ford–Fulkerson}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/example-1.pseudocode	Mon May 04 16:57:17 2026 +0200
@@ -0,0 +1,47 @@
+// -*- coding: utf-8; indent-tabs-mode: nil -*-
+\PROGRAM {The Pseudocode Lexer} \IS
+
+  /*
+   * The program is here, but it also could be an \ALGORITHM
+   *
+   * /* YES! Nested multiline comments work! */
+   */
+
+  \PROC {A Procedure name} \IS
+    \TBLOCK {A text block 1}
+    \TBLOCK {A text block 2 with an expression: \expr{flag is FALSE}}
+    \BLOCK {
+        \REMARK  A remark on its own line within a "BLOCK"
+    }
+  \END-PROC {A Procedure name}
+
+  \FUNCTION{A Function with {escaped\} text} \IS
+    a and b xor (c in d)      \rem this is another remark
+    \block {foo bar}
+
+    \IF a is nil \THEN
+      \text{Set something}
+    \ELSEIF
+      \text{Set some other thing}
+    \END-IF
+  \END FUNCTION{A Function with {escaped\} text}
+
+  \CLASS{A Class} \IS
+    // This is a one-line comment
+    a and b xor (c in d)      \rem this is another remark
+
+    # This is another one-line comment
+    \block {foo
+      bar}
+    \block{a 1.2 {x in X\} c}
+    \tstate{We will compute next \expr{a xor b or (\text{set} X is Empty)} \rem without c!
+      or multiply it the other way round}
+
+    \tstate{foo bar     \rem A remark within a text statement until LF!
+      nextfoo nextbar
+      nextnextfoo nextnextbar}
+  \ENDCLASS{A Class}
+
+  @A_XXX
+  FOO BAR
+\ENDPROG
--- a/docs/index.rst	Mon May 04 16:40:13 2026 +0200
+++ b/docs/index.rst	Mon May 04 16:57:17 2026 +0200
@@ -8,8 +8,73 @@
    :maxdepth: 2
    :caption: Contents:
 
-   details	     
+   details
+
+
+Expressions:
+
+- Strings (single-quote, double-quote, triple-single-quote, triple-double-quote)
+- Numbers (Python style)
+- ``\TEXT{...}``
+
+  The curly brace can be quoted with ``\}`` to not end the text mode
+
+- Names (`Name.Entity`)
+
+.. literalinclude:: example-1.pseudocode
+   :language: AlgPseudocode
+   :lines: 2-
+
+With a customized `AlgPseudocodeLexer` and its `no_end`
+option set to ``True``.
+
+.. literalinclude:: example-1.pseudocode
+   :language: NoEndAlgPseudocode
+   :lines: 2-
+
+Python:
+
+.. code-block:: python
+
+   class HUHU:
 
+     # This is a comment
+     @classmethod
+     def method1(cls_, aparam1, param2):
+       return aparam1 + param2
+
+
+This is Wikipedia's description of *Dinic's Algorithm*
+(see https://en.wikipedia.org/wiki/Dinic%27s_algorithm):
+
+.. literalinclude:: algorithm-dinic.description
+   :language: AlgPseudocode
+   :lines: 2-
+
+This is Wikipedia's pseudocode of the *Ford–Fulkerson Algorithm*
+(see https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm):
+
+.. literalinclude:: algorithm-ford-fulkerson.pseudocode
+   :language: AlgPseudocode
+   :lines: 2-
+
+This is Wikipedia's pseudocode of the *Edmonds–Karp Algorithm*
+(see https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm):
+
+.. literalinclude:: algorithm-edmonds-karp.pseudocode
+   :language: NoEndAlgPseudocode
+   :lines: 2-	   
+
+.. todo::
+
+   Note how
+   https://stackoverflow.com/questions/11413203/sphinx-pygments-lexer-filter-extension
+   documents dynamic lexer and style creation for Pygments within Sphinx.
+
+   Examples:
+
+   - Load lexers with some custom (init) options
+   - Dynamically create new lexers, styles, formatters or filters
 
 .. todolist::