lemon/graph_utils.h
changeset 1726 f214631ea1ac
parent 1712 4fb435ad31cf
child 1729 06f939455cb1
equal deleted inserted replaced
24:2f315f21c258 25:6b997c996e2e
    23 #include <cmath>
    23 #include <cmath>
    24 
    24 
    25 #include <lemon/invalid.h>
    25 #include <lemon/invalid.h>
    26 #include <lemon/utility.h>
    26 #include <lemon/utility.h>
    27 #include <lemon/maps.h>
    27 #include <lemon/maps.h>
       
    28 #include <lemon/traits.h>
    28 #include <lemon/bits/alteration_notifier.h>
    29 #include <lemon/bits/alteration_notifier.h>
    29 
    30 
    30 ///\ingroup gutils
    31 ///\ingroup gutils
    31 ///\file
    32 ///\file
    32 ///\brief Graph utilities.
    33 ///\brief Graph utilities.
   398     for (; it != INVALID; ++it) {
   399     for (; it != INVALID; ++it) {
   399       target[it] = source[it];
   400       target[it] = source[it];
   400     }
   401     }
   401   }
   402   }
   402 
   403 
   403 
       
   404   /// \brief Class to copy a graph.
   404   /// \brief Class to copy a graph.
   405   ///
   405   ///
   406   /// Class to copy a graph to an other graph (duplicate a graph). The
   406   /// Class to copy a graph to an other graph (duplicate a graph). The
   407   /// simplest way of using it is through the \c copyGraph() function.
   407   /// simplest way of using it is through the \c copyGraph() function.
   408   template <typename Target, typename Source>
   408   template <typename Target, typename Source>
   512     ///
   512     ///
   513     /// Gives back the stored edge references.
   513     /// Gives back the stored edge references.
   514     const EdgeRefMap& edgeRef() const {
   514     const EdgeRefMap& edgeRef() const {
   515       return edgeRefMap;
   515       return edgeRefMap;
   516     }
   516     }
       
   517 
       
   518     void run() {}
   517 
   519 
   518   private:
   520   private:
   519     
   521     
   520     const Source& source;
   522     const Source& source;
   521     Target& target;
   523     Target& target;
   540   template <typename Target, typename Source>
   542   template <typename Target, typename Source>
   541   GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
   543   GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
   542     return GraphCopy<Target, Source>(target, source);
   544     return GraphCopy<Target, Source>(target, source);
   543   }
   545   }
   544 
   546 
   545   template <typename _Graph, typename _Item>
   547   /// \brief Class to copy an undirected graph.
   546   class ItemSetTraits {};
   548   ///
   547   
   549   /// Class to copy an undirected graph to an other graph (duplicate a graph).
   548   template <typename _Graph>
   550   /// The simplest way of using it is through the \c copyUndirGraph() function.
   549   class ItemSetTraits<_Graph, typename _Graph::Node> {
   551   template <typename Target, typename Source>
   550   public:
   552   class UndirGraphCopy {
   551     
   553   public: 
   552     typedef _Graph Graph;
   554     typedef typename Source::Node Node;
   553 
   555     typedef typename Source::NodeIt NodeIt;
   554     typedef typename Graph::Node Item;
   556     typedef typename Source::Edge Edge;
   555     typedef typename Graph::NodeIt ItemIt;
   557     typedef typename Source::EdgeIt EdgeIt;
   556 
   558     typedef typename Source::UndirEdge UndirEdge;
   557     template <typename _Value>
   559     typedef typename Source::UndirEdgeIt UndirEdgeIt;
   558     class Map : public Graph::template NodeMap<_Value> {
   560 
   559     public:
   561     typedef typename Source::
   560       typedef typename Graph::template NodeMap<_Value> Parent; 
   562     template NodeMap<typename Target::Node> NodeRefMap;
   561       typedef typename Parent::Value Value;
   563     
   562 
   564     typedef typename Source::
   563       Map(const Graph& _graph) : Parent(_graph) {}
   565     template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;
   564       Map(const Graph& _graph, const Value& _value) 
   566 
   565 	: Parent(_graph, _value) {}
   567   private:
       
   568 
       
   569     struct EdgeRefMap {
       
   570       EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}
       
   571       typedef typename Source::Edge Key;
       
   572       typedef typename Target::Edge Value;
       
   573 
       
   574       Value operator[](const Key& key) {
       
   575 	return gc.target.direct(gc.undirEdgeRef[key], 
       
   576 				gc.target.direction(key));
       
   577       }
       
   578       
       
   579       UndirGraphCopy& gc;
   566     };
   580     };
   567 
   581     
       
   582   public:
       
   583 
       
   584     /// \brief Constructor for the UndirGraphCopy.
       
   585     ///
       
   586     /// It copies the content of the \c _source graph into the
       
   587     /// \c _target graph. It creates also two references, one beetween
       
   588     /// the two nodeset and one beetween the two edgesets.
       
   589     UndirGraphCopy(Target& _target, const Source& _source) 
       
   590       : source(_source), target(_target), 
       
   591 	nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {
       
   592       for (NodeIt it(source); it != INVALID; ++it) {
       
   593 	nodeRefMap[it] = target.addNode();
       
   594       }
       
   595       for (UndirEdgeIt it(source); it != INVALID; ++it) {
       
   596 	undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
       
   597 					nodeRefMap[source.target(it)]);
       
   598       }
       
   599     }
       
   600 
       
   601     /// \brief Copies the node references into the given map.
       
   602     ///
       
   603     /// Copies the node references into the given map.
       
   604     template <typename NodeRef>
       
   605     const UndirGraphCopy& nodeRef(NodeRef& map) const {
       
   606       for (NodeIt it(source); it != INVALID; ++it) {
       
   607 	map.set(it, nodeRefMap[it]);
       
   608       }
       
   609       return *this;
       
   610     }
       
   611 
       
   612     /// \brief Reverse and copies the node references into the given map.
       
   613     ///
       
   614     /// Reverse and copies the node references into the given map.
       
   615     template <typename NodeRef>
       
   616     const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {
       
   617       for (NodeIt it(source); it != INVALID; ++it) {
       
   618 	map.set(nodeRefMap[it], it);
       
   619       }
       
   620       return *this;
       
   621     }
       
   622 
       
   623     /// \brief Copies the edge references into the given map.
       
   624     ///
       
   625     /// Copies the edge references into the given map.
       
   626     template <typename EdgeRef>
       
   627     const UndirGraphCopy& edgeRef(EdgeRef& map) const {
       
   628       for (EdgeIt it(source); it != INVALID; ++it) {
       
   629 	map.set(edgeRefMap[it], it);
       
   630       }
       
   631       return *this;
       
   632     }
       
   633 
       
   634     /// \brief Reverse and copies the undirected edge references into the 
       
   635     /// given map.
       
   636     ///
       
   637     /// Reverse and copies the undirected edge references into the given map.
       
   638     template <typename EdgeRef>
       
   639     const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {
       
   640       for (EdgeIt it(source); it != INVALID; ++it) {
       
   641 	map.set(it, edgeRefMap[it]);
       
   642       }
       
   643       return *this;
       
   644     }
       
   645 
       
   646     /// \brief Copies the undirected edge references into the given map.
       
   647     ///
       
   648     /// Copies the undirected edge references into the given map.
       
   649     template <typename EdgeRef>
       
   650     const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {
       
   651       for (UndirEdgeIt it(source); it != INVALID; ++it) {
       
   652 	map.set(it, undirEdgeRefMap[it]);
       
   653       }
       
   654       return *this;
       
   655     }
       
   656 
       
   657     /// \brief Reverse and copies the undirected edge references into the 
       
   658     /// given map.
       
   659     ///
       
   660     /// Reverse and copies the undirected edge references into the given map.
       
   661     template <typename EdgeRef>
       
   662     const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {
       
   663       for (UndirEdgeIt it(source); it != INVALID; ++it) {
       
   664 	map.set(undirEdgeRefMap[it], it);
       
   665       }
       
   666       return *this;
       
   667     }
       
   668 
       
   669     /// \brief Make copy of the given map.
       
   670     ///
       
   671     /// Makes copy of the given map for the newly created graph. 
       
   672     /// The new map's key type is the target graph's node type,
       
   673     /// and the copied map's key type is the source graph's node
       
   674     /// type.  
       
   675     template <typename TargetMap, typename SourceMap>
       
   676     const UndirGraphCopy& nodeMap(TargetMap& tMap, 
       
   677 				  const SourceMap& sMap) const {
       
   678       copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
       
   679       return *this;
       
   680     }
       
   681 
       
   682     /// \brief Make copy of the given map.
       
   683     ///
       
   684     /// Makes copy of the given map for the newly created graph. 
       
   685     /// The new map's key type is the target graph's edge type,
       
   686     /// and the copied map's key type is the source graph's edge
       
   687     /// type.  
       
   688     template <typename TargetMap, typename SourceMap>
       
   689     const UndirGraphCopy& edgeMap(TargetMap& tMap, 
       
   690 				  const SourceMap& sMap) const {
       
   691       copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
       
   692       return *this;
       
   693     }
       
   694 
       
   695     /// \brief Make copy of the given map.
       
   696     ///
       
   697     /// Makes copy of the given map for the newly created graph. 
       
   698     /// The new map's key type is the target graph's edge type,
       
   699     /// and the copied map's key type is the source graph's edge
       
   700     /// type.  
       
   701     template <typename TargetMap, typename SourceMap>
       
   702     const UndirGraphCopy& undirEdgeMap(TargetMap& tMap, 
       
   703 				  const SourceMap& sMap) const {
       
   704       copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);
       
   705       return *this;
       
   706     }
       
   707 
       
   708     /// \brief Gives back the stored node references.
       
   709     ///
       
   710     /// Gives back the stored node references.
       
   711     const NodeRefMap& nodeRef() const {
       
   712       return nodeRefMap;
       
   713     }
       
   714 
       
   715     /// \brief Gives back the stored edge references.
       
   716     ///
       
   717     /// Gives back the stored edge references.
       
   718     const EdgeRefMap& edgeRef() const {
       
   719       return edgeRefMap;
       
   720     }
       
   721 
       
   722     /// \brief Gives back the stored undir edge references.
       
   723     ///
       
   724     /// Gives back the stored undir edge references.
       
   725     const UndirEdgeRefMap& undirEdgeRef() const {
       
   726       return undirEdgeRefMap;
       
   727     }
       
   728 
       
   729     void run() {}
       
   730 
       
   731   private:
       
   732     
       
   733     const Source& source;
       
   734     Target& target;
       
   735 
       
   736     NodeRefMap nodeRefMap;
       
   737     EdgeRefMap edgeRefMap;
       
   738     UndirEdgeRefMap undirEdgeRefMap;
   568   };
   739   };
   569 
   740 
   570   template <typename _Graph>
   741   /// \brief Copy a graph to an other graph.
   571   class ItemSetTraits<_Graph, typename _Graph::Edge> {
   742   ///
   572   public:
   743   /// Copy a graph to an other graph.
   573     
   744   /// The usage of the function:
   574     typedef _Graph Graph;
   745   /// 
   575 
   746   /// \code
   576     typedef typename Graph::Edge Item;
   747   /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
   577     typedef typename Graph::EdgeIt ItemIt;
   748   /// \endcode
   578 
   749   /// 
   579     template <typename _Value>
   750   /// After the copy the \c nr map will contain the mapping from the
   580     class Map : public Graph::template EdgeMap<_Value> {
   751   /// source graph's nodes to the target graph's nodes and the \c ecr will
   581     public:
   752   /// contain the mapping from the target graph's edges to the source's
   582       typedef typename Graph::template EdgeMap<_Value> Parent; 
   753   /// edges.
   583       typedef typename Parent::Value Value;
   754   template <typename Target, typename Source>
   584 
   755   UndirGraphCopy<Target, Source> 
   585       Map(const Graph& _graph) : Parent(_graph) {}
   756   copyUndirGraph(Target& target, const Source& source) {
   586       Map(const Graph& _graph, const Value& _value) 
   757     return UndirGraphCopy<Target, Source>(target, source);
   587 	: Parent(_graph, _value) {}
   758   }
   588     };
   759 
   589 
       
   590   };
       
   591 
       
   592   template <typename _Graph>
       
   593   class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
       
   594   public:
       
   595     
       
   596     typedef _Graph Graph;
       
   597 
       
   598     typedef typename Graph::UndirEdge Item;
       
   599     typedef typename Graph::UndirEdgeIt ItemIt;
       
   600 
       
   601     template <typename _Value>
       
   602     class Map : public Graph::template UndirEdgeMap<_Value> {
       
   603     public:
       
   604       typedef typename Graph::template UndirEdgeMap<_Value> Parent; 
       
   605       typedef typename Parent::Value Value;
       
   606 
       
   607       Map(const Graph& _graph) : Parent(_graph) {}
       
   608       Map(const Graph& _graph, const Value& _value) 
       
   609 	: Parent(_graph, _value) {}
       
   610     };
       
   611 
       
   612   };
       
   613 
   760 
   614   /// @}
   761   /// @}
   615 
   762 
   616   /// \addtogroup graph_maps
   763   /// \addtogroup graph_maps
   617   /// @{
   764   /// @{
   618 
       
   619   template <typename Map, typename Enable = void>
       
   620   struct ReferenceMapTraits {
       
   621     typedef typename Map::Value Value;
       
   622     typedef typename Map::Value& Reference;
       
   623     typedef const typename Map::Value& ConstReference;
       
   624     typedef typename Map::Value* Pointer;
       
   625     typedef const typename Map::Value* ConstPointer;
       
   626   };
       
   627 
       
   628   template <typename Map>
       
   629   struct ReferenceMapTraits<
       
   630     Map, 
       
   631     typename enable_if<typename Map::FullTypeTag, void>::type
       
   632   > {
       
   633     typedef typename Map::Value Value;
       
   634     typedef typename Map::Reference Reference;
       
   635     typedef typename Map::ConstReference ConstReference;
       
   636     typedef typename Map::Pointer Pointer;
       
   637     typedef typename Map::ConstPointer ConstPointer;
       
   638   };
       
   639 
   765 
   640   /// Provides an immutable and unique id for each item in the graph.
   766   /// Provides an immutable and unique id for each item in the graph.
   641 
   767 
   642   /// The IdMap class provides a unique and immutable id for each item of the
   768   /// The IdMap class provides a unique and immutable id for each item of the
   643   /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
   769   /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
   752     }
   878     }
   753 
   879 
   754     /// \brief The getter function of the map.
   880     /// \brief The getter function of the map.
   755     ///
   881     ///
   756     /// It gives back the value associated with the key.
   882     /// It gives back the value associated with the key.
   757     const Value operator[](const Key& key) const {
   883     Value operator[](const Key& key) const {
   758       return Map::operator[](key);
   884       return Map::operator[](key);
   759     }
   885     }
   760 
   886 
   761   protected:
   887   protected:
   762 
   888 
  1190   PotentialDifferenceMap<Graph, NodeMap> 
  1316   PotentialDifferenceMap<Graph, NodeMap> 
  1191   potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
  1317   potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
  1192     return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
  1318     return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
  1193   }
  1319   }
  1194 
  1320 
  1195   /// \brief Container for store values for each ordered pair of nodes
       
  1196   ///
       
  1197   /// Container for store values for each ordered pair of nodes.
       
  1198   template <typename _Graph, typename _Value>
       
  1199   class NodeMatrixMap 
       
  1200     : protected AlterationNotifier<typename _Graph::Node>::ObserverBase {
       
  1201   public:
       
  1202     typedef _Graph Graph;
       
  1203     typedef typename Graph::Node Node;
       
  1204     typedef Node Key;
       
  1205     typedef _Value Value;
       
  1206 
       
  1207     /// \brief Creates a node matrix for the given graph
       
  1208     ///
       
  1209     /// Creates a node matrix for the given graph.
       
  1210     NodeMatrixMap(const Graph& _graph) 
       
  1211       : graph(_graph), values(size(_graph.maxId(Node()) + 1)) {}
       
  1212 
       
  1213     /// \brief Creates a node matrix for the given graph
       
  1214     ///
       
  1215     /// Creates a node matrix for the given graph and assigns each
       
  1216     /// initial value to the given parameter.
       
  1217     NodeMatrixMap(const Graph& _graph, const Value& _val) 
       
  1218       : graph(_graph), values(size(_graph.maxId(Node()) + 1), _val) {}
       
  1219 
       
  1220     /// \brief Gives back the value assigned to the \c left - \c right
       
  1221     /// ordered pair.
       
  1222     ///
       
  1223     /// Gives back the value assigned to the \c left - \c right ordered pair.
       
  1224     const Value& operator()(const Node& left, const Node& right) const {
       
  1225       return values[index(graph.id(left), graph.id(right))];
       
  1226     }
       
  1227     
       
  1228     /// \brief Gives back the value assigned to the \c left - \c right
       
  1229     /// ordered pair.
       
  1230     ///
       
  1231     /// Gives back the value assigned to the \c left - \c right ordered pair.
       
  1232     Value& operator()(const Node& left, const Node& right) {
       
  1233       return values[index(graph.id(left), graph.id(right))];
       
  1234     }
       
  1235 
       
  1236     /// \brief Setter function for the matrix map.
       
  1237     ///
       
  1238     /// Setter function for the matrix map.
       
  1239     void set(const Node& left, const Node& right, const Value& val) {
       
  1240       values[index(graph.id(left), graph.id(right))] = val;
       
  1241     }
       
  1242 
       
  1243     /// \brief Map for the coloumn view of the matrix
       
  1244     ///
       
  1245     /// Map for the coloumn view of the matrix.
       
  1246     class ColMap : public MapBase<Node, Value> {
       
  1247       friend class NodeMatrixMap;
       
  1248     private:
       
  1249       ColMap(NodeMatrixMap& _matrix, Node _col) 
       
  1250 	: matrix(_matrix), col(_col) {}
       
  1251 
       
  1252     public:
       
  1253       /// \brief Subscription operator
       
  1254       ///
       
  1255       /// Subscription operator.
       
  1256       Value& operator[](Node row) {
       
  1257 	return matrix(col, row);
       
  1258       }
       
  1259 
       
  1260       /// \brief Setter function
       
  1261       ///
       
  1262       /// Setter function.
       
  1263       void set(Node row, const Value& val) {
       
  1264 	matrix.set(col, row, val);
       
  1265       }
       
  1266       
       
  1267       /// \brief Subscription operator
       
  1268       ///
       
  1269       /// Subscription operator.
       
  1270       const Value& operator[](Node row) const {
       
  1271 	return matrix(col, row);
       
  1272       }
       
  1273 
       
  1274     private:
       
  1275       NodeMatrixMap& matrix;
       
  1276       Node col;
       
  1277     };
       
  1278 
       
  1279     /// \brief Map for the const coloumn view of the matrix
       
  1280     ///
       
  1281     /// Map for the const coloumn view of the matrix.
       
  1282     class ConstColMap : public MapBase<Node, Value> {
       
  1283       friend class NodeMatrixMap;
       
  1284     private:
       
  1285       ConstColMap(const NodeMatrixMap& _matrix, Node _col) 
       
  1286 	: matrix(_matrix), col(_col) {}
       
  1287       
       
  1288     public:
       
  1289       /// \brief Subscription operator
       
  1290       ///
       
  1291       /// Subscription operator.
       
  1292       const Value& operator[](Node row) const {
       
  1293 	return matrix(col, row);
       
  1294       }
       
  1295       
       
  1296     private:
       
  1297       const NodeMatrixMap& matrix;
       
  1298       Node col;
       
  1299     };
       
  1300 
       
  1301     /// \brief Map for the row view of the matrix
       
  1302     ///
       
  1303     /// Map for the row view of the matrix.
       
  1304     class RowMap : public MapBase<Node, Value> {
       
  1305     public:
       
  1306       friend class NodeMatrixMap;
       
  1307     private:
       
  1308       RowMap(NodeMatrixMap& _matrix, Node _row) 
       
  1309 	: matrix(_matrix), row(_row) {}
       
  1310       
       
  1311     public:
       
  1312       /// \brief Subscription operator
       
  1313       ///
       
  1314       /// Subscription operator.
       
  1315       Value& operator[](Node col) {
       
  1316 	return matrix(col, row);
       
  1317       }
       
  1318 
       
  1319       /// \brief Setter function
       
  1320       ///
       
  1321       /// Setter function.
       
  1322       void set(Node col, const Value& val) {
       
  1323 	matrix.set(col, row, val);
       
  1324       }
       
  1325       
       
  1326       /// \brief Subscription operator
       
  1327       ///
       
  1328       /// Subscription operator.
       
  1329       const Value& operator[](Node col) const {
       
  1330 	return matrix(col, row);
       
  1331       }
       
  1332 
       
  1333     private:
       
  1334       NodeMatrixMap& matrix;
       
  1335       Node row;
       
  1336     };
       
  1337 
       
  1338     /// \brief Map for the const row view of the matrix
       
  1339     ///
       
  1340     /// Map for the row const view of the matrix.
       
  1341     class ConstRowMap : public MapBase<Node, Value> {
       
  1342     public:
       
  1343       friend class NodeMatrixMap;
       
  1344     private:
       
  1345       ConstRowMap(const NodeMatrixMap& _matrix, Node _row) 
       
  1346 	: matrix(_matrix), row(_row) {}
       
  1347       
       
  1348     public:
       
  1349       /// \brief Subscription operator
       
  1350       ///
       
  1351       /// Subscription operator.
       
  1352       const Value& operator[](Node col) const {
       
  1353 	return matrix(col, row);
       
  1354       }
       
  1355       
       
  1356     private:
       
  1357       const NodeMatrixMap& matrix;
       
  1358       Node row;
       
  1359     };
       
  1360 
       
  1361     /// \brief Gives back the column view for the given node
       
  1362     ///
       
  1363     /// Gives back the column view for the given node
       
  1364     ConstColMap operator[](Node col) const { return ConstColMap(*this, col); }
       
  1365     /// \brief Gives back the column view for the given node
       
  1366     ///
       
  1367     /// Gives back the column view for the given node
       
  1368     ColMap operator[](Node col) { return ColMap(*this, col); }
       
  1369 
       
  1370     /// \brief Gives back the column view for the given node
       
  1371     ///
       
  1372     /// Gives back the column view for the given node
       
  1373     ConstColMap colMap(Node col) const { return ConstColMap(*this, col); }
       
  1374     /// \brief Gives back the column view for the given node
       
  1375     ///
       
  1376     /// Gives back the column view for the given node
       
  1377     ColMap colMap(Node col) { return ColMap(*this, col); }
       
  1378 
       
  1379     /// \brief Gives back the row view for the given node
       
  1380     ///
       
  1381     /// Gives back the row view for the given node
       
  1382     ConstRowMap rowMap(Node row) const { return ConstRowMap(*this, row); }
       
  1383     /// \brief Gives back the row view for the given node
       
  1384     ///
       
  1385     /// Gives back the row view for the given node
       
  1386     RowMap rowMap(Node row) { return RowMap(*this, row); }
       
  1387 
       
  1388   protected:
       
  1389 
       
  1390     static int index(int i, int j) {
       
  1391       if (i < j) {
       
  1392 	return j * j + i;
       
  1393       } else {
       
  1394 	return i * i + i + j;
       
  1395       }
       
  1396     }
       
  1397 
       
  1398     static int size(int s) {
       
  1399       return s * s;
       
  1400     }
       
  1401 
       
  1402     void add(const Node& node) {
       
  1403       if (size(graph.id(node) + 1) >= (int)values.size()) {
       
  1404 	values.resize(size(graph.id(node) + 1));	
       
  1405       }
       
  1406     }
       
  1407 
       
  1408     void erase(const Node&) {}
       
  1409 
       
  1410     void build() {
       
  1411       values.resize(size(graph.maxId(Node()) + 1));
       
  1412     }
       
  1413 
       
  1414     void clear() {
       
  1415       values.clear();
       
  1416     }   
       
  1417     
       
  1418   private:
       
  1419     const Graph& graph;
       
  1420     std::vector<Value> values;
       
  1421   };
       
  1422 
       
  1423   /// \brief Map of the node in-degrees.
  1321   /// \brief Map of the node in-degrees.
  1424   ///
  1322   ///
  1425   /// This map returns the in-degree of a node. Once it is constructed,
  1323   /// This map returns the in-degree of a node. Once it is constructed,
  1426   /// the degrees are stored in a standard NodeMap, so each query is done
  1324   /// the degrees are stored in a standard NodeMap, so each query is done
  1427   /// in constant time. On the other hand, the values are updated automatically
  1325   /// in constant time. On the other hand, the values are updated automatically
  1428   /// whenever the graph changes.
  1326   /// whenever the graph changes.
  1429   ///
       
  1430   /// \warning Besides addNode() and addEdge(), a graph structure may provide
       
  1431   /// alternative ways to mogify the graph. The correct behavior of InDegMap
       
  1432   /// is not guarantied if these additional featureas are used. For example
       
  1433   /// the funstions \ref ListGraph::changeSource() "changeSource()",
       
  1434   /// \ref ListGraph::changeTarget() "changeTarget()" and
       
  1435   /// \ref ListGraph::reverseEdge() "reverseEdge()"
       
  1436   /// of \ref ListGraph will \e not update the degree values correctly.
       
  1437   ///
  1327   ///
  1438   /// \sa OutDegMap
  1328   /// \sa OutDegMap
  1439 
  1329 
  1440   template <typename _Graph>
  1330   template <typename _Graph>
  1441   class InDegMap  
  1331   class InDegMap  
  1499 
  1389 
  1500     virtual void erase(const Edge& edge) {
  1390     virtual void erase(const Edge& edge) {
  1501       --deg[graph.target(edge)];
  1391       --deg[graph.target(edge)];
  1502     }
  1392     }
  1503 
  1393 
       
  1394     virtual void signalChange(const Edge& edge) {
       
  1395       erase(edge);
       
  1396     }
       
  1397 
       
  1398     virtual void commitChange(const Edge& edge) {
       
  1399       add(edge);
       
  1400     }
  1504 
  1401 
  1505     virtual void build() {
  1402     virtual void build() {
  1506       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1403       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1507 	deg[it] = countInEdges(graph, it);
  1404 	deg[it] = countInEdges(graph, it);
  1508       }      
  1405       }      
  1523   ///
  1420   ///
  1524   /// This map returns the out-degree of a node. Once it is constructed,
  1421   /// This map returns the out-degree of a node. Once it is constructed,
  1525   /// the degrees are stored in a standard NodeMap, so each query is done
  1422   /// the degrees are stored in a standard NodeMap, so each query is done
  1526   /// in constant time. On the other hand, the values are updated automatically
  1423   /// in constant time. On the other hand, the values are updated automatically
  1527   /// whenever the graph changes.
  1424   /// whenever the graph changes.
  1528   ///
       
  1529   /// \warning Besides addNode() and addEdge(), a graph structure may provide
       
  1530   /// alternative ways to mogify the graph. The correct behavior of OutDegMap
       
  1531   /// is not guarantied if these additional featureas are used. For example
       
  1532   /// the funstions \ref ListGraph::changeSource() "changeSource()",
       
  1533   /// \ref ListGraph::changeTarget() "changeTarget()" and
       
  1534   /// \ref ListGraph::reverseEdge() "reverseEdge()"
       
  1535   /// of \ref ListGraph will \e not update the degree values correctly.
       
  1536   ///
  1425   ///
  1537   /// \sa InDegMap
  1426   /// \sa InDegMap
  1538 
  1427 
  1539   template <typename _Graph>
  1428   template <typename _Graph>
  1540   class OutDegMap  
  1429   class OutDegMap  
  1598 
  1487 
  1599     virtual void erase(const Edge& edge) {
  1488     virtual void erase(const Edge& edge) {
  1600       --deg[graph.source(edge)];
  1489       --deg[graph.source(edge)];
  1601     }
  1490     }
  1602 
  1491 
       
  1492     virtual void signalChange(const Edge& edge) {
       
  1493       erase(edge);
       
  1494     }
       
  1495 
       
  1496     virtual void commitChange(const Edge& edge) {
       
  1497       add(edge);
       
  1498     }
       
  1499 
  1603 
  1500 
  1604     virtual void build() {
  1501     virtual void build() {
  1605       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1502       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
  1606 	deg[it] = countOutEdges(graph, it);
  1503 	deg[it] = countOutEdges(graph, it);
  1607       }      
  1504       }      
  1616     
  1513     
  1617     const _Graph& graph;
  1514     const _Graph& graph;
  1618     AutoNodeMap deg;
  1515     AutoNodeMap deg;
  1619   };
  1516   };
  1620 
  1517 
  1621   // Indicators for the tags
       
  1622 
       
  1623   template <typename Graph, typename Enable = void>
       
  1624   struct NodeNumTagIndicator {
       
  1625     static const bool value = false;
       
  1626   };
       
  1627 
       
  1628   template <typename Graph>
       
  1629   struct NodeNumTagIndicator<
       
  1630     Graph, 
       
  1631     typename enable_if<typename Graph::NodeNumTag, void>::type
       
  1632   > {
       
  1633     static const bool value = true;
       
  1634   };
       
  1635 
       
  1636   template <typename Graph, typename Enable = void>
       
  1637   struct EdgeNumTagIndicator {
       
  1638     static const bool value = false;
       
  1639   };
       
  1640 
       
  1641   template <typename Graph>
       
  1642   struct EdgeNumTagIndicator<
       
  1643     Graph, 
       
  1644     typename enable_if<typename Graph::EdgeNumTag, void>::type
       
  1645   > {
       
  1646     static const bool value = true;
       
  1647   };
       
  1648 
       
  1649   template <typename Graph, typename Enable = void>
       
  1650   struct FindEdgeTagIndicator {
       
  1651     static const bool value = false;
       
  1652   };
       
  1653 
       
  1654   template <typename Graph>
       
  1655   struct FindEdgeTagIndicator<
       
  1656     Graph, 
       
  1657     typename enable_if<typename Graph::FindEdgeTag, void>::type
       
  1658   > {
       
  1659     static const bool value = true;
       
  1660   };
       
  1661 
       
  1662 
  1518 
  1663   /// @}
  1519   /// @}
  1664 
  1520 
  1665 } //END OF NAMESPACE LEMON
  1521 } //END OF NAMESPACE LEMON
  1666 
  1522