Mercurial > hgrepos > Python > libs > pygments-lexer-pseudocode2

annotate docs/examples/algorithm-edmonds-karp.pseudocode @ 160:b4028838e0c8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Implement lexer option "prohibit_raiseonerror_filter". Sphinx raises by default when an Error token is seen (by means of the "raiseonerror" filter that is applied by default to lexers in Sphinx). This option skips this and allows error locations to be seen and highlighted properly. While there convert most Generic.Error tokens to Error tokens because now they can be handled by a lexer with "prohibit_raiseonerror_filter=True".
author Franz Glasner <fzglas.hg@dom66.de>
date Fri, 08 May 2026 17:46:28 +0200
parents 4a8c122725b0
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
107
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
1 // -*- coding: utf-8; indent-tabs-mode: nil -*-
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
2 \ALGORITHM{Edmonds–Karp} \WITH
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
3 \INPUT{
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
4 \expr{graph}: \expr{graph[v]} should be the list of edges coming out of vertex \expr{v} in the
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
5 original graph and their corresponding constructed reverse edges
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
6 which are used for push-back flow.
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
7 Each edge should have a capacity \expr{cap}, \expr{flow}, source \expr{s} and sink \expr{t}
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
8 as parameters, as well as a pointer to the reverse edge \expr{rev}.
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
9 \expr{s}: Source vertex
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
10 \expr{t}: Sink vertex}
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
11 \OUTPUT{
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
12 \expr{flow}: Value of maximum flow)}
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
13 \IS
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
14 flow := 0
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
15 \REPEAT
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
16 /* Run a breadth-first search (bfs) to find the shortest s-t path.
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
17 We use 'pred' to store the edge taken to get to each vertex,
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
18 so we can recover the path afterwards. */
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
19 q := queue()
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
20 q.push(s)
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
21 pred := array(graph.length)
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
22 \WHILE not empty(q) and pred[t] = null \DO
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
23 cur := q.pop()
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
24 \FOR \text{Edge} e in graph[cur] \DO
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
25 \IF pred[e.t] = null and e.t != s and e.cap > e.flow \THEN
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
26 pred[e.t] := e
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
27 q.push(e.t)
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
28 \END IF
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
29 \END FOR
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
30 \END WHILE
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
31 \IF not (pred[t] = null) \THEN
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
32 /* We found an augmenting path.
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
33 See how much flow we can send */
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
34 df := ∞
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
35 \FOR (e := pred[t]; e != null; e := pred[e.s]) \DO
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
36 df := min(df, e.cap - e.flow)
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
37 \END FOR
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
38 /* And update edges by that amount */
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
39 \FOR (e := pred[t]; e != null; e := pred[e.s]) \DO
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
40 e.flow := e.flow + df
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
41 e.rev.flow := e.rev.flow - df
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
42 \END FOR
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
43 flow := flow + df
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
44 \END IF
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
45 \UNTIL pred[t] = null \REM i.e., until no augmenting path was found
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
46 \RETURN flow
1c1985532139 A couple of real pseudocode examples.
Franz Glasner <fzglas.hg@dom66.de>
parents:
diff changeset
47 \END ALGORITHM {Edmonds–Karp}