RhodeCode

    //Creates the maps if necessary.

    //Creates the maps if necessary.

  /// \tparam _Graph The graph this map is attached to.

// The contents of this file was inspired by the concept checking

// utility of the BOOST library (http://www.boost.org).

  ///Create convenient typedefs for the digraph types and iterators

  ///This \c \#define creates convenient type definitions for the following

  ///types of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,

  typedef Digraph::ArcMap<double> DoubleArcMap;

  ///Create convenient typedefs for the digraph types and iterators

  typedef typename Digraph::template ArcMap<double> DoubleArcMap;

  ///Create convenient typedefs for the graph types and iterators

  ///This \c \#define creates the same convenient type definitions as defined

  ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()

  typedef Graph::EdgeMap<double> DoubleEdgeMap;

  ///Create convenient typedefs for the graph types and iterators

  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap;

  /// \brief Function to count the items in a graph.

  /// This function counts the items (nodes, arcs etc.) in a graph.

  /// The complexity of the function is linear because

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

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

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

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

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

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

  /// in the graph \c g.

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

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

  /// in the graph \c g.

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

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

  /// in the undirected graph \c g.

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

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

              typename FromMap, typename ToMap>

      MapCopy(const FromMap& map, ToMap& tmap)

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

      const FromMap& _map;

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

      Item _item;

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

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

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

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

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

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

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

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

  ///  // Create references for the nodes

  ///  cg.nodeRef(nr);

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

  ///  cg.arcCrossRef(acr);

  ///  // Copy an arc map

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

  ///  // Copy a node

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

  ///  // Execute copying

  ///  cg.run();

  template <typename From, typename To>

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

    /// \brief Destructor of DigraphCopy

    /// Destructor of DigraphCopy.

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

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

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

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

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

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

                           NodeRefMap, TNode>(node, tnode));

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

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

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

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

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

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

                          ArcRefMap, TArc>(arc, tarc));

    /// \brief Execute copying.

    /// This function executes the copying of the digraph along with the

    /// copying of the assigned data.

        copy(_from, _to, nodeRefMap, arcRefMap);

      _node_maps;

      _arc_maps;

  /// This function copies a digraph to another digraph.

  /// The complete usage of it is detailed in the DigraphCopy class, but

  /// a short example shows a basic work:

  /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();

  /// \c acr will contain the mapping from the arcs of the \c to digraph

  template <typename From, typename To>

  DigraphCopy<From, To> digraphCopy(const From& from, To& to) {

    return DigraphCopy<From, To>(from, to);

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

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

  /// the two graphs, and it can copy maps for using with the newly created

  /// graph.

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

  ///  // Create references for the nodes

  ///  cg.nodeRef(nr);

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

  ///  NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);

  ///  cg.edgeCrossRef(ecr);

  ///  // Copy an edge map

  ///  OrigGraph::EdgeMap<double> oemap(orig_graph);

  ///  NewGraph::EdgeMap<double> nemap(new_graph);

  ///  cg.edgeMap(oemap, nemap);

  ///  // Copy a node

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

  ///  // Execute copying

  ///  cg.run();

  template <typename From, typename To>

      ArcRefMap(const From& from, const To& to,

        : _from(from), _to(to),

      const From& _from;

    /// \brief Constructor of GraphCopy.

    /// Constructor of GraphCopy for copying the content of the

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

    GraphCopy(const From& from, To& to)

    /// \brief Destructor of GraphCopy

    /// Destructor of GraphCopy.

    /// \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 graph, while the value type is the Node type of the

    /// destination graph.

    /// \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 graph, while the value type is

    /// the Node type of the source graph.

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

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

    /// created graph.

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

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

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

    template <typename FromMap, typename ToMap>

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

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

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

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

                           NodeRefMap, TNode>(node, tnode));

    /// \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 graph, while the value type is the Arc type of the

    /// destination graph.

    /// \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 graph, while the value type is

    /// the Arc type of the source graph.

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

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

    /// created graph.

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

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

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

    template <typename FromMap, typename ToMap>

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

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

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

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

                          ArcRefMap, TArc>(arc, tarc));

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

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

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

    /// the source graph, while the value type is the Edge type of the

    /// destination graph.

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

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

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

    /// is the Edge type of the destination graph, while the value type is

    /// the Edge type of the source graph.

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

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

    /// created graph.

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

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

    /// should be the Edge type of the source graph.

    template <typename FromMap, typename ToMap>

    GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {

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

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

    GraphCopy& edge(const Edge& edge, TEdge& tedge) {

                           EdgeRefMap, TEdge>(edge, tedge));

    /// \brief Execute copying.

    /// This function executes the copying of the graph along with the

    /// copying of the assigned data.

      ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);

        copy(_from, _to, nodeRefMap, edgeRefMap);

      _node_maps;

      _arc_maps;

      _edge_maps;

  /// This function copies a graph to another graph.

  /// The complete usage of it is detailed in the GraphCopy class,

  /// but a short example shows a basic work:

  /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();

  /// \c ecr will contain the mapping from the edges of the \c to graph

  /// to the edges of the \c from graph.

  template <typename From, typename To>

  GraphCopy<From, To>

  graphCopy(const From& from, To& to) {

    return GraphCopy<From, To>(from, to);

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

  /// \brief Find an arc between two nodes of a digraph.

  /// This function finds an arc from node \c u to node \c v in the

  /// digraph \c g.

  /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {

  /// \note \ref ConArcIt provides iterator interface for the same

  /// functionality.

  ///

  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp

  /// \brief Iterator for iterating on parallel arcs connecting the same nodes.

  /// Iterator for iterating on parallel arcs connecting the same nodes. It is

  /// a higher level interface for the \ref findArc() function. You can

  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp

    /// Construct a new ConArcIt iterating on the arcs that

    /// connects nodes \c u and \c v.

    /// Construct a new ConArcIt that continues the iterating from arc \c a.

  /// \brief Find an edge between two nodes of a graph.

  /// This function finds an edge from node \c u to node \c v in graph \c g.

  /// If node \c u and node \c v is equal then each loop edge

  /// it finds the first edge from \c u to \c v. Otherwise it looks for

  /// the next edge from \c u to \c v after \c prev.

  /// \return The found edge or \ref INVALID if there is no such an edge.

  /// Thus you can iterate through each edge between \c u and \c v

  /// as it follows.

  /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {

  /// \note \ref ConEdgeIt provides iterator interface for the same

  /// functionality.

  ///

  /// \brief Iterator for iterating on parallel edges connecting the same nodes.

  /// Iterator for iterating on parallel edges connecting the same nodes.

  /// It is a higher level interface for the findEdge() function. You can

  /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {

    /// Construct a new ConEdgeIt iterating on the edges that

    /// connects nodes \c u and \c v.

    /// Construct a new ConEdgeIt that continues iterating from edge \c e.

  ///Dynamic arc look-up between given endpoints.

  ///source to a given target in amortized time <em>O</em>(log<em>d</em>),

  ///This is a dynamic data structure. Consider to use \ref ArcLookUp or

  ///\ref AllArcLookUp if your digraph is not changed so frequently.

  ///This class uses a self-adjusting binary search tree, the Splay tree

  ///of Sleator and Tarjan to guarantee the logarithmic amortized

  ///time bound for arc look-ups. This class also guarantees the

    ///\param s The source node.

    ///\param t The target node.

    ///int n = 0;

    ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;

    ///Finding the arcs take at most <em>O</em>(log<em>d</em>)

    ///structure is updated after each graph alteration. Thus although

    ///this data structure is theoretically faster than \ref ArcLookUp

    ///and \ref AllArcLookup, it often provides worse performance than

  ///Fast arc look-up between given endpoints.

  ///source to a given target in time <em>O</em>(log<em>d</em>),

  ///\warning This class is static, so you should call refresh() (or at

  ///least refresh(Node)) to refresh this data structure whenever the

  ///digraph changes. This is a time consuming (superlinearly proportional

  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).

    ///Refresh the search data structure at a node.

    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>

    ///is the number of the outgoing arcs of \c n.

    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is

    ///the number of the arcs in the digraph and <em>D</em> is the maximum