COIN-OR::LEMON - Graph Library

Changeset 1069:d1a48668ddb4 in lemon-main for lemon


Ignore:
Timestamp:
07/30/13 15:14:29 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
1067:8a3fb3155dca (diff), 1068:756022ac1674 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge fix #470

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/core.h

    r1027 r1069  
    3636#ifdef _MSC_VER
    3737#pragma warning( disable : 4250 4355 4503 4800 4996 )
     38#endif
     39
     40#ifdef __GNUC__
     41// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
     42#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
    3843#endif
    3944
  • lemon/core.h

    r1068 r1069  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    154154  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
    155155
     156  ///Create convenience typedefs for the bipartite graph types and iterators
     157
     158  ///This \c \#define creates the same convenient type definitions as
     159  ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it
     160  ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap,
     161  ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt,
     162  ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap.
     163  ///
     164  ///\note If the graph type is a dependent type, ie. the graph type depend
     165  ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
     166  ///macro.
     167#define BPGRAPH_TYPEDEFS(BpGraph)                                       \
     168  GRAPH_TYPEDEFS(BpGraph);                                              \
     169  typedef BpGraph::RedNode RedNode;                                     \
     170  typedef BpGraph::RedNodeIt RedNodeIt;                                 \
     171  typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap;                     \
     172  typedef BpGraph::RedNodeMap<int> IntRedNodeMap;                       \
     173  typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap;                 \
     174  typedef BpGraph::BlueNode BlueNode;                                   \
     175  typedef BpGraph::BlueNodeIt BlueNodeIt;                               \
     176  typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap;                   \
     177  typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap;                     \
     178  typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap
     179
     180  ///Create convenience typedefs for the bipartite graph types and iterators
     181
     182  ///\see BPGRAPH_TYPEDEFS
     183  ///
     184  ///\note Use this macro, if the graph type is a dependent type,
     185  ///ie. the graph type depend on a template parameter.
     186#define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph)                                  \
     187  TEMPLATE_GRAPH_TYPEDEFS(BpGraph);                                         \
     188  typedef typename BpGraph::RedNode RedNode;                                \
     189  typedef typename BpGraph::RedNodeIt RedNodeIt;                            \
     190  typedef typename BpGraph::template RedNodeMap<bool> BoolRedNodeMap;       \
     191  typedef typename BpGraph::template RedNodeMap<int> IntRedNodeMap;         \
     192  typedef typename BpGraph::template RedNodeMap<double> DoubleRedNodeMap;   \
     193  typedef typename BpGraph::BlueNode BlueNode;                              \
     194  typedef typename BpGraph::BlueNodeIt BlueNodeIt;                          \
     195  typedef typename BpGraph::template BlueNodeMap<bool> BoolBlueNodeMap;     \
     196  typedef typename BpGraph::template BlueNodeMap<int> IntBlueNodeMap;       \
     197  typedef typename BpGraph::template BlueNodeMap<double> DoubleBlueNodeMap
     198
    156199  /// \brief Function to count the items in a graph.
    157200  ///
     
    205248  }
    206249
     250  namespace _graph_utils_bits {
     251   
     252    template <typename Graph, typename Enable = void>
     253    struct CountRedNodesSelector {
     254      static int count(const Graph &g) {
     255        return countItems<Graph, typename Graph::RedNode>(g);
     256      }
     257    };
     258
     259    template <typename Graph>
     260    struct CountRedNodesSelector<
     261      Graph, typename
     262      enable_if<typename Graph::NodeNumTag, void>::type>
     263    {
     264      static int count(const Graph &g) {
     265        return g.redNum();
     266      }
     267    };   
     268  }
     269
     270  /// \brief Function to count the red nodes in the graph.
     271  ///
     272  /// This function counts the red nodes in the graph.
     273  /// The complexity of the function is O(n) but for some
     274  /// graph structures it is specialized to run in O(1).
     275  ///
     276  /// If the graph contains a \e redNum() member function and a
     277  /// \e NodeNumTag tag then this function calls directly the member
     278  /// function to query the cardinality of the node set.
     279  template <typename Graph>
     280  inline int countRedNodes(const Graph& g) {
     281    return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g);
     282  }
     283
     284  namespace _graph_utils_bits {
     285   
     286    template <typename Graph, typename Enable = void>
     287    struct CountBlueNodesSelector {
     288      static int count(const Graph &g) {
     289        return countItems<Graph, typename Graph::BlueNode>(g);
     290      }
     291    };
     292
     293    template <typename Graph>
     294    struct CountBlueNodesSelector<
     295      Graph, typename
     296      enable_if<typename Graph::NodeNumTag, void>::type>
     297    {
     298      static int count(const Graph &g) {
     299        return g.blueNum();
     300      }
     301    };   
     302  }
     303
     304  /// \brief Function to count the blue nodes in the graph.
     305  ///
     306  /// This function counts the blue nodes in the graph.
     307  /// The complexity of the function is O(n) but for some
     308  /// graph structures it is specialized to run in O(1).
     309  ///
     310  /// If the graph contains a \e blueNum() member function and a
     311  /// \e NodeNumTag tag then this function calls directly the member
     312  /// function to query the cardinality of the node set.
     313  template <typename Graph>
     314  inline int countBlueNodes(const Graph& g) {
     315    return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g);
     316  }
     317
    207318  // Arc counting:
    208319
     
    446557      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    447558      static void copy(const From& from, Graph &to,
    448                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
     559                       NodeRefMap& nodeRefMap,
     560                       EdgeRefMap& edgeRefMap) {
    449561        to.build(from, nodeRefMap, edgeRefMap);
    450562      }
    451563    };
    452564
     565    template <typename BpGraph, typename Enable = void>
     566    struct BpGraphCopySelector {
     567      template <typename From, typename RedNodeRefMap,
     568                typename BlueNodeRefMap, typename EdgeRefMap>
     569      static void copy(const From& from, BpGraph &to,
     570                       RedNodeRefMap& redNodeRefMap,
     571                       BlueNodeRefMap& blueNodeRefMap,
     572                       EdgeRefMap& edgeRefMap) {
     573        to.clear();
     574        for (typename From::RedNodeIt it(from); it != INVALID; ++it) {
     575          redNodeRefMap[it] = to.addRedNode();
     576        }
     577        for (typename From::BlueNodeIt it(from); it != INVALID; ++it) {
     578          blueNodeRefMap[it] = to.addBlueNode();
     579        }
     580        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
     581          edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
     582                                      blueNodeRefMap[from.blueNode(it)]);
     583        }
     584      }
     585    };
     586
     587    template <typename BpGraph>
     588    struct BpGraphCopySelector<
     589      BpGraph,
     590      typename enable_if<typename BpGraph::BuildTag, void>::type>
     591    {
     592      template <typename From, typename RedNodeRefMap,
     593                typename BlueNodeRefMap, typename EdgeRefMap>
     594      static void copy(const From& from, BpGraph &to,
     595                       RedNodeRefMap& redNodeRefMap,
     596                       BlueNodeRefMap& blueNodeRefMap,
     597                       EdgeRefMap& edgeRefMap) {
     598        to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
     599      }
     600    };
     601
    453602  }
     603
     604  /// \brief Check whether a graph is undirected.
     605  ///
     606  /// This function returns \c true if the given graph is undirected.
     607#ifdef DOXYGEN
     608  template <typename GR>
     609  bool undirected(const GR& g) { return false; }
     610#else
     611  template <typename GR>
     612  typename enable_if<UndirectedTagIndicator<GR>, bool>::type
     613  undirected(const GR&) {
     614    return true;
     615  }
     616  template <typename GR>
     617  typename disable_if<UndirectedTagIndicator<GR>, bool>::type
     618  undirected(const GR&) {
     619    return false;
     620  }
     621#endif
    454622
    455623  /// \brief Class to copy a digraph.
     
    9761144  graphCopy(const From& from, To& to) {
    9771145    return GraphCopy<From, To>(from, to);
     1146  }
     1147
     1148  /// \brief Class to copy a bipartite graph.
     1149  ///
     1150  /// Class to copy a bipartite graph to another graph (duplicate a
     1151  /// graph). The simplest way of using it is through the
     1152  /// \c bpGraphCopy() function.
     1153  ///
     1154  /// This class not only make a copy of a bipartite graph, but it can
     1155  /// create references and cross references between the nodes, edges
     1156  /// and arcs of the two graphs, and it can copy maps for using with
     1157  /// the newly created graph.
     1158  ///
     1159  /// To make a copy from a graph, first an instance of BpGraphCopy
     1160  /// should be created, then the data belongs to the graph should
     1161  /// assigned to copy. In the end, the \c run() member should be
     1162  /// called.
     1163  ///
     1164  /// The next code copies a graph with several data:
     1165  ///\code
     1166  ///  BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
     1167  ///  // Create references for the nodes
     1168  ///  OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
     1169  ///  cg.nodeRef(nr);
     1170  ///  // Create cross references (inverse) for the edges
     1171  ///  NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph);
     1172  ///  cg.edgeCrossRef(ecr);
     1173  ///  // Copy a red node map
     1174  ///  OrigBpGraph::RedNodeMap<double> ormap(orig_graph);
     1175  ///  NewBpGraph::RedNodeMap<double> nrmap(new_graph);
     1176  ///  cg.redNodeMap(ormap, nrmap);
     1177  ///  // Copy a node
     1178  ///  OrigBpGraph::Node on;
     1179  ///  NewBpGraph::Node nn;
     1180  ///  cg.node(on, nn);
     1181  ///  // Execute copying
     1182  ///  cg.run();
     1183  ///\endcode
     1184  template <typename From, typename To>
     1185  class BpGraphCopy {
     1186  private:
     1187
     1188    typedef typename From::Node Node;
     1189    typedef typename From::RedNode RedNode;
     1190    typedef typename From::BlueNode BlueNode;
     1191    typedef typename From::NodeIt NodeIt;
     1192    typedef typename From::Arc Arc;
     1193    typedef typename From::ArcIt ArcIt;
     1194    typedef typename From::Edge Edge;
     1195    typedef typename From::EdgeIt EdgeIt;
     1196
     1197    typedef typename To::Node TNode;
     1198    typedef typename To::RedNode TRedNode;
     1199    typedef typename To::BlueNode TBlueNode;
     1200    typedef typename To::Arc TArc;
     1201    typedef typename To::Edge TEdge;
     1202
     1203    typedef typename From::template RedNodeMap<TRedNode> RedNodeRefMap;
     1204    typedef typename From::template BlueNodeMap<TBlueNode> BlueNodeRefMap;
     1205    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
     1206
     1207    struct NodeRefMap {
     1208      NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
     1209                 const BlueNodeRefMap& blue_node_ref)
     1210        : _from(from), _red_node_ref(red_node_ref),
     1211          _blue_node_ref(blue_node_ref) {}
     1212
     1213      typedef typename From::Node Key;
     1214      typedef typename To::Node Value;
     1215
     1216      Value operator[](const Key& key) const {
     1217        if (_from.red(key)) {
     1218          return _red_node_ref[_from.asRedNodeUnsafe(key)];
     1219        } else {
     1220          return _blue_node_ref[_from.asBlueNodeUnsafe(key)];
     1221        }
     1222      }
     1223
     1224      const From& _from;
     1225      const RedNodeRefMap& _red_node_ref;
     1226      const BlueNodeRefMap& _blue_node_ref;
     1227    };
     1228
     1229    struct ArcRefMap {
     1230      ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
     1231        : _from(from), _to(to), _edge_ref(edge_ref) {}
     1232
     1233      typedef typename From::Arc Key;
     1234      typedef typename To::Arc Value;
     1235
     1236      Value operator[](const Key& key) const {
     1237        return _to.direct(_edge_ref[key], _from.direction(key));
     1238      }
     1239
     1240      const From& _from;
     1241      const To& _to;
     1242      const EdgeRefMap& _edge_ref;
     1243    };
     1244
     1245  public:
     1246
     1247    /// \brief Constructor of BpGraphCopy.
     1248    ///
     1249    /// Constructor of BpGraphCopy for copying the content of the
     1250    /// \c from graph into the \c to graph.
     1251    BpGraphCopy(const From& from, To& to)
     1252      : _from(from), _to(to) {}
     1253
     1254    /// \brief Destructor of BpGraphCopy
     1255    ///
     1256    /// Destructor of BpGraphCopy.
     1257    ~BpGraphCopy() {
     1258      for (int i = 0; i < int(_node_maps.size()); ++i) {
     1259        delete _node_maps[i];
     1260      }
     1261      for (int i = 0; i < int(_red_maps.size()); ++i) {
     1262        delete _red_maps[i];
     1263      }
     1264      for (int i = 0; i < int(_blue_maps.size()); ++i) {
     1265        delete _blue_maps[i];
     1266      }
     1267      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     1268        delete _arc_maps[i];
     1269      }
     1270      for (int i = 0; i < int(_edge_maps.size()); ++i) {
     1271        delete _edge_maps[i];
     1272      }
     1273    }
     1274
     1275    /// \brief Copy the node references into the given map.
     1276    ///
     1277    /// This function copies the node references into the given map.
     1278    /// The parameter should be a map, whose key type is the Node type of
     1279    /// the source graph, while the value type is the Node type of the
     1280    /// destination graph.
     1281    template <typename NodeRef>
     1282    BpGraphCopy& nodeRef(NodeRef& map) {
     1283      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
     1284                           NodeRefMap, NodeRef>(map));
     1285      return *this;
     1286    }
     1287
     1288    /// \brief Copy the node cross references into the given map.
     1289    ///
     1290    /// This function copies the node cross references (reverse references)
     1291    /// into the given map. The parameter should be a map, whose key type
     1292    /// is the Node type of the destination graph, while the value type is
     1293    /// the Node type of the source graph.
     1294    template <typename NodeCrossRef>
     1295    BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
     1296      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
     1297                           NodeRefMap, NodeCrossRef>(map));
     1298      return *this;
     1299    }
     1300
     1301    /// \brief Make a copy of the given node map.
     1302    ///
     1303    /// This function makes a copy of the given node map for the newly
     1304    /// created graph.
     1305    /// The key type of the new map \c tmap should be the Node type of the
     1306    /// destination graph, and the key type of the original map \c map
     1307    /// should be the Node type of the source graph.
     1308    template <typename FromMap, typename ToMap>
     1309    BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
     1310      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
     1311                           NodeRefMap, FromMap, ToMap>(map, tmap));
     1312      return *this;
     1313    }
     1314
     1315    /// \brief Make a copy of the given node.
     1316    ///
     1317    /// This function makes a copy of the given node.
     1318    BpGraphCopy& node(const Node& node, TNode& tnode) {
     1319      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
     1320                           NodeRefMap, TNode>(node, tnode));
     1321      return *this;
     1322    }
     1323
     1324    /// \brief Copy the red node references into the given map.
     1325    ///
     1326    /// This function copies the red node references into the given
     1327    /// map.  The parameter should be a map, whose key type is the
     1328    /// Node type of the source graph with the red item set, while the
     1329    /// value type is the Node type of the destination graph.
     1330    template <typename RedRef>
     1331    BpGraphCopy& redRef(RedRef& map) {
     1332      _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
     1333                          RedNodeRefMap, RedRef>(map));
     1334      return *this;
     1335    }
     1336
     1337    /// \brief Copy the red node cross references into the given map.
     1338    ///
     1339    /// This function copies the red node cross references (reverse
     1340    /// references) into the given map. The parameter should be a map,
     1341    /// whose key type is the Node type of the destination graph with
     1342    /// the red item set, while the value type is the Node type of the
     1343    /// source graph.
     1344    template <typename RedCrossRef>
     1345    BpGraphCopy& redCrossRef(RedCrossRef& map) {
     1346      _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
     1347                          RedNodeRefMap, RedCrossRef>(map));
     1348      return *this;
     1349    }
     1350
     1351    /// \brief Make a copy of the given red node map.
     1352    ///
     1353    /// This function makes a copy of the given red node map for the newly
     1354    /// created graph.
     1355    /// The key type of the new map \c tmap should be the Node type of
     1356    /// the destination graph with the red items, and the key type of
     1357    /// the original map \c map should be the Node type of the source
     1358    /// graph.
     1359    template <typename FromMap, typename ToMap>
     1360    BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) {
     1361      _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
     1362                          RedNodeRefMap, FromMap, ToMap>(map, tmap));
     1363      return *this;
     1364    }
     1365
     1366    /// \brief Make a copy of the given red node.
     1367    ///
     1368    /// This function makes a copy of the given red node.
     1369    BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
     1370      _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
     1371                          RedNodeRefMap, TRedNode>(node, tnode));
     1372      return *this;
     1373    }
     1374
     1375    /// \brief Copy the blue node references into the given map.
     1376    ///
     1377    /// This function copies the blue node references into the given
     1378    /// map.  The parameter should be a map, whose key type is the
     1379    /// Node type of the source graph with the blue item set, while the
     1380    /// value type is the Node type of the destination graph.
     1381    template <typename BlueRef>
     1382    BpGraphCopy& blueRef(BlueRef& map) {
     1383      _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
     1384                           BlueNodeRefMap, BlueRef>(map));
     1385      return *this;
     1386    }
     1387
     1388    /// \brief Copy the blue node cross references into the given map.
     1389    ///
     1390    /// This function copies the blue node cross references (reverse
     1391    /// references) into the given map. The parameter should be a map,
     1392    /// whose key type is the Node type of the destination graph with
     1393    /// the blue item set, while the value type is the Node type of the
     1394    /// source graph.
     1395    template <typename BlueCrossRef>
     1396    BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
     1397      _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
     1398                           BlueNodeRefMap, BlueCrossRef>(map));
     1399      return *this;
     1400    }
     1401
     1402    /// \brief Make a copy of the given blue node map.
     1403    ///
     1404    /// This function makes a copy of the given blue node map for the newly
     1405    /// created graph.
     1406    /// The key type of the new map \c tmap should be the Node type of
     1407    /// the destination graph with the blue items, and the key type of
     1408    /// the original map \c map should be the Node type of the source
     1409    /// graph.
     1410    template <typename FromMap, typename ToMap>
     1411    BpGraphCopy& blueNodeMap(const FromMap& map, ToMap& tmap) {
     1412      _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
     1413                           BlueNodeRefMap, FromMap, ToMap>(map, tmap));
     1414      return *this;
     1415    }
     1416
     1417    /// \brief Make a copy of the given blue node.
     1418    ///
     1419    /// This function makes a copy of the given blue node.
     1420    BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
     1421      _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode,
     1422                           BlueNodeRefMap, TBlueNode>(node, tnode));
     1423      return *this;
     1424    }
     1425
     1426    /// \brief Copy the arc references into the given map.
     1427    ///
     1428    /// This function copies the arc references into the given map.
     1429    /// The parameter should be a map, whose key type is the Arc type of
     1430    /// the source graph, while the value type is the Arc type of the
     1431    /// destination graph.
     1432    template <typename ArcRef>
     1433    BpGraphCopy& arcRef(ArcRef& map) {
     1434      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
     1435                          ArcRefMap, ArcRef>(map));
     1436      return *this;
     1437    }
     1438
     1439    /// \brief Copy the arc cross references into the given map.
     1440    ///
     1441    /// This function copies the arc cross references (reverse references)
     1442    /// into the given map. The parameter should be a map, whose key type
     1443    /// is the Arc type of the destination graph, while the value type is
     1444    /// the Arc type of the source graph.
     1445    template <typename ArcCrossRef>
     1446    BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
     1447      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
     1448                          ArcRefMap, ArcCrossRef>(map));
     1449      return *this;
     1450    }
     1451
     1452    /// \brief Make a copy of the given arc map.
     1453    ///
     1454    /// This function makes a copy of the given arc map for the newly
     1455    /// created graph.
     1456    /// The key type of the new map \c tmap should be the Arc type of the
     1457    /// destination graph, and the key type of the original map \c map
     1458    /// should be the Arc type of the source graph.
     1459    template <typename FromMap, typename ToMap>
     1460    BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
     1461      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
     1462                          ArcRefMap, FromMap, ToMap>(map, tmap));
     1463      return *this;
     1464    }
     1465
     1466    /// \brief Make a copy of the given arc.
     1467    ///
     1468    /// This function makes a copy of the given arc.
     1469    BpGraphCopy& arc(const Arc& arc, TArc& tarc) {
     1470      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
     1471                          ArcRefMap, TArc>(arc, tarc));
     1472      return *this;
     1473    }
     1474
     1475    /// \brief Copy the edge references into the given map.
     1476    ///
     1477    /// This function copies the edge references into the given map.
     1478    /// The parameter should be a map, whose key type is the Edge type of
     1479    /// the source graph, while the value type is the Edge type of the
     1480    /// destination graph.
     1481    template <typename EdgeRef>
     1482    BpGraphCopy& edgeRef(EdgeRef& map) {
     1483      _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
     1484                           EdgeRefMap, EdgeRef>(map));
     1485      return *this;
     1486    }
     1487
     1488    /// \brief Copy the edge cross references into the given map.
     1489    ///
     1490    /// This function copies the edge cross references (reverse references)
     1491    /// into the given map. The parameter should be a map, whose key type
     1492    /// is the Edge type of the destination graph, while the value type is
     1493    /// the Edge type of the source graph.
     1494    template <typename EdgeCrossRef>
     1495    BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
     1496      _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
     1497                           Edge, EdgeRefMap, EdgeCrossRef>(map));
     1498      return *this;
     1499    }
     1500
     1501    /// \brief Make a copy of the given edge map.
     1502    ///
     1503    /// This function makes a copy of the given edge map for the newly
     1504    /// created graph.
     1505    /// The key type of the new map \c tmap should be the Edge type of the
     1506    /// destination graph, and the key type of the original map \c map
     1507    /// should be the Edge type of the source graph.
     1508    template <typename FromMap, typename ToMap>
     1509    BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
     1510      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
     1511                           EdgeRefMap, FromMap, ToMap>(map, tmap));
     1512      return *this;
     1513    }
     1514
     1515    /// \brief Make a copy of the given edge.
     1516    ///
     1517    /// This function makes a copy of the given edge.
     1518    BpGraphCopy& edge(const Edge& edge, TEdge& tedge) {
     1519      _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
     1520                           EdgeRefMap, TEdge>(edge, tedge));
     1521      return *this;
     1522    }
     1523
     1524    /// \brief Execute copying.
     1525    ///
     1526    /// This function executes the copying of the graph along with the
     1527    /// copying of the assigned data.
     1528    void run() {
     1529      RedNodeRefMap redNodeRefMap(_from);
     1530      BlueNodeRefMap blueNodeRefMap(_from);
     1531      NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap);
     1532      EdgeRefMap edgeRefMap(_from);
     1533      ArcRefMap arcRefMap(_from, _to, edgeRefMap);
     1534      _core_bits::BpGraphCopySelector<To>::
     1535        copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap);
     1536      for (int i = 0; i < int(_node_maps.size()); ++i) {
     1537        _node_maps[i]->copy(_from, nodeRefMap);
     1538      }
     1539      for (int i = 0; i < int(_red_maps.size()); ++i) {
     1540        _red_maps[i]->copy(_from, redNodeRefMap);
     1541      }
     1542      for (int i = 0; i < int(_blue_maps.size()); ++i) {
     1543        _blue_maps[i]->copy(_from, blueNodeRefMap);
     1544      }
     1545      for (int i = 0; i < int(_edge_maps.size()); ++i) {
     1546        _edge_maps[i]->copy(_from, edgeRefMap);
     1547      }
     1548      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     1549        _arc_maps[i]->copy(_from, arcRefMap);
     1550      }
     1551    }
     1552
     1553  private:
     1554
     1555    const From& _from;
     1556    To& _to;
     1557
     1558    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
     1559      _node_maps;
     1560
     1561    std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
     1562      _red_maps;
     1563
     1564    std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
     1565      _blue_maps;
     1566
     1567    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
     1568      _arc_maps;
     1569
     1570    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
     1571      _edge_maps;
     1572
     1573  };
     1574
     1575  /// \brief Copy a graph to another graph.
     1576  ///
     1577  /// This function copies a graph to another graph.
     1578  /// The complete usage of it is detailed in the BpGraphCopy class,
     1579  /// but a short example shows a basic work:
     1580  ///\code
     1581  /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
     1582  ///\endcode
     1583  ///
     1584  /// After the copy the \c nr map will contain the mapping from the
     1585  /// nodes of the \c from graph to the nodes of the \c to graph and
     1586  /// \c ecr will contain the mapping from the edges of the \c to graph
     1587  /// to the edges of the \c from graph.
     1588  ///
     1589  /// \see BpGraphCopy
     1590  template <typename From, typename To>
     1591  BpGraphCopy<From, To>
     1592  bpGraphCopy(const From& from, To& to) {
     1593    return BpGraphCopy<From, To>(from, to);
    9781594  }
    9791595
     
    12441860    /// The Digraph type
    12451861    typedef GR Digraph;
    1246 
     1862   
    12471863  protected:
    12481864
    1249     class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
     1865    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
     1866    {
    12501867      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
    12511868
     
    12861903    };
    12871904
    1288   protected: 
     1905  protected:
    12891906
    12901907    const Digraph &_g;
Note: See TracChangeset for help on using the changeset viewer.