418 /// \brief Increment operator. |
416 /// \brief Increment operator. |
419 /// |
417 /// |
420 /// It increments the iterator and gives back the next edge. |
418 /// It increments the iterator and gives back the next edge. |
421 ConUndirEdgeIt& operator++() { |
419 ConUndirEdgeIt& operator++() { |
422 Parent::operator=(findUndirEdge(graph, graph.source(*this), |
420 Parent::operator=(findUndirEdge(graph, graph.source(*this), |
423 graph.target(*this), *this)); |
421 graph.target(*this), *this)); |
424 return *this; |
422 return *this; |
425 } |
423 } |
426 private: |
424 private: |
427 const Graph& graph; |
425 const Graph& graph; |
428 }; |
426 }; |
936 return Map::operator[](key); |
934 return Map::operator[](key); |
937 } |
935 } |
938 |
936 |
939 protected: |
937 protected: |
940 |
938 |
941 /// \brief Add a new key to the map. |
|
942 /// |
|
943 /// Add a new key to the map. It is called by the |
|
944 /// \c AlterationNotifier. |
|
945 virtual void add(const Key& key) { |
|
946 Map::add(key); |
|
947 } |
|
948 |
|
949 /// \brief Erase the key from the map. |
939 /// \brief Erase the key from the map. |
950 /// |
940 /// |
951 /// Erase the key to the map. It is called by the |
941 /// Erase the key to the map. It is called by the |
952 /// \c AlterationNotifier. |
942 /// \c AlterationNotifier. |
953 virtual void erase(const Key& key) { |
943 virtual void erase(const Key& key) { |
955 typename Container::iterator it = invMap.find(val); |
945 typename Container::iterator it = invMap.find(val); |
956 if (it != invMap.end() && it->second == key) { |
946 if (it != invMap.end() && it->second == key) { |
957 invMap.erase(it); |
947 invMap.erase(it); |
958 } |
948 } |
959 Map::erase(key); |
949 Map::erase(key); |
|
950 } |
|
951 |
|
952 /// \brief Erase more keys from the map. |
|
953 /// |
|
954 /// Erase more keys from the map. It is called by the |
|
955 /// \c AlterationNotifier. |
|
956 virtual void erase(const std::vector<Key>& keys) { |
|
957 for (int i = 0; i < (int)keys.size(); ++i) { |
|
958 Value val = Map::operator[](keys[i]); |
|
959 typename Container::iterator it = invMap.find(val); |
|
960 if (it != invMap.end() && it->second == keys[i]) { |
|
961 invMap.erase(it); |
|
962 } |
|
963 } |
|
964 Map::erase(keys); |
960 } |
965 } |
961 |
966 |
962 /// \brief Clear the keys from the map and inverse map. |
967 /// \brief Clear the keys from the map and inverse map. |
963 /// |
968 /// |
964 /// Clear the keys from the map and inverse map. It is called by the |
969 /// Clear the keys from the map and inverse map. It is called by the |
1068 Map::add(item); |
1073 Map::add(item); |
1069 Map::set(item, invMap.size()); |
1074 Map::set(item, invMap.size()); |
1070 invMap.push_back(item); |
1075 invMap.push_back(item); |
1071 } |
1076 } |
1072 |
1077 |
|
1078 /// \brief Add more new keys to the map. |
|
1079 /// |
|
1080 /// Add more new keys to the map. It is called by the |
|
1081 /// \c AlterationNotifier. |
|
1082 virtual void add(const std::vector<Item>& items) { |
|
1083 Map::add(items); |
|
1084 for (int i = 0; i < (int)items.size(); ++i) { |
|
1085 Map::set(items[i], invMap.size()); |
|
1086 invMap.push_back(items[i]); |
|
1087 } |
|
1088 } |
|
1089 |
1073 /// \brief Erase the key from the map. |
1090 /// \brief Erase the key from the map. |
1074 /// |
1091 /// |
1075 /// Erase the key to the map. It is called by the |
1092 /// Erase the key from the map. It is called by the |
1076 /// \c AlterationNotifier. |
1093 /// \c AlterationNotifier. |
1077 virtual void erase(const Item& item) { |
1094 virtual void erase(const Item& item) { |
1078 Map::set(invMap.back(), Map::operator[](item)); |
1095 Map::set(invMap.back(), Map::operator[](item)); |
1079 invMap[Map::operator[](item)] = invMap.back(); |
1096 invMap[Map::operator[](item)] = invMap.back(); |
1080 invMap.pop_back(); |
1097 invMap.pop_back(); |
1081 Map::erase(item); |
1098 Map::erase(item); |
|
1099 } |
|
1100 |
|
1101 /// \brief Erase more keys from the map. |
|
1102 /// |
|
1103 /// Erase more keys from the map. It is called by the |
|
1104 /// \c AlterationNotifier. |
|
1105 virtual void erase(const std::vector<Item>& items) { |
|
1106 for (int i = 0; i < (int)items.size(); ++i) { |
|
1107 Map::set(invMap.back(), Map::operator[](items[i])); |
|
1108 invMap[Map::operator[](items[i])] = invMap.back(); |
|
1109 invMap.pop_back(); |
|
1110 } |
|
1111 Map::erase(items); |
1082 } |
1112 } |
1083 |
1113 |
1084 /// \brief Build the unique map. |
1114 /// \brief Build the unique map. |
1085 /// |
1115 /// |
1086 /// Build the unique map. It is called by the |
1116 /// Build the unique map. It is called by the |
1377 /// in constant time. On the other hand, the values are updated automatically |
1407 /// in constant time. On the other hand, the values are updated automatically |
1378 /// whenever the graph changes. |
1408 /// whenever the graph changes. |
1379 /// |
1409 /// |
1380 /// \warning Besides addNode() and addEdge(), a graph structure may provide |
1410 /// \warning Besides addNode() and addEdge(), a graph structure may provide |
1381 /// alternative ways to modify the graph. The correct behavior of InDegMap |
1411 /// alternative ways to modify the graph. The correct behavior of InDegMap |
1382 /// is not guarantied if these additional featureas are used. For example |
1412 /// is not guarantied if these additional features are used. For example |
1383 /// the funstions \ref ListGraph::changeSource() "changeSource()", |
1413 /// the functions \ref ListGraph::changeSource() "changeSource()", |
1384 /// \ref ListGraph::changeTarget() "changeTarget()" and |
1414 /// \ref ListGraph::changeTarget() "changeTarget()" and |
1385 /// \ref ListGraph::reverseEdge() "reverseEdge()" |
1415 /// \ref ListGraph::reverseEdge() "reverseEdge()" |
1386 /// of \ref ListGraph will \e not update the degree values correctly. |
1416 /// of \ref ListGraph will \e not update the degree values correctly. |
1387 /// |
1417 /// |
1388 /// \sa OutDegMap |
1418 /// \sa OutDegMap |
1407 typedef typename Parent::Key Key; |
1437 typedef typename Parent::Key Key; |
1408 typedef typename Parent::Value Value; |
1438 typedef typename Parent::Value Value; |
1409 |
1439 |
1410 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {} |
1440 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {} |
1411 |
1441 |
1412 void add(const Key& key) { |
1442 virtual void add(const Key& key) { |
1413 Parent::add(key); |
1443 Parent::add(key); |
1414 Parent::set(key, 0); |
1444 Parent::set(key, 0); |
|
1445 } |
|
1446 virtual void add(const std::vector<Key>& keys) { |
|
1447 Parent::add(keys); |
|
1448 for (int i = 0; i < (int)keys.size(); ++i) { |
|
1449 Parent::set(keys[i], 0); |
|
1450 } |
1415 } |
1451 } |
1416 }; |
1452 }; |
1417 |
1453 |
1418 public: |
1454 public: |
1419 |
1455 |
1449 |
1485 |
1450 virtual void erase(const Edge& edge) { |
1486 virtual void erase(const Edge& edge) { |
1451 --deg[graph.target(edge)]; |
1487 --deg[graph.target(edge)]; |
1452 } |
1488 } |
1453 |
1489 |
1454 virtual void signalChange(const Edge& edge) { |
|
1455 erase(edge); |
|
1456 } |
|
1457 |
|
1458 virtual void commitChange(const Edge& edge) { |
|
1459 add(edge); |
|
1460 } |
|
1461 |
|
1462 virtual void build() { |
1490 virtual void build() { |
1463 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { |
1491 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { |
1464 deg[it] = countInEdges(graph, it); |
1492 deg[it] = countInEdges(graph, it); |
1465 } |
1493 } |
1466 } |
1494 } |
1483 /// in constant time. On the other hand, the values are updated automatically |
1511 /// in constant time. On the other hand, the values are updated automatically |
1484 /// whenever the graph changes. |
1512 /// whenever the graph changes. |
1485 /// |
1513 /// |
1486 /// \warning Besides addNode() and addEdge(), a graph structure may provide |
1514 /// \warning Besides addNode() and addEdge(), a graph structure may provide |
1487 /// alternative ways to modify the graph. The correct behavior of OutDegMap |
1515 /// alternative ways to modify the graph. The correct behavior of OutDegMap |
1488 /// is not guarantied if these additional featureas are used. For example |
1516 /// is not guarantied if these additional features are used. For example |
1489 /// the funstions \ref ListGraph::changeSource() "changeSource()", |
1517 /// the functions \ref ListGraph::changeSource() "changeSource()", |
1490 /// \ref ListGraph::changeTarget() "changeTarget()" and |
1518 /// \ref ListGraph::changeTarget() "changeTarget()" and |
1491 /// \ref ListGraph::reverseEdge() "reverseEdge()" |
1519 /// \ref ListGraph::reverseEdge() "reverseEdge()" |
1492 /// of \ref ListGraph will \e not update the degree values correctly. |
1520 /// of \ref ListGraph will \e not update the degree values correctly. |
1493 /// |
1521 /// |
1494 /// \sa InDegMap |
1522 /// \sa InDegMap |
1513 typedef typename Parent::Key Key; |
1541 typedef typename Parent::Key Key; |
1514 typedef typename Parent::Value Value; |
1542 typedef typename Parent::Value Value; |
1515 |
1543 |
1516 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {} |
1544 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {} |
1517 |
1545 |
1518 void add(const Key& key) { |
1546 virtual void add(const Key& key) { |
1519 Parent::add(key); |
1547 Parent::add(key); |
1520 Parent::set(key, 0); |
1548 Parent::set(key, 0); |
|
1549 } |
|
1550 virtual void add(const std::vector<Key>& keys) { |
|
1551 Parent::add(keys); |
|
1552 for (int i = 0; i < (int)keys.size(); ++i) { |
|
1553 Parent::set(keys[i], 0); |
|
1554 } |
1521 } |
1555 } |
1522 }; |
1556 }; |
1523 |
1557 |
1524 public: |
1558 public: |
1525 |
1559 |
1555 |
1589 |
1556 virtual void erase(const Edge& edge) { |
1590 virtual void erase(const Edge& edge) { |
1557 --deg[graph.source(edge)]; |
1591 --deg[graph.source(edge)]; |
1558 } |
1592 } |
1559 |
1593 |
1560 virtual void signalChange(const Edge& edge) { |
|
1561 erase(edge); |
|
1562 } |
|
1563 |
|
1564 virtual void commitChange(const Edge& edge) { |
|
1565 add(edge); |
|
1566 } |
|
1567 |
|
1568 |
|
1569 virtual void build() { |
1594 virtual void build() { |
1570 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { |
1595 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { |
1571 deg[it] = countOutEdges(graph, it); |
1596 deg[it] = countOutEdges(graph, it); |
1572 } |
1597 } |
1573 } |
1598 } |