RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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,

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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,

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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,

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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,

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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,

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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,

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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,

        Value rem = (*_flow)[e];

        if (_tolerance.positive(rem)) {

          Node v = _graph.source(e);

          if ((*_level)[v] == _level->maxLevel()) continue;

          _flow->set(e, 0);

          (*_excess)[v] += rem;

        }

      }

        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))

          _level->activate(n);

      return true;

    }

    /// \brief Starts the first phase of the preflow algorithm.

    ///

    /// The preflow algorithm consists of two phases, this method runs

    /// the first phase. After the first phase the maximum flow value

    /// and a minimum value cut can already be computed, although a

        Node n = INVALID;

        int level = -1;

        while (num > 0) {

          n = _level->highestActive();

          if (n == INVALID) goto first_phase_done;

          level = _level->highestActiveLevel();

          --num;

          Value excess = (*_excess)[n];

          int new_level = _level->maxLevel();

          for (OutArcIt e(_graph, n); e != INVALID; ++e) {

            Value rem = (*_capacity)[e] - (*_flow)[e];

            if (!_tolerance.positive(rem)) continue;

            Node v = _graph.target(e);

            if ((*_level)[v] < level) {

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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,

      }

    }

  }

  {

  Dfs<Digraph> dfs(G);

  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");

  }

  {

    NullMap<Node,Arc> myPredMap;

    dfs(G).predMap(myPredMap).run(s);

  }

}

int main()

{

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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,

  ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);

  ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);

  digraphCopy(from, to).

    nodeMap(fnm, tnm).arcMap(fam, tam).

    nodeRef(nr).arcRef(er).

    nodeCrossRef(ncr).arcCrossRef(ecr).

    node(fn, tn).arc(fa, ta).run();

  check(countNodes(from) == countNodes(to), "Wrong copy.");

  check(countArcs(from) == countArcs(to), "Wrong copy.");

  for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {

    check(ncr[nr[it]] == it, "Wrong copy.");

    check(fnm[it] == tnm[nr[it]], "Wrong copy.");

  }

  for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {

    check(er[ecr[it]] == it, "Wrong copy.");

  }

  check(tn == nr[fn], "Wrong copy.");

  check(ta == er[fa], "Wrong copy.");

  // Test repeated copy

  digraphCopy(from, to).run();

  check(countNodes(from) == countNodes(to), "Wrong copy.");

  check(countArcs(from) == countArcs(to), "Wrong copy.");

}

void graph_copy_test() {

  const int nn = 10;

  // Build a graph

    check(er[ecr[it]] == it, "Wrong copy.");

  }

  check(tn == nr[fn], "Wrong copy.");

  check(ta == ar[fa], "Wrong copy.");

  check(te == er[fe], "Wrong copy.");

  // Test repeated copy

  graphCopy(from, to).run();

  check(countNodes(from) == countNodes(to), "Wrong copy.");

  check(countEdges(from) == countEdges(to), "Wrong copy.");

  check(countArcs(from) == countArcs(to), "Wrong copy.");

}

int main() {

  digraph_copy_test();

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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,

  "label\n"

  "0\n"

  "1\n"

  "@arcs\n"

  "     label -\n"

  "0 1\n";

{

  {

    ListDigraph::Node s,t;

    ListDigraph::ArcMap<int> label(d);

    std::istringstream input(test_lgf);

    digraphReader(d, input).

      node("source", s).

      node("target", t).

      arcMap("label", label).

      run();

      node("target", t).

      edgeMap("label", label).

      run();

    check(countNodes(g) == 2,"There should be 2 nodes");

    check(countEdges(g) == 2,"There should be 2 arcs");

  }

  {

    std::istringstream input(test_lgf_nomap);

    digraphReader(d, input).

      run();

    check(countNodes(d) == 2,"There should be 2 nodes");

    check(countArcs(d) == 1,"There should be 1 arc");

  }

  {

    ListGraph g;

    std::istringstream input(test_lgf_nomap);

    graphReader(g, input).

      run();

    check(countNodes(g) == 2,"There should be 2 nodes");

    check(countEdges(g) == 1,"There should be 1 edge");

  }

  {

    std::istringstream input(test_lgf_bad1);

    bool ok=false;

    try {

      digraphReader(d, input).

        run();

    }

      {

        ok = true;

      }

    check(ok,"FormatError exception should have occured");

  }

  {

    ListGraph g;

    std::istringstream input(test_lgf_bad1);

    catch (FormatError& error)

      {

        ok = true;

      }

    check(ok,"FormatError exception should have occured");

  }

  {

    std::istringstream input(test_lgf_bad2);

    bool ok=false;

    try {

      digraphReader(d, input).

        run();

    }

    catch (FormatError& error)

      {

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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,

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * 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,

    if (sum != 0) return false;

  }

  return true;

}

void initFlowTest()

{

  DIGRAPH_TYPEDEFS(SmartDigraph);

  SmartDigraph g;

  SmartDigraph::ArcMap<int> cap(g),iflow(g);

  Node s=g.addNode(); Node t=g.addNode();

  Node n1=g.addNode(); Node n2=g.addNode();

  Arc a;

  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;

  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;

  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;

  preflow_test.minCutMap(min_cut3);

  min_cut_value=cutValue(g,min_cut3,cap);

  check(preflow_test.flowValue() == min_cut_value,

        "The max flow value or the three min cut values are incorrect.");

  initFlowTest();

  return 0;

}