Merge pull request #782 from whitequark/flowmap_dfs

 flowmap: construct a max-volume max-flow min-cut, not just any one

2 files changed, 38 insertions, 0 deletions

diff --git a/passes/tests/flowmap/flow.v b/passes/tests/flowmap/flow.v
new file mode 100644
index 000000000..297ef910e
--- /dev/null
+++ b/passes/tests/flowmap/flow.v
@@ -0,0 +1,22 @@
+// Exact reproduction of Figure 2(a) from 10.1109/43.273754.
+module top(...);
+	input a,b,c,d,e,f;
+	wire nA = b&c;
+	wire A = !nA;
+	wire nB = c|d;
+	wire B = !nB;
+	wire nC = e&f;
+	wire C = !nC;
+	wire D = A|B;
+	wire E = a&D;
+	wire nF = D&C;
+	wire F = !nF;
+	wire nG = F|B;
+	wire G = !nG;
+	wire H = a&F;
+	wire I = E|G;
+	wire J = G&C;
+	wire np = H&I;
+	output p = !np;
+	output q = A|J;
+endmodule
diff --git a/passes/tests/flowmap/flowp.v b/passes/tests/flowmap/flowp.v
new file mode 100644
index 000000000..2fb40ffa4
--- /dev/null
+++ b/passes/tests/flowmap/flowp.v
@@ -0,0 +1,16 @@
+// Like flow.v, but results in a network identical to Figure 2(b).
+module top(...);
+	input a,b,c,d,e,f;
+	wire A = b&c;
+	wire B = c|d;
+	wire C = e&f;
+	wire D = A|B;
+	wire E = a&D;
+	wire F = D&C;
+	wire G = F|B;
+	wire H = a&F;
+	wire I = E|G;
+	wire J = G&C;
+	output p = H&I;
+	output q = A|J;
+endmodule