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

comparison docs/algorithm-edmonds-karp.pseudocode @ 107:1c1985532139

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
children
comparison
equal deleted inserted replaced
106:f6b46a379aba 107:1c1985532139
1 // -*- coding: utf-8; indent-tabs-mode: nil -*-
2 \ALGORITHM{Edmonds–Karp} \WITH
3 \INPUT{
4 \expr{graph}: \expr{graph[v]} should be the list of edges coming out of vertex \expr{v} in the
5 original graph and their corresponding constructed reverse edges
6 which are used for push-back flow.
7 Each edge should have a capacity \expr{cap}, \expr{flow}, source \expr{s} and sink \expr{t}
8 as parameters, as well as a pointer to the reverse edge \expr{rev}.
9 \expr{s}: Source vertex
10 \expr{t}: Sink vertex}
11 \OUTPUT{
12 \expr{flow}: Value of maximum flow)}
13 \IS
14 flow := 0
15 \REPEAT
16 /* Run a breadth-first search (bfs) to find the shortest s-t path.
17 We use 'pred' to store the edge taken to get to each vertex,
18 so we can recover the path afterwards. */
19 q := queue()
20 q.push(s)
21 pred := array(graph.length)
22 \WHILE not empty(q) and pred[t] = null \DO
23 cur := q.pop()
24 \FOR \text{Edge} e in graph[cur] \DO
25 \IF pred[e.t] = null and e.t != s and e.cap > e.flow \THEN
26 pred[e.t] := e
27 q.push(e.t)
28 \END IF
29 \END FOR
30 \END WHILE
31 \IF not (pred[t] = null) \THEN
32 /* We found an augmenting path.
33 See how much flow we can send */
34 df := ∞
35 \FOR (e := pred[t]; e != null; e := pred[e.s]) \DO
36 df := min(df, e.cap - e.flow)
37 \END FOR
38 /* And update edges by that amount */
39 \FOR (e := pred[t]; e != null; e := pred[e.s]) \DO
40 e.flow := e.flow + df
41 e.rev.flow := e.rev.flow - df
42 \END FOR
43 flow := flow + df
44 \END IF
45 \UNTIL pred[t] = null \REM i.e., until no augmenting path was found
46 \RETURN flow
47 \END ALGORITHM {Edmonds–Karp}