COIN-OR::LEMON - Graph Library

Changeset 1253:5958cc5c0a98 in lemon


Ignore:
Timestamp:
08/06/13 12:28:37 (6 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
1252:38c432e01489 (diff), 1247:115031ac8001 (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 further fixes #470

Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/core.h

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

    r1239 r1253  
    3939
    4040#ifdef __GNUC__
     41#define GCC_VERSION (__GNUC__ * 10000                   \
     42                     + __GNUC_MINOR__ * 100             \
     43                     + __GNUC_PATCHLEVEL__)
     44#endif
     45
     46#if GCC_VERSION >= 40800
    4147// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
    4248#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
  • lemon/graph_to_eps.h

    r1247 r1249  
    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).
     
    143143  ///\param gr  Reference to the graph to be printed.
    144144  ///\param ost Reference to the output stream.
    145   ///By default it is <tt>std::cout</tt>.
     145  ///By default, it is <tt>std::cout</tt>.
    146146  ///\param pros If it is \c true, then the \c ostream referenced by \c os
    147147  ///will be explicitly deallocated by the destructor.
     
    513513  ///Turn on/off pre-scaling
    514514
    515   ///By default graphToEps() rescales the whole image in order to avoid
     515  ///By default, graphToEps() rescales the whole image in order to avoid
    516516  ///very big or very small bounding boxes.
    517517  ///
     
    11151115///\param g Reference to the graph to be printed.
    11161116///\param os Reference to the output stream.
    1117 ///By default it is <tt>std::cout</tt>.
     1117///By default, it is <tt>std::cout</tt>.
    11181118///
    11191119///This function also has a lot of
     
    11271127///\endcode
    11281128///
    1129 ///For more detailed examples see the \ref graph_to_eps_demo.cc demo file.
     1129///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file.
    11301130///
    11311131///\warning Don't forget to put the \ref GraphToEps::run() "run()"
  • lemon/graph_to_eps.h

    r1159 r1249  
    223223  using T::_copyright;
    224224
    225   using typename T::NodeTextColorType;
     225  using T::NodeTextColorType;
    226226  using T::CUST_COL;
    227227  using T::DIST_COL;
Note: See TracChangeset for help on using the changeset viewer.