RhodeCode

    template <typename Graph, typename Enable = void>

    struct CountArcsSelector {

      static int count(const Graph &g) {

        return countItems<Graph, typename Graph::Arc>(g);

      }

    };

    template <typename Graph>

    struct CountArcsSelector<

      Graph,

      typename enable_if<typename Graph::ArcNumTag, void>::type>

    {

      static int count(const Graph &g) {

        return g.arcNum();

      }

    };

  }

  /// \brief Function to count the arcs in the graph.

  ///

  /// This function counts the arcs in the graph.

  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some

  /// graph structures it is specialized to run in <em>O</em>(1).

  ///

  /// \note If the graph contains a \c arcNum() member function and a

  /// \c ArcNumTag tag then this function calls directly the member

  /// function to query the cardinality of the arc set.

  template <typename Graph>

  inline int countArcs(const Graph& g) {

    return _core_bits::CountArcsSelector<Graph>::count(g);

  }

  // Edge counting:

  namespace _core_bits {

    template <typename Graph, typename Enable = void>

    struct CountEdgesSelector {

      static int count(const Graph &g) {

        return countItems<Graph, typename Graph::Edge>(g);

      }

    };

    template <typename Graph>

    struct CountEdgesSelector<

      Graph,

      typename enable_if<typename Graph::EdgeNumTag, void>::type>

    {

      static int count(const Graph &g) {

        return g.edgeNum();

      }

    };

  }

  /// \brief Function to count the edges in the graph.

  ///

  /// This function counts the edges in the graph.

  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some

  /// graph structures it is specialized to run in <em>O</em>(1).

  ///

  /// \note If the graph contains a \c edgeNum() member function and a

  /// \c EdgeNumTag tag then this function calls directly the member

  /// function to query the cardinality of the edge set.

  template <typename Graph>

  inline int countEdges(const Graph& g) {

    return _core_bits::CountEdgesSelector<Graph>::count(g);

  }

  template <typename Graph, typename DegIt>

  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {

    int num = 0;

    for (DegIt it(_g, _n); it != INVALID; ++it) {

      ++num;

    }

    return num;

  }

  /// \brief Function to count the number of the out-arcs from node \c n.

  ///

  /// This function counts the number of the out-arcs from node \c n

  /// in the graph \c g.

  template <typename Graph>

  inline int countOutArcs(const Graph& g,  const typename Graph::Node& n) {

    return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);

  }

  /// \brief Function to count the number of the in-arcs to node \c n.

  ///

  /// This function counts the number of the in-arcs to node \c n

  /// in the graph \c g.

  template <typename Graph>

  inline int countInArcs(const Graph& g,  const typename Graph::Node& n) {

    return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);

  }

  /// \brief Function to count the number of the inc-edges to node \c n.

  ///

  /// This function counts the number of the inc-edges to node \c n

  /// in the undirected graph \c g.

  template <typename Graph>

  inline int countIncEdges(const Graph& g,  const typename Graph::Node& n) {

    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);

  }

  namespace _core_bits {

    template <typename Digraph, typename Item, typename RefMap>

    class MapCopyBase {

    public:

      virtual void copy(const Digraph& from, const RefMap& refMap) = 0;

      virtual ~MapCopyBase() {}

    };

    template <typename Digraph, typename Item, typename RefMap,

              typename FromMap, typename ToMap>

    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {

    public:

      MapCopy(const FromMap& map, ToMap& tmap)

        : _map(map), _tmap(tmap) {}

      virtual void copy(const Digraph& digraph, const RefMap& refMap) {

        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;

        for (ItemIt it(digraph); it != INVALID; ++it) {

          _tmap.set(refMap[it], _map[it]);

        }

      }

    private:

      const FromMap& _map;

      ToMap& _tmap;

    };

    template <typename Digraph, typename Item, typename RefMap, typename It>

    class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {

    public:

      ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}

      virtual void copy(const Digraph&, const RefMap& refMap) {

        _it = refMap[_item];

      }

    private:

      Item _item;

      It& _it;

    };

    template <typename Digraph, typename Item, typename RefMap, typename Ref>

    class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {

    public:

      RefCopy(Ref& map) : _map(map) {}

      virtual void copy(const Digraph& digraph, const RefMap& refMap) {

        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;

        for (ItemIt it(digraph); it != INVALID; ++it) {

          _map.set(it, refMap[it]);

        }

      }

    private:

      Ref& _map;

    };

    template <typename Digraph, typename Item, typename RefMap,

              typename CrossRef>

    class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {

    public:

      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}

      virtual void copy(const Digraph& digraph, const RefMap& refMap) {

        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;

        for (ItemIt it(digraph); it != INVALID; ++it) {

          _cmap.set(refMap[it], it);

        }

      }

    private:

      CrossRef& _cmap;

    };

    template <typename Digraph, typename Enable = void>

    struct DigraphCopySelector {

      template <typename From, typename NodeRefMap, typename ArcRefMap>

      static void copy(const From& from, Digraph &to,

                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {

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

          nodeRefMap[it] = to.addNode();

        }

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

          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],

                                    nodeRefMap[from.target(it)]);

        }

      }

    };

    template <typename Digraph>

    struct DigraphCopySelector<

      Digraph,

      typename enable_if<typename Digraph::BuildTag, void>::type>

    {

      template <typename From, typename NodeRefMap, typename ArcRefMap>

      static void copy(const From& from, Digraph &to,

                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {

        to.build(from, nodeRefMap, arcRefMap);

      }

    };

    template <typename Graph, typename Enable = void>

    struct GraphCopySelector {

      template <typename From, typename NodeRefMap, typename EdgeRefMap>

      static void copy(const From& from, Graph &to,

                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {

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

          nodeRefMap[it] = to.addNode();

        }

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

          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],

                                      nodeRefMap[from.v(it)]);

        }

      }

    };

    template <typename Graph>

    struct GraphCopySelector<

      Graph,

      typename enable_if<typename Graph::BuildTag, void>::type>

    {

      template <typename From, typename NodeRefMap, typename EdgeRefMap>

      static void copy(const From& from, Graph &to,

                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {

        to.build(from, nodeRefMap, edgeRefMap);

      }

    };

  }

  /// \brief Class to copy a digraph.

  ///

  /// Class to copy a digraph to another digraph (duplicate a digraph). The

  /// simplest way of using it is through the \c digraphCopy() function.

  ///

  /// This class not only make a copy of a digraph, but it can create

  /// references and cross references between the nodes and arcs of

  /// the two digraphs, and it can copy maps to use with the newly created

  /// digraph.

  ///

  /// To make a copy from a digraph, first an instance of DigraphCopy

  /// should be created, then the data belongs to the digraph should

  /// assigned to copy. In the end, the \c run() member should be

  /// called.

  ///

  /// The next code copies a digraph with several data:

  ///\code

  ///  DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);

  ///  // Create references for the nodes

  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);

  ///  cg.nodeRef(nr);

  ///  // Create cross references (inverse) for the arcs

  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);

  ///  cg.arcCrossRef(acr);

  ///  // Copy an arc map

  ///  OrigGraph::ArcMap<double> oamap(orig_graph);

  ///  NewGraph::ArcMap<double> namap(new_graph);

  ///  cg.arcMap(oamap, namap);

  ///  // Copy a node

  ///  OrigGraph::Node on;

  ///  NewGraph::Node nn;

  ///  cg.node(on, nn);

  ///  // Execute copying

  ///  cg.run();

  ///\endcode

  template <typename From, typename To>

  class DigraphCopy {

  private:

    typedef typename From::Node Node;

    typedef typename From::NodeIt NodeIt;

    typedef typename From::Arc Arc;

    typedef typename From::ArcIt ArcIt;

    typedef typename To::Node TNode;

    typedef typename To::Arc TArc;

    typedef typename From::template NodeMap<TNode> NodeRefMap;

    typedef typename From::template ArcMap<TArc> ArcRefMap;

  public:

    /// \brief Constructor of DigraphCopy.

    ///

    /// Constructor of DigraphCopy for copying the content of the

    /// \c from digraph into the \c to digraph.

    DigraphCopy(const From& from, To& to)

      : _from(from), _to(to) {}

    /// \brief Destructor of DigraphCopy

    ///

    /// Destructor of DigraphCopy.

    ~DigraphCopy() {

      for (int i = 0; i < int(_node_maps.size()); ++i) {

        delete _node_maps[i];

      }

      for (int i = 0; i < int(_arc_maps.size()); ++i) {

        delete _arc_maps[i];

      }

    }

    /// \brief Copy the node references into the given map.

    ///

    /// This function copies the node references into the given map.

    /// The parameter should be a map, whose key type is the Node type of

    /// the source digraph, while the value type is the Node type of the

    /// destination digraph.

    template <typename NodeRef>

    DigraphCopy& nodeRef(NodeRef& map) {

      _node_maps.push_back(new _core_bits::RefCopy<From, Node,

                           NodeRefMap, NodeRef>(map));

      return *this;

    }

    /// \brief Copy the node cross references into the given map.

    ///

    /// This function copies the node cross references (reverse references)

    /// into the given map. The parameter should be a map, whose key type

    /// is the Node type of the destination digraph, while the value type is

    /// the Node type of the source digraph.

    template <typename NodeCrossRef>

    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {

      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,

                           NodeRefMap, NodeCrossRef>(map));

      return *this;

    }

    /// \brief Make a copy of the given node map.

    ///

    /// This function makes a copy of the given node map for the newly

    /// created digraph.

    /// The key type of the new map \c tmap should be the Node type of the

    /// destination digraph, and the key type of the original map \c map

    /// should be the Node type of the source digraph.

    template <typename FromMap, typename ToMap>

    DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {

      _node_maps.push_back(new _core_bits::MapCopy<From, Node,

                           NodeRefMap, FromMap, ToMap>(map, tmap));

      return *this;

    }

    /// \brief Make a copy of the given node.

    ///

    /// This function makes a copy of the given node.

    DigraphCopy& node(const Node& node, TNode& tnode) {

      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,

                           NodeRefMap, TNode>(node, tnode));

      return *this;

    }

    /// \brief Copy the arc references into the given map.

    ///

    /// This function copies the arc references into the given map.

    /// The parameter should be a map, whose key type is the Arc type of

    /// the source digraph, while the value type is the Arc type of the

    /// destination digraph.

    template <typename ArcRef>

    DigraphCopy& arcRef(ArcRef& map) {

      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,

                          ArcRefMap, ArcRef>(map));

      return *this;

    }

    /// \brief Copy the arc cross references into the given map.

    ///

    /// This function copies the arc cross references (reverse references)

    /// into the given map. The parameter should be a map, whose key type

    /// is the Arc type of the destination digraph, while the value type is

    /// the Arc type of the source digraph.

    template <typename ArcCrossRef>

    DigraphCopy& arcCrossRef(ArcCrossRef& map) {

      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,

                          ArcRefMap, ArcCrossRef>(map));

      return *this;

    }

    /// \brief Make a copy of the given arc map.

    ///

    /// This function makes a copy of the given arc map for the newly

    /// created digraph.

    /// The key type of the new map \c tmap should be the Arc type of the

    /// destination digraph, and the key type of the original map \c map

    /// should be the Arc type of the source digraph.

    template <typename FromMap, typename ToMap>

    DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {

      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,

                          ArcRefMap, FromMap, ToMap>(map, tmap));

      return *this;

    }

    /// \brief Make a copy of the given arc.

    ///

    /// This function makes a copy of the given arc.

    DigraphCopy& arc(const Arc& arc, TArc& tarc) {

      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,

                          ArcRefMap, TArc>(arc, tarc));

      return *this;

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

 *

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

 *

 * Copyright (C) 2003-2009

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

  const int nn = 10;

  SmartDigraph from;

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

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

  SmartDigraph::Node fn = INVALID;

  SmartDigraph::Arc fa = INVALID;

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

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

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

    fnv.push_back(node);

    fnm[node] = i * i;

    if (i == 0) fn = node;

  }

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

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

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

      fam[arc] = i + j * j;

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

    }

  }

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

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

}

