54 lines
1.4 KiB
Clojure
54 lines
1.4 KiB
Clojure
(ns loom.test.flow
|
|
(:require [loom.graph :refer (weighted-digraph successors predecessors weight)]
|
|
[loom.flow :refer (edmonds-karp is-admissible-flow?)]
|
|
[loom.alg :refer [max-flow]]
|
|
#?@(:clj [[clojure.test :refer :all]]
|
|
:cljs [cljs.test]))
|
|
#?@(:cljs [(:require-macros [cljs.test :refer (deftest testing are is)])]))
|
|
|
|
|
|
;; Trivial case
|
|
(def g0
|
|
(weighted-digraph
|
|
[:s :t 100]))
|
|
|
|
;; From Cormen et al. Algorithms, 3 ed. p. 726-727
|
|
(def g1
|
|
(weighted-digraph
|
|
[:s :v1 16]
|
|
[:s :v2 13]
|
|
[:v1 :v3 12]
|
|
[:v2 :v1 4]
|
|
[:v2 :v4 14]
|
|
[:v3 :v2 9]
|
|
[:v3 :t 20]
|
|
[:v4 :v3 7]
|
|
[:v4 :t 4]))
|
|
|
|
;; Source and sink disconnected
|
|
(def g2
|
|
(weighted-digraph
|
|
[:s :a 5]
|
|
[:b :t 10]))
|
|
|
|
|
|
(deftest edmonds-karp-test
|
|
(are [max-value network]
|
|
(let [[flow value] (edmonds-karp (successors network)
|
|
(predecessors network)
|
|
(weight network)
|
|
:s :t)]
|
|
(and (= max-value value)
|
|
(is-admissible-flow? flow (weight network)
|
|
:s :t)))
|
|
23 g1
|
|
100 g0
|
|
0 g2))
|
|
|
|
|
|
(deftest max-flow-convenience-test
|
|
(are [max-value network]
|
|
(let [[flow value] (max-flow (weighted-digraph network) :s :t)]
|
|
(and (= max-value value)
|
|
(is-admissible-flow? flow (weight network) :s :t)))
|
|
23 g1))
|