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

annotate docs/examples/algorithm-edmonds-karp.pseudocode @ 216:8ef73270beae

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Make my-doc-style.sty more flexible by providing the "stdtitle" option to switch off the customized titlepage content
author Franz Glasner <fzglas.hg@dom66.de>
date Fri, 15 May 2026 14:34:11 +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}