lemon/graph_utils.h
changeset 1829 183b4cbf9733
parent 1811 597ce92fae73
child 1830 ffd6d50fb155
equal deleted inserted replaced
31:9d74a9666cda 32:a5223e8d1e8b
   108   }
   108   }
   109 
   109 
   110   // Node counting:
   110   // Node counting:
   111 
   111 
   112   template <typename Graph>
   112   template <typename Graph>
   113   inline
   113   inline typename enable_if<typename Graph::NodeNumTag, int>::type
   114   typename enable_if<typename Graph::NodeNumTag, int>::type
       
   115   _countNodes(const Graph &g) {
   114   _countNodes(const Graph &g) {
   116     return g.nodeNum();
   115     return g.nodeNum();
   117   }
   116   }
   118 
   117 
   119   template <typename Graph>
   118   template <typename Graph>
   135   }
   134   }
   136 
   135 
   137   // Edge counting:
   136   // Edge counting:
   138 
   137 
   139   template <typename Graph>
   138   template <typename Graph>
   140   inline
   139   inline typename enable_if<typename Graph::EdgeNumTag, int>::type
   141   typename enable_if<typename Graph::EdgeNumTag, int>::type
       
   142   _countEdges(const Graph &g) {
   140   _countEdges(const Graph &g) {
   143     return g.edgeNum();
   141     return g.edgeNum();
   144   }
   142   }
   145 
   143 
   146   template <typename Graph>
   144   template <typename Graph>
   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     }