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.

 *

 */

/**

\dir demo

\brief A collection of demo applications.

#include<lemon/dijkstra.h>

\endcode

*/

/**

\dir concepts

\brief Concept descriptors and checking classes.

This directory contains the concept descriptors and concept checking tools.

For more information see the \ref concept "Concepts" module.

*/

/**

\dir bits

\brief Auxiliary tools for implementation.

maps and some other classes.

As a user you typically don't have to deal with these files.

*/

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

 *

 */

/**

@defgroup datas Data Structures

This group describes the several data structures implemented in LEMON.

- Finally, They can serve as a skeleton of a new implementation of a concept.

*/

/**

@defgroup graph_concepts Graph Structure Concepts

@ingroup concept

\brief Skeleton and concept checking classes for graph structures

This group describes the skeletons and concept checking classes of LEMON's

graph structures and helper classes used to implement these.

*/

/**

@defgroup map_concepts Map Concepts

@ingroup concept

\brief Skeleton and concept checking classes for maps

This group describes the skeletons and concept checking classes of maps.

*/

/**

\anchor demoprograms

@defgroup demos Demo programs

Some demo programs are listed here. Their full source codes can be found in

the \c demo subdirectory of the source tree.

It order to compile them, use <tt>--enable-demo</tt> configure option when

build the library.

*/

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

/*!

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

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

#define LEMON_BITS_DEFAULT_MAP_H

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

#define LEMON_BITS_MAP_EXTENDER_H

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

#define LEMON_BITS_PRED_MAP_PATH_H

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

      double tck=sysconf(_SC_CLK_TCK);

      times(&ts);

      utime=ts.tms_utime/tck;

      stime=ts.tms_stime/tck;

      cutime=ts.tms_cutime/tck;

      cstime=ts.tms_cstime/tck;

#endif

    }

    std::string getWinFormattedDate()

    {

      std::ostringstream os;

#ifdef WIN32

      SYSTEMTIME time;

      GetSystemTime(&time);

      char buf1[11], buf2[9], buf3[5];

                        ("ddd MMM dd"), buf1, 11) &&

          GetTimeFormat(MY_LOCALE, 0, &time,

                        ("HH':'mm':'ss"), buf2, 9) &&

          GetDateFormat(MY_LOCALE, 0, &time,

                        ("yyyy"), buf3, 5)) {

        os << buf1 << ' ' << buf2 << ' ' << buf3;

      }

      else os << "unknown";

#else

      timeval tv;

      gettimeofday(&tv, 0);

      char cbuf[26];

      ctime_r(&tv.tv_sec,cbuf);

      os << cbuf;

#endif

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

#define LEMON_CORE_H

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

#define LEMON_DFS_H

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

#define LEMON_GRAPH_TO_EPS_H

          } else if (!isWhiteSpace(c)) {

            getline(is, line);

            ++line_num;

          }

        }

        if (is) is.putback(c);

        else if (is.eof()) is.clear();

      }

    };

  }

  template <typename Digraph>

  class DigraphReader;

  template <typename Digraph>

                                       std::istream& is = std::cin);

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(Digraph& digraph, const std::string& fn);

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(Digraph& digraph, const char *fn);

  /// \ingroup lemon_io

  ///

  /// \brief \ref lgf-format "LGF" reader for directed graphs

  ///

  /// This utility reads an \ref lgf-format "LGF" file.

  ///

  /// The reading method does a batch processing. The user creates a

  /// reader object, then various reading rules can be added to the

  /// reader, and eventually the reading is executed with the \c run()

  /// member function. A map reading rule can be added to the reader

      for (typename Attributes::iterator it = _attributes.begin();

           it != _attributes.end(); ++it) {

        delete it->second;

      }

      if (local_is) {

        delete _is;

      }

    }

  private:

    template <typename DGR>

    friend DigraphReader<DGR> digraphReader(DGR& digraph, std::istream& is);

    template <typename DGR>

                                            const std::string& fn);

    template <typename DGR>

    friend DigraphReader<DGR> digraphReader(DGR& digraph, const char *fn);

    DigraphReader(DigraphReader& other)

      : _is(other._is), local_is(other.local_is), _digraph(other._digraph),

        _use_nodes(other._use_nodes), _use_arcs(other._use_arcs),

        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {

      other._is = 0;

      other.local_is = false;

      _node_index.swap(other._node_index);

      _arc_index.swap(other._arc_index);

      _node_maps.swap(other._node_maps);

    DigraphReader<Digraph> tmp(digraph, fn);

    return tmp;

  }

  /// \brief Return a \ref DigraphReader class

  ///

  /// This function just returns a \ref DigraphReader class.

  /// \relates DigraphReader

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(Digraph& digraph, const char* fn) {

    DigraphReader<Digraph> tmp(digraph, fn);

    return tmp;

  }

  template <typename Graph>

  class GraphReader;

  template <typename Graph>

                                 std::istream& is = std::cin);

  template <typename Graph>

  GraphReader<Graph> graphReader(Graph& graph, const std::string& fn);

  template <typename Graph>

  GraphReader<Graph> graphReader(Graph& graph, const char *fn);

  /// \ingroup lemon_io

  ///

  /// \brief \ref lgf-format "LGF" reader for undirected graphs

  ///

  /// This utility reads an \ref lgf-format "LGF" file.

  ///

  /// It can be used almost the same way as \c DigraphReader.

  /// The only difference is that this class can handle edges and

  /// edge maps as well as arcs and arc maps.

  ///

      for (typename Attributes::iterator it = _attributes.begin();

           it != _attributes.end(); ++it) {

        delete it->second;

      }

      if (local_is) {

        delete _is;

      }

    }

  private:

    template <typename GR>

    friend GraphReader<GR> graphReader(GR& graph, std::istream& is);

    template <typename GR>

    template <typename GR>

    friend GraphReader<GR> graphReader(GR& graph, const char *fn);

    GraphReader(GraphReader& other)

      : _is(other._is), local_is(other.local_is), _graph(other._graph),

        _use_nodes(other._use_nodes), _use_edges(other._use_edges),

        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {

      other._is = 0;

      other.local_is = false;

      _node_index.swap(other._node_index);

      _edge_index.swap(other._edge_index);

      _node_maps.swap(other._node_maps);

      _edge_maps.swap(other._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.

 *

 */

///\ingroup lemon_io

///\file

///\brief \ref lgf-format "LEMON Graph Format" writer.

        delete it->second;

      }

      for (typename Attributes::iterator it = _attributes.begin();

           it != _attributes.end(); ++it) {

        delete it->second;

      }

      if (local_os) {

        delete _os;

      }

    }

  private:

    template <typename DGR>

                                            std::ostream& os);

    template <typename DGR>

    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,

                                            const std::string& fn);

    template <typename DGR>

    friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,

                                            const char *fn);

    DigraphWriter(DigraphWriter& other)

      : _os(other._os), local_os(other.local_os), _digraph(other._digraph),

        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {

      other._os = 0;

      other.local_os = false;

      _node_index.swap(other._node_index);

      if (local_os) {

        delete _os;

      }

    }

  private:

    template <typename GR>

    friend GraphWriter<GR> graphWriter(const GR& graph,

                                       std::ostream& os);

    template <typename GR>

    friend GraphWriter<GR> graphWriter(const GR& graph,

                                       const std::string& fn);

    template <typename GR>

    friend GraphWriter<GR> graphWriter(const GR& graph,

                                       const char *fn);

    GraphWriter(GraphWriter& other)

      : _os(other._os), local_os(other.local_os), _graph(other._graph),

        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {

      other._os = 0;

      other.local_os = false;

      _node_index.swap(other._node_index);

      _edge_index.swap(other._edge_index);

      _node_maps.swap(other._node_maps);

      _edge_maps.swap(other._edge_maps);

      _attributes.swap(other._attributes);

      _nodes_caption = other._nodes_caption;

      _edges_caption = other._edges_caption;

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

#define LEMON_LIST_GRAPH_H

    public:

      Edge() {}

      Edge (Invalid) { id = -1; }

      bool operator==(const Edge& edge) const {return id == edge.id;}

      bool operator!=(const Edge& edge) const {return id != edge.id;}

      bool operator<(const Edge& edge) const {return id < edge.id;}

    };

    class Arc {

      friend class ListGraphBase;

    protected:

      int id;

      explicit Arc(int pid) { id = pid;}

    public:

      }

      Arc() {}

      Arc (Invalid) { id = -1; }

      bool operator==(const Arc& arc) const {return id == arc.id;}

      bool operator!=(const Arc& arc) const {return id != arc.id;}

      bool operator<(const Arc& arc) const {return id < arc.id;}

    };

    ListGraphBase()

      : nodes(), first_node(-1),

        first_free_node(-1), arcs(), first_free_arc(-1) {}

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

 *

 */

///\ingroup paths

///\file

///\brief Classes for representing paths in digraphs.

      static void copy(const From& from, To& to) {

        to.clear();

        for (typename From::RevArcIt it(from); it != INVALID; ++it) {

          to.addFront(it);

        }

      }

    };

    template <typename From, typename To>

    struct PathCopySelectorBackward<From, To, true> {

      static void copy(const From& from, To& to) {

        to.clear();

        to.buildRev(from);

      }

    };

    template <typename From, typename To,

              bool revEnable = RevPathTagIndicator<From>::value>

    struct PathCopySelector {

      static void copy(const From& from, To& to) {

        PathCopySelectorForward<From, To>::copy(from, to);

    };

    template <typename From, typename To>

    struct PathCopySelector<From, To, true> {

      static void copy(const From& from, To& to) {

        PathCopySelectorBackward<From, To>::copy(from, to);

    };

  }

  /// \brief Make a copy of a path.

  ///

  /// This function makes a copy of a path.

  template <typename From, typename To>

  void pathCopy(const From& from, To& to) {

    checkConcept<concepts::PathDumper<typename From::Digraph>, From>();

    _path_bits::PathCopySelector<From, To>::copy(from, to);

  }

  /// \brief Deprecated version of \ref pathCopy().

  ///

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

 *

 */

/*

 * This file contains the reimplemented version of the Mersenne Twister

 * Generator of Matsumoto and Nishimura.

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

#define LEMON_SMART_GRAPH_H

    public:

      Edge() {}

      Edge (Invalid) { _id = -1; }

      bool operator==(const Edge& arc) const {return _id == arc._id;}

      bool operator!=(const Edge& arc) const {return _id != arc._id;}

      bool operator<(const Edge& arc) const {return _id < arc._id;}

    };

    class Arc {

      friend class SmartGraphBase;

    protected:

      int _id;

      explicit Arc(int id) { _id = id;}

    public:

      }

      Arc() {}

      Arc (Invalid) { _id = -1; }

      bool operator==(const Arc& arc) const {return _id == arc._id;}

      bool operator!=(const Arc& arc) const {return _id != arc._id;}

      bool operator<(const Arc& arc) const {return _id < arc._id;}

    };

    SmartGraphBase()

      : nodes(), arcs() {}

    int maxNodeId() const { return nodes.size()-1; }

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

#define LEMON_TIME_MEASURE_H

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

#define LEMON_TOLERANCE_H

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

#define LEMON_UNION_FIND_H

          } else {

            int pd = nodes[jd].parent;

            if (nodes[nodes[jd].next].size < cmax) {

              pushLeft(nodes[jd].next, nodes[jd].left);

              if (less(jd, nodes[jd].next) ||

                  nodes[jd].item == nodes[pd].item) {

                nodes[nodes[jd].next].prio = nodes[jd].prio;

                nodes[nodes[jd].next].item = nodes[jd].item;

              }

              popLeft(pd);

              deleteNode(jd);

              jd = pd;

            } else {

              int ld = nodes[nodes[jd].next].left;

              popLeft(nodes[jd].next);

              pushRight(jd, ld);

                  nodes[ld].item == nodes[pd].item) {

                nodes[jd].item = nodes[ld].item;

                nodes[jd].prio = nodes[ld].prio;

              }

              if (nodes[nodes[jd].next].item == nodes[ld].item) {

                setPrio(nodes[jd].next);

              }

              jd = nodes[jd].left;

            }

          }

        } else {

          jd = nodes[jd].left;

        }

      }

    }

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

      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>

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