#include <iostream>
#include <lemon/list_graph.h>
#include <lemon/suurballe.h>

using namespace std;
using namespace lemon;

int main() {
  DIGRAPH_TYPEDEFS(ListDigraph);
  ListDigraph g;

  Node n0 = g.addNode();
  Node n1 = g.addNode();
  Node n2 = g.addNode();
  Node n3 = g.addNode();
  Node n4 = g.addNode();

  Arc a0 = g.addArc(n0, n1);
  Arc a1 = g.addArc(n0, n2);
  Arc a2 = g.addArc(n1, n3);
  Arc a3 = g.addArc(n1, n4);
  Arc a4 = g.addArc(n2, n1);
  Arc a5 = g.addArc(n2, n3);
  Arc a6 = g.addArc(n2, n4);
  Arc a7 = g.addArc(n3, n4);

  typedef ListDigraph::ArcMap<int> LengthMap;
  LengthMap length(g);
  length[a0] = 1;
  length[a1] = 1;
  length[a2] = 1;
  length[a3] = 5;
  length[a4] = 2;
  length[a5] = 1;
  length[a6] = 10;
  length[a7] = 3;

  Suurballe<ListDigraph, LengthMap> srb(g, length);
  srb.run(n0, n4, 2);

  for (int i = 0; i != srb.pathNum(); ++i) {
    cout << "Path " << i+1 << ": ";
    for (int j = 0; j != srb.path(i).length(); ++j) {
      cout << g.id(g.source(srb.path(i).nth(j))) << "->"
           << g.id(g.target(srb.path(i).nth(j))) << " ";
    }
    cout << endl;
  }

  return 0;
}