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

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

 *

 */

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

 *

 */

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

 *

 */

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

 *

 */

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

 *

 */

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

 *

 */

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

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

 *

 */

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

 *

 */

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

 *

 */

        }

        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.

  ///

      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;

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

  ///

      }

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

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

 *

 */

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

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

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

 *

 */

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

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

 *

 */

        }

      }

    };

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

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

 *

 */

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

 *

 */

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

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

 *

 */

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

 *

 */

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

 *

 */

              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.

 *

 */

        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.

 *

 */

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

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

  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;

}

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

  }

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

 *

 */

typedef ReadWriteMap<A, bool> BoolWriteMap;

typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;

int main()

{

  // Map concepts

  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();

  checkConcept<ReadMap<A,C>, ReadMap<A,C> >();

  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();

  checkConcept<WriteMap<A,C>, WriteMap<A,C> >();

  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();

  checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();

  // NullMap

  {

    checkConcept<ReadWriteMap<A,B>, NullMap<A,B> >();

    NullMap<A,B> map1;

    NullMap<A,B> map2 = map1;

    map1 = nullMap<A,B>();

  }

  // ConstMap

  {

    checkConcept<ReadWriteMap<A,B>, ConstMap<A,B> >();