Add the LEMON graph library source to the repo

I'll likely be using it, so this just makes it easier to get to from
elsewhere. If I end up not using it then I can just delete it.

1 files changed, 141 insertions, 0 deletions

diff --git a/lemon/test/gomory_hu_test.cc b/lemon/test/gomory_hu_test.cc
new file mode 100644
index 0000000..c35f2e3
--- /dev/null
+++ b/lemon/test/gomory_hu_test.cc
@@ -0,0 +1,141 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#include <iostream>
+
+#include "test_tools.h"
+#include <lemon/smart_graph.h>
+#include <lemon/concepts/graph.h>
+#include <lemon/concepts/maps.h>
+#include <lemon/lgf_reader.h>
+#include <lemon/gomory_hu.h>
+#include <cstdlib>
+
+using namespace std;
+using namespace lemon;
+
+typedef SmartGraph Graph;
+
+char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "@arcs\n"
+  "     label capacity\n"
+  "0 1  0     1\n"
+  "1 2  1     1\n"
+  "2 3  2     1\n"
+  "0 3  4     5\n"
+  "0 3  5     10\n"
+  "0 3  6     7\n"
+  "4 2  7     1\n"
+  "@attributes\n"
+  "source 0\n"
+  "target 3\n";
+
+void checkGomoryHuCompile()
+{
+  typedef int Value;
+  typedef concepts::Graph Graph;
+
+  typedef Graph::Node Node;
+  typedef Graph::Edge Edge;
+  typedef concepts::ReadMap<Edge, Value> CapMap;
+  typedef concepts::ReadWriteMap<Node, bool> CutMap;
+
+  Graph g;
+  Node n;
+  CapMap cap;
+  CutMap cut;
+  Value v;
+  int d;
+
+  GomoryHu<Graph, CapMap> gh_test(g, cap);
+  const GomoryHu<Graph, CapMap>&
+    const_gh_test = gh_test;
+
+  gh_test.run();
+
+  n = const_gh_test.predNode(n);
+  v = const_gh_test.predValue(n);
+  d = const_gh_test.rootDist(n);
+  v = const_gh_test.minCutValue(n, n);
+  v = const_gh_test.minCutMap(n, n, cut);
+}
+
+GRAPH_TYPEDEFS(Graph);
+typedef Graph::EdgeMap<int> IntEdgeMap;
+typedef Graph::NodeMap<bool> BoolNodeMap;
+
+int cutValue(const Graph& graph, const BoolNodeMap& cut,
+             const IntEdgeMap& capacity) {
+
+  int sum = 0;
+  for (EdgeIt e(graph); e != INVALID; ++e) {
+    Node s = graph.u(e);
+    Node t = graph.v(e);
+
+    if (cut[s] != cut[t]) {
+      sum += capacity[e];
+    }
+  }
+  return sum;
+}
+
+
+int main() {
+  Graph graph;
+  IntEdgeMap capacity(graph);
+
+  std::istringstream input(test_lgf);
+  GraphReader<Graph>(graph, input).
+    edgeMap("capacity", capacity).run();
+
+  GomoryHu<Graph> ght(graph, capacity);
+  ght.run();
+
+  for (NodeIt u(graph); u != INVALID; ++u) {
+    for (NodeIt v(graph); v != u; ++v) {
+      Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
+      pf.runMinCut();
+      BoolNodeMap cm(graph);
+      ght.minCutMap(u, v, cm);
+      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
+      check(cm[u] != cm[v], "Wrong cut 2");
+      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
+
+      int sum=0;
+      for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
+        sum+=capacity[a];
+      check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
+
+      sum=0;
+      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n)
+        sum++;
+      for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n)
+        sum++;
+      check(sum == countNodes(graph), "Problem with MinCutNodeIt");
+    }
+  }
+
+  return 0;
+}