RhodeCode

 * 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 <lemon/concepts/digraph.h>

#include <lemon/smart_graph.h>

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/bfs.h>

#include <lemon/path.h>

#include "graph_test.h"

#include "test_tools.h"

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "5\n"

  "@arcs\n"

  "     label\n"

  "0 1  0\n"

  "1 2  1\n"

  "2 3  2\n"

  "3 4  3\n"

  "0 3  4\n"

  "0 3  5\n"

  "5 2  6\n"

  "@attributes\n"

  "source 0\n"

  "target 4\n";

void checkBfsCompile()

{

  typedef concepts::Digraph Digraph;

  typedef Bfs<Digraph> BType;

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  Digraph G;

  Arc e;

  bool b;

  BType::DistMap d(G);

  BType::PredMap p(G);

  Path<Digraph> pp;

  {

    BType bfs_test(G);

    bfs_test.run(s);

    bfs_test.run(s,t);

    bfs_test.run();

  }

  {

    BType

      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >

      ::SetDistMap<concepts::ReadWriteMap<Node,int> >

      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >

      ::SetProcessedMap<concepts::WriteMap<Node,bool> >

      ::Create bfs_test(G);

    bfs_test.run(s);

    bfs_test.run(s,t);

    bfs_test.run();

    l  = bfs_test.dist(t);

    e  = bfs_test.predArc(t);

    s  = bfs_test.predNode(t);

    b  = bfs_test.reached(t);

    pp = bfs_test.path(t);

  }

}

void checkBfsFunctionCompile()

{

  typedef int VType;

  typedef concepts::Digraph Digraph;

  typedef Digraph::Arc Arc;

  typedef Digraph::Node Node;

  Digraph g;

  bool b;

  bfs(g).run(Node());

  b=bfs(g).run(Node(),Node());

  bfs(g).run();

  bfs(g)

    .predMap(concepts::ReadWriteMap<Node,Arc>())

    .distMap(concepts::ReadWriteMap<Node,VType>())

    .reachedMap(concepts::ReadWriteMap<Node,bool>())

    .processedMap(concepts::WriteMap<Node,bool>())

    .run(Node());

  b=bfs(g)

    .predMap(concepts::ReadWriteMap<Node,Arc>())

    .distMap(concepts::ReadWriteMap<Node,VType>())

    .reachedMap(concepts::ReadWriteMap<Node,bool>())

    .processedMap(concepts::WriteMap<Node,bool>())

    .path(concepts::Path<Digraph>())

    .dist(VType())

    .run(Node(),Node());

  bfs(g)

    .predMap(concepts::ReadWriteMap<Node,Arc>())

    .distMap(concepts::ReadWriteMap<Node,VType>())

    .reachedMap(concepts::ReadWriteMap<Node,bool>())

    .processedMap(concepts::WriteMap<Node,bool>())

    .run();

}

template <class Digraph>

void checkBfs() {

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  Digraph G;

#include <lemon/concepts/maps.h>

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "5\n"

  "@arcs\n"

  "     lcap  ucap\n"

  "0 1  2  10\n"

  "0 2  2  6\n"

  "1 3  4  7\n"

  "1 4  0  5\n"

  "2 4  1  3\n"

  "3 5  3  8\n"

  "4 5  3  7\n"

  "@attributes\n"

  "source 0\n"

  "sink   5\n";

void checkCirculationCompile()

{

  typedef int VType;

  typedef concepts::Digraph Digraph;

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  typedef concepts::ReadMap<Arc,VType> CapMap;

  typedef concepts::ReadMap<Node,VType> DeltaMap;

  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;

  typedef concepts::WriteMap<Node,bool> BarrierMap;

  typedef Elevator<Digraph, Digraph::Node> Elev;

  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;

  Digraph g;

  Node n;

  Arc a;

  CapMap lcap, ucap;

  DeltaMap delta;

  FlowMap flow;

  BarrierMap bar;

  circ_test.init();

  circ_test.greedyInit();

  circ_test.start();

  circ_test.run();

}

template <class G, class LM, class UM, class DM>

void checkCirculation(const G& g, const LM& lm, const UM& um,

                      const DM& dm, bool find)

{

  Circulation<G, LM, UM, DM> circ(g, lm, um, dm);

  bool ret = circ.run();

  if (find) {

    check(ret, "A feasible solution should have been found.");

    check(circ.checkFlow(), "The found flow is corrupt.");

    check(!circ.checkBarrier(), "A barrier should not have been found.");

  } else {

    check(!ret, "A feasible solution should not have been found.");

    check(circ.checkBarrier(), "The found barrier is corrupt.");

  }

}

int main (int, char*[])

{

  typedef ListDigraph Digraph;

  DIGRAPH_TYPEDEFS(Digraph);

  Digraph g;

  IntArcMap lo(g), up(g);

  IntNodeMap delta(g, 0);

  Node s, t;

  std::istringstream input(test_lgf);

  DigraphReader<Digraph>(g,input).

    arcMap("lcap", lo).

    arcMap("ucap", up).

    node("source",s).

    node("sink",t).

    run();

  delta[s] = 7; delta[t] = -7;

  checkCirculation(g, lo, up, delta, true);

  delta[s] = 13; delta[t] = -13;

  checkCirculation(g, lo, up, delta, true);

  delta[s] = 6; delta[t] = -6;

  checkCirculation(g, lo, up, delta, false);

  delta[s] = 14; delta[t] = -14;

  checkCirculation(g, lo, up, delta, false);

 */

#include <lemon/concepts/digraph.h>

#include <lemon/smart_graph.h>

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/dfs.h>

#include <lemon/path.h>

#include "graph_test.h"

#include "test_tools.h"

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "5\n"

  "6\n"

  "@arcs\n"

  "     label\n"

  "0 1  0\n"

  "1 2  1\n"

  "2 3  2\n"

  "1 4  3\n"

  "4 2  4\n"

  "4 5  5\n"

  "5 0  6\n"

  "6 3  7\n"

  "@attributes\n"

  "source 0\n"

  "target 5\n";

void checkDfsCompile()

{

  typedef concepts::Digraph Digraph;

  typedef Dfs<Digraph> DType;

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  Digraph G;

  Node s, t;

  Arc e;

  bool b;

  DType::DistMap d(G);

  DType::PredMap p(G);

  Path<Digraph> pp;

  {

    DType dfs_test(G);

    dfs_test.run(s);

    dfs_test.run(s,t);

    dfs_test.run();

  }

  {

    DType

      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >

      ::SetDistMap<concepts::ReadWriteMap<Node,int> >

      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >

      ::SetProcessedMap<concepts::WriteMap<Node,bool> >

      ::Create dfs_test(G);

    dfs_test.run(s);

    dfs_test.run(s,t);

    dfs_test.run();

    l  = dfs_test.dist(t);

    e  = dfs_test.predArc(t);

    s  = dfs_test.predNode(t);

    b  = dfs_test.reached(t);

    pp = dfs_test.path(t);

  }

}

void checkDfsFunctionCompile()

{

  typedef int VType;

  typedef concepts::Digraph Digraph;

  typedef Digraph::Arc Arc;

  typedef Digraph::Node Node;

  Digraph g;

  bool b;

  dfs(g).run(Node());

  b=dfs(g).run(Node(),Node());

  dfs(g).run();

  dfs(g)

    .predMap(concepts::ReadWriteMap<Node,Arc>())

    .distMap(concepts::ReadWriteMap<Node,VType>())

    .reachedMap(concepts::ReadWriteMap<Node,bool>())

    .processedMap(concepts::WriteMap<Node,bool>())

    .run(Node());

  b=dfs(g)

    .predMap(concepts::ReadWriteMap<Node,Arc>())

    .distMap(concepts::ReadWriteMap<Node,VType>())

    .reachedMap(concepts::ReadWriteMap<Node,bool>())

    .processedMap(concepts::WriteMap<Node,bool>())

    .path(concepts::Path<Digraph>())

    .dist(VType())

    .run(Node(),Node());

  dfs(g)

    .predMap(concepts::ReadWriteMap<Node,Arc>())

    .distMap(concepts::ReadWriteMap<Node,VType>())

    .reachedMap(concepts::ReadWriteMap<Node,bool>())

    .processedMap(concepts::WriteMap<Node,bool>())

    .run();

}

template <class Digraph>

void checkDfs() {

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  Digraph G;

 * purpose.

 *

 */

#include <lemon/concepts/digraph.h>

#include <lemon/smart_graph.h>

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/dijkstra.h>

#include <lemon/path.h>

#include <lemon/bin_heap.h>

#include "graph_test.h"

#include "test_tools.h"

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "@arcs\n"

  "     label length\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 checkDijkstraCompile()

{

  typedef int VType;

  typedef concepts::Digraph Digraph;

  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;

  typedef Dijkstra<Digraph, LengthMap> DType;

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  Digraph G;

  Arc e;

  VType l;

  bool b;

  DType::DistMap d(G);

  DType::PredMap p(G);

  LengthMap length;

  Path<Digraph> pp;

  {

    DType dijkstra_test(G,length);

    dijkstra_test.run(s);

    dijkstra_test.run(s,t);

    l  = dijkstra_test.dist(t);

    e  = dijkstra_test.predArc(t);

    s  = dijkstra_test.predNode(t);

    b  = dijkstra_test.reached(t);

    pp = dijkstra_test.path(t);

  }

}

void checkDijkstraFunctionCompile()

{

  typedef int VType;

  typedef concepts::Digraph Digraph;

  typedef Digraph::Arc Arc;

  typedef Digraph::Node Node;

  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;

  Digraph g;

  bool b;

  dijkstra(g,LengthMap()).run(Node());

  b=dijkstra(g,LengthMap()).run(Node(),Node());

  dijkstra(g,LengthMap())

    .predMap(concepts::ReadWriteMap<Node,Arc>())

    .distMap(concepts::ReadWriteMap<Node,VType>())

    .processedMap(concepts::WriteMap<Node,bool>())

    .run(Node());

  b=dijkstra(g,LengthMap())

    .predMap(concepts::ReadWriteMap<Node,Arc>())

    .distMap(concepts::ReadWriteMap<Node,VType>())

    .processedMap(concepts::WriteMap<Node,bool>())

    .path(concepts::Path<Digraph>())

    .dist(VType())

    .run(Node(),Node());

}

template <class Digraph>

void checkDijkstra() {

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  typedef typename Digraph::template ArcMap<int> LengthMap;

  Digraph G;

  Node s, t;

  LengthMap length(G);

  std::istringstream input(test_lgf);

  digraphReader(G, input).

    arcMap("length", length).

    node("source", s).

    node("target", t).

    run();

  Dijkstra<Digraph, LengthMap>

        dijkstra_test(G, length);

  "5\n"

  "6\n"

  "7\n"

  "8\n"

  "9\n"

  "@arcs\n"

  "    label capacity\n"

  "0 1 0     20\n"

  "0 2 1     0\n"

  "1 1 2     3\n"

  "1 2 3     8\n"

  "1 3 4     8\n"

  "2 5 5     5\n"

  "3 2 6     5\n"

  "3 5 7     5\n"

  "3 6 8     5\n"

  "4 3 9     3\n"

  "5 7 10    3\n"

  "5 6 11    10\n"

  "5 8 12    10\n"

  "6 8 13    8\n"

  "8 9 14    20\n"

  "8 1 15    5\n"

  "9 5 16    5\n"

  "@attributes\n"

  "source 1\n"

  "target 8\n";

void checkPreflowCompile()

{

  typedef int VType;

  typedef concepts::Digraph Digraph;

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  typedef concepts::ReadMap<Arc,VType> CapMap;

  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;

  typedef concepts::WriteMap<Node,bool> CutMap;

  typedef Elevator<Digraph, Digraph::Node> Elev;

  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;

  Digraph g;

  Node n;

  Arc e;

  CapMap cap;

  FlowMap flow;

  CutMap cut;

  preflow_test.init();

  preflow_test.init(cap);

  preflow_test.startFirstPhase();

  preflow_test.startSecondPhase();

  preflow_test.run();

  preflow_test.runMinCut();

}

int cutValue (const SmartDigraph& g,

              const SmartDigraph::NodeMap<bool>& cut,

              const SmartDigraph::ArcMap<int>& cap) {

  int c=0;

  for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {

    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];

  }

  return c;

}

bool checkFlow(const SmartDigraph& g,

               const SmartDigraph::ArcMap<int>& flow,

               const SmartDigraph::ArcMap<int>& cap,

               SmartDigraph::Node s, SmartDigraph::Node t) {

  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {

    if (flow[e] < 0 || flow[e] > cap[e]) return false;

  }

  for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {

    if (n == s || n == t) continue;

    int sum = 0;

    for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {

      sum += flow[e];

    }

    for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {

      sum -= flow[e];

    }

    if (sum != 0) return false;

  }

  return true;

}

int main() {

  typedef SmartDigraph Digraph;

  typedef Digraph::Node Node;

  typedef Digraph::NodeIt NodeIt;

  typedef Digraph::ArcIt ArcIt;

  typedef Digraph::ArcMap<int> CapMap;

  typedef Digraph::ArcMap<int> FlowMap;

  typedef Digraph::NodeMap<bool> CutMap;

  typedef Preflow<Digraph, CapMap> PType;