equal
deleted
inserted
replaced
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library. |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2009 |
5 * Copyright (C) 2003-2011 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
1816 /// @{ |
1816 /// @{ |
1817 |
1817 |
1818 /// \brief Provides an immutable and unique id for each item in a graph. |
1818 /// \brief Provides an immutable and unique id for each item in a graph. |
1819 /// |
1819 /// |
1820 /// IdMap provides a unique and immutable id for each item of the |
1820 /// IdMap provides a unique and immutable id for each item of the |
1821 /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is |
1821 /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is |
1822 /// - \b unique: different items get different ids, |
1822 /// - \b unique: different items get different ids, |
1823 /// - \b immutable: the id of an item does not change (even if you |
1823 /// - \b immutable: the id of an item does not change (even if you |
1824 /// delete other nodes). |
1824 /// delete other nodes). |
1825 /// |
1825 /// |
1826 /// Using this map you get access (i.e. can read) the inner id values of |
1826 /// Using this map you get access (i.e. can read) the inner id values of |
2271 int operator[](const Item& item) const { |
2271 int operator[](const Item& item) const { |
2272 return Map::operator[](item); |
2272 return Map::operator[](item); |
2273 } |
2273 } |
2274 |
2274 |
2275 /// \brief Gives back the item belonging to a \e RangeId |
2275 /// \brief Gives back the item belonging to a \e RangeId |
2276 /// |
2276 /// |
2277 /// Gives back the item belonging to a \e RangeId. |
2277 /// Gives back the item belonging to a \e RangeId. |
2278 Item operator()(int id) const { |
2278 Item operator()(int id) const { |
2279 return _inv_map[id]; |
2279 return _inv_map[id]; |
2280 } |
2280 } |
2281 |
2281 |
2497 /// This map returns the in-degree of a node. Once it is constructed, |
2497 /// This map returns the in-degree of a node. Once it is constructed, |
2498 /// the degrees are stored in a standard \c NodeMap, so each query is done |
2498 /// the degrees are stored in a standard \c NodeMap, so each query is done |
2499 /// in constant time. On the other hand, the values are updated automatically |
2499 /// in constant time. On the other hand, the values are updated automatically |
2500 /// whenever the digraph changes. |
2500 /// whenever the digraph changes. |
2501 /// |
2501 /// |
2502 /// \warning Besides \c addNode() and \c addArc(), a digraph structure |
2502 /// \warning Besides \c addNode() and \c addArc(), a digraph structure |
2503 /// may provide alternative ways to modify the digraph. |
2503 /// may provide alternative ways to modify the digraph. |
2504 /// The correct behavior of InDegMap is not guarantied if these additional |
2504 /// The correct behavior of InDegMap is not guarantied if these additional |
2505 /// features are used. For example the functions |
2505 /// features are used. For example the functions |
2506 /// \ref ListDigraph::changeSource() "changeSource()", |
2506 /// \ref ListDigraph::changeSource() "changeSource()", |
2507 /// \ref ListDigraph::changeTarget() "changeTarget()" and |
2507 /// \ref ListDigraph::changeTarget() "changeTarget()" and |
2513 class InDegMap |
2513 class InDegMap |
2514 : protected ItemSetTraits<GR, typename GR::Arc> |
2514 : protected ItemSetTraits<GR, typename GR::Arc> |
2515 ::ItemNotifier::ObserverBase { |
2515 ::ItemNotifier::ObserverBase { |
2516 |
2516 |
2517 public: |
2517 public: |
2518 |
2518 |
2519 /// The graph type of InDegMap |
2519 /// The graph type of InDegMap |
2520 typedef GR Graph; |
2520 typedef GR Graph; |
2521 typedef GR Digraph; |
2521 typedef GR Digraph; |
2522 /// The key type |
2522 /// The key type |
2523 typedef typename Digraph::Node Key; |
2523 typedef typename Digraph::Node Key; |
2627 /// This map returns the out-degree of a node. Once it is constructed, |
2627 /// This map returns the out-degree of a node. Once it is constructed, |
2628 /// the degrees are stored in a standard \c NodeMap, so each query is done |
2628 /// the degrees are stored in a standard \c NodeMap, so each query is done |
2629 /// in constant time. On the other hand, the values are updated automatically |
2629 /// in constant time. On the other hand, the values are updated automatically |
2630 /// whenever the digraph changes. |
2630 /// whenever the digraph changes. |
2631 /// |
2631 /// |
2632 /// \warning Besides \c addNode() and \c addArc(), a digraph structure |
2632 /// \warning Besides \c addNode() and \c addArc(), a digraph structure |
2633 /// may provide alternative ways to modify the digraph. |
2633 /// may provide alternative ways to modify the digraph. |
2634 /// The correct behavior of OutDegMap is not guarantied if these additional |
2634 /// The correct behavior of OutDegMap is not guarantied if these additional |
2635 /// features are used. For example the functions |
2635 /// features are used. For example the functions |
2636 /// \ref ListDigraph::changeSource() "changeSource()", |
2636 /// \ref ListDigraph::changeSource() "changeSource()", |
2637 /// \ref ListDigraph::changeTarget() "changeTarget()" and |
2637 /// \ref ListDigraph::changeTarget() "changeTarget()" and |