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,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

namespace lemon {

/*!

\page lgf-format LEMON Graph Format (LGF)

The \e LGF is a <em>column oriented</em>

file format for storing graphs and associated data like

node and edge maps.

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

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H

#define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H

#include <lemon/core.h>

#include <lemon/error.h>

namespace lemon {

  template <typename _Digraph>

  class DigraphAdaptorExtender : public _Digraph {

    typedef _Digraph Parent;

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

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_PATH_DUMP_H

#define LEMON_BITS_PATH_DUMP_H

#include <lemon/core.h>

#include <lemon/concept_check.h>

namespace lemon {

  template <typename _Digraph, typename _PredMap>

  class PredMapPath {

  public:

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

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

///\file

///\brief Some basic non-inline functions and static global data.

#include<lemon/bits/windows.h>

#ifdef WIN32

#ifndef WIN32_LEAN_AND_MEAN

#define WIN32_LEAN_AND_MEAN

#endif

#ifndef NOMINMAX

#define NOMINMAX

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

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_COST_SCALING_H

#define LEMON_COST_SCALING_H

/// \ingroup min_cost_flow_algs

/// \file

/// \brief Cost scaling algorithm for finding a minimum cost flow.

#include <vector>

#include <deque>

#include <limits>

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

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_MAPS_H

#define LEMON_MAPS_H

#include <iterator>

#include <functional>

#include <vector>

#include <map>

#include <lemon/core.h>

///\file

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

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_PREFLOW_H

#define LEMON_PREFLOW_H

#include <lemon/tolerance.h>

#include <lemon/elevator.h>

/// \file

/// \ingroup max_flow

/// \brief Implementation of the preflow algorithm.

namespace lemon {

          }

        }

        queue.swap(nqueue);

      }

      _level->initFinish();

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

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

        if (_tolerance.positive(rem)) {

          Node u = _graph.target(e);

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

          _flow->set(e, (*_capacity)[e]);

          (*_excess)[u] += rem;

        }

      }

      for (InArcIt e(_graph, _source); e != INVALID; ++e) {

        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

    /// maximum flow is not yet obtained. So after calling this method

    /// \ref flowValue() returns the value of a maximum flow and \ref

    /// minCut() returns a minimum cut.

    /// \pre One of the \ref init() functions must be called before

    /// using this function.

    void startFirstPhase() {

      _phase = true;

      while (true) {

        int num = _node_num;

        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) {

              if (!_level->active(v) && v != _target) {

                _level->activate(v);

              }

              if (!_tolerance.less(rem, excess)) {

                _flow->set(e, (*_flow)[e] + excess);

                (*_excess)[v] += excess;

                excess = 0;

                goto no_more_push_1;

              } else {

                excess -= rem;

                (*_excess)[v] += rem;

                _flow->set(e, (*_capacity)[e]);

              }

            } else if (new_level > (*_level)[v]) {

              new_level = (*_level)[v];

            }

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

 * 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/dfs.h>

#include <lemon/path.h>

#include "graph_test.h"

#include "test_tools.h"

using namespace lemon;

  Path<Digraph> p = dfs_test.path(t);

  check(p.length() == dfs_test.dist(t),"path() found a wrong path.");

  check(checkPath(G, p),"path() found a wrong path.");

  check(pathSource(G, p) == s,"path() found a wrong path.");

  check(pathTarget(G, p) == t,"path() found a wrong path.");

  for(NodeIt v(G); v!=INVALID; ++v) {

    if (dfs_test.reached(v)) {

      check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");

      if (dfs_test.predArc(v)!=INVALID ) {

        Arc e=dfs_test.predArc(v);

        Node u=G.source(e);

        check(u==dfs_test.predNode(v),"Wrong tree.");

        check(dfs_test.dist(v) - dfs_test.dist(u) == 1,

              "Wrong distance. (" << dfs_test.dist(u) << "->"

              << dfs_test.dist(v) << ")");

      }

    }

  }

  {

  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()

{

  checkDfs<ListDigraph>();

  checkDfs<SmartDigraph>();

  return 0;

}

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

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#include <lemon/smart_graph.h>

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/error.h>

#include "test_tools.h"

using namespace std;

using namespace lemon;

void digraph_copy_test() {

      SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]);

      fam[arc] = i + j * j;

      if (i == 0 && j == 0) fa = arc;

    }

  }

  // Test digraph copy

  ListDigraph to;

  ListDigraph::NodeMap<int> tnm(to);

  ListDigraph::ArcMap<int> tam(to);

  ListDigraph::Node tn;

  ListDigraph::Arc ta;

  SmartDigraph::NodeMap<ListDigraph::Node> nr(from);

  SmartDigraph::ArcMap<ListDigraph::Arc> er(from);

  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 (SmartDigraph::ArcIt it(from); it != INVALID; ++it) {

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

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

    check(nr[from.source(it)] == to.source(er[it]), "Wrong copy.");

    check(nr[from.target(it)] == to.target(er[it]), "Wrong copy.");

  }

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

    check(nr[ncr[it]] == 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

  SmartGraph from;

  SmartGraph::NodeMap<int> fnm(from);

  SmartGraph::ArcMap<int> fam(from);

  SmartGraph::EdgeMap<int> fem(from);

  SmartGraph::Node fn = INVALID;

  SmartGraph::Arc fa = INVALID;

  SmartGraph::Edge fe = INVALID;

  std::vector<SmartGraph::Node> fnv;

  for (int i = 0; i < nn; ++i) {

    SmartGraph::Node node = from.addNode();

    fnv.push_back(node);

    fnm[node] = i * i;

    if (i == 0) fn = node;

  }

    check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),

          "Wrong copy.");

    check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),

          "Wrong copy.");

    check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),

          "Wrong copy.");

  }

  for (ListGraph::NodeIt it(to); it != INVALID; ++it) {

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

  }

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

    check(ar[acr[it]] == it, "Wrong copy.");

  }

  for (ListGraph::EdgeIt it(to); it != INVALID; ++it) {

    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();

  graph_copy_test();

  return 0;

}

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

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#include <iostream>

#include <fstream>

#include <string>

#include <vector>

#include <lemon/concept_check.h>

#include <lemon/concepts/heap.h>

#include <lemon/smart_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/dijkstra.h>

  "1\n"

  "@arcs\n"

  "     -\n"

  "0 1\n";

char test_lgf_bad1[] =

  "@nodes\n"

  "label\n"

  "0\n"

  "1\n"

  "@arcs\n"

  "     - another\n"

  "0 1\n";

char test_lgf_bad2[] =

  "@nodes\n"

  "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();

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

    check(countArcs(d) == 2,"There should be 2 arcs");

  }

  {

    ListGraph g;

    ListGraph::Node s,t;

    ListGraph::EdgeMap<int> label(g);

    std::istringstream input(test_lgf);

    graphReader(g, input).

      node("source", s).

      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);

    bool ok=false;

    try {

      graphReader(g, input).

        run();

    }

    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)

      {

        ok = true;

      }

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

  }

  {

    ListGraph g;

    std::istringstream input(test_lgf_bad2);

    bool ok=false;

    try {

      graphReader(g, input).

        run();

    }

    catch (FormatError& error)

      {

        ok = true;

      }

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

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#include <deque>

#include <set>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

#include <lemon/maps.h>

#include <lemon/list_graph.h>

#include <lemon/smart_graph.h>

#include <lemon/adaptors.h>

#include <lemon/dfs.h>

#include <algorithm>

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

 * 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/preflow.h>

#include <lemon/concepts/digraph.h>

#include <lemon/concepts/maps.h>

#include <lemon/lgf_reader.h>

#include <lemon/elevator.h>

using namespace lemon;

               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;

}

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<SmartDigraph> pre(g,cap,s,t);

  pre.init(iflow);

  pre.startFirstPhase();

  check(pre.flowValue() == 10, "The incorrect max flow value.");

  check(pre.minCut(s), "Wrong min cut (Node s).");

  check(pre.minCut(n1), "Wrong min cut (Node n1).");

  check(!pre.minCut(n2), "Wrong min cut (Node n2).");

  check(!pre.minCut(t), "Wrong min cut (Node t).");

}

int main() {

  typedef SmartDigraph Digraph;

  preflow_test.flowMap(flow);

  NodeIt tmp1(g,s);

  ++tmp1;

  if ( tmp1 != INVALID ) s=tmp1;

  NodeIt tmp2(g,t);

  ++tmp2;

  if ( tmp2 != INVALID ) t=tmp2;

  preflow_test.source(s);

  preflow_test.target(t);

  preflow_test.run();

  CutMap min_cut3(g);

  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;

}