void graph_copy_test() {

  const int nn = 10;

  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;

  }

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

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

      SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]);

      fem[edge] = i * i + j * j;

      fam[from.direct(edge, true)] = i + j * j;

      fam[from.direct(edge, false)] = i * i + j;

      if (i == 0 && j == 0) fa = from.direct(edge, true);

      if (i == 0 && j == 0) fe = edge;

    }

  }

  ListGraph to;

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

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

  ListGraph::EdgeMap<int> tem(to);

  ListGraph::Node tn;

  ListGraph::Arc ta;

  ListGraph::Edge te;

  SmartGraph::NodeMap<ListGraph::Node> nr(from);

  SmartGraph::ArcMap<ListGraph::Arc> ar(from);

  SmartGraph::EdgeMap<ListGraph::Edge> er(from);

  ListGraph::NodeMap<SmartGraph::Node> ncr(to);

  ListGraph::ArcMap<SmartGraph::Arc> acr(to);

  ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);

  graphCopy(from, to).

    nodeMap(fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem).

    nodeRef(nr).arcRef(ar).edgeRef(er).

    nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).

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

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

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

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

  }

  for (SmartGraph::ArcIt it(from); it != INVALID; ++it) {

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

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

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

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

  }

  for (SmartGraph::EdgeIt it(from); it != INVALID; ++it) {

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

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

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

}

int main() {

  digraph_copy_test();

  graph_copy_test();

  return 0;

}