equal
deleted
inserted
replaced
352 /// |
352 /// |
353 ///\sa findArc() |
353 ///\sa findArc() |
354 ///\sa ArcLookUp |
354 ///\sa ArcLookUp |
355 ///\sa AllArcLookUp |
355 ///\sa AllArcLookUp |
356 ///\sa DynArcLookUp |
356 ///\sa DynArcLookUp |
357 /// |
|
358 /// \author Balazs Dezso |
|
359 template <typename _Graph> |
357 template <typename _Graph> |
360 class ConArcIt : public _Graph::Arc { |
358 class ConArcIt : public _Graph::Arc { |
361 public: |
359 public: |
362 |
360 |
363 typedef _Graph Graph; |
361 typedef _Graph Graph; |
476 /// ... |
474 /// ... |
477 /// } |
475 /// } |
478 ///\endcode |
476 ///\endcode |
479 /// |
477 /// |
480 ///\sa findEdge() |
478 ///\sa findEdge() |
481 /// |
|
482 /// \author Balazs Dezso |
|
483 template <typename _Graph> |
479 template <typename _Graph> |
484 class ConEdgeIt : public _Graph::Edge { |
480 class ConEdgeIt : public _Graph::Edge { |
485 public: |
481 public: |
486 |
482 |
487 typedef _Graph Graph; |
483 typedef _Graph Graph; |
1240 /// in the inverse map. |
1236 /// in the inverse map. |
1241 /// |
1237 /// |
1242 /// The values of the map can be accessed |
1238 /// The values of the map can be accessed |
1243 /// with stl compatible forward iterator. |
1239 /// with stl compatible forward iterator. |
1244 /// |
1240 /// |
1245 /// \param _Graph The graph type. |
1241 /// \tparam _Graph The graph type. |
1246 /// \param _Item The item type of the graph. |
1242 /// \tparam _Item The item type of the graph. |
1247 /// \param _Value The value type of the map. |
1243 /// \tparam _Value The value type of the map. |
1248 /// |
1244 /// |
1249 /// \see IterableValueMap |
1245 /// \see IterableValueMap |
1250 template <typename _Graph, typename _Item, typename _Value> |
1246 template <typename _Graph, typename _Item, typename _Value> |
1251 class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> { |
1247 class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> { |
1252 private: |
1248 private: |
1445 /// integers between 0 and \c n-1, where \c n is the number of the items of |
1441 /// integers between 0 and \c n-1, where \c n is the number of the items of |
1446 /// this type (e.g. nodes) (so the id of a node can change if you delete an |
1442 /// this type (e.g. nodes) (so the id of a node can change if you delete an |
1447 /// other node, i.e. this id is mutable). </ul> This map can be inverted |
1443 /// other node, i.e. this id is mutable). </ul> This map can be inverted |
1448 /// with its member class \c InverseMap, or with the \c operator() member. |
1444 /// with its member class \c InverseMap, or with the \c operator() member. |
1449 /// |
1445 /// |
1450 /// \param _Graph The graph class the \c DescriptorMap belongs to. |
1446 /// \tparam _Graph The graph class the \c DescriptorMap belongs to. |
1451 /// \param _Item The Item is the Key of the Map. It may be Node, Arc or |
1447 /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or |
1452 /// Edge. |
1448 /// Edge. |
1453 template <typename _Graph, typename _Item> |
1449 template <typename _Graph, typename _Item> |
1454 class DescriptorMap : protected DefaultMap<_Graph, _Item, int> { |
1450 class DescriptorMap : protected DefaultMap<_Graph, _Item, int> { |
1455 |
1451 |
1456 typedef _Item Item; |
1452 typedef _Item Item; |
1635 |
1631 |
1636 /// \brief Returns the source of the given arc. |
1632 /// \brief Returns the source of the given arc. |
1637 /// |
1633 /// |
1638 /// The SourceMap gives back the source Node of the given arc. |
1634 /// The SourceMap gives back the source Node of the given arc. |
1639 /// \see TargetMap |
1635 /// \see TargetMap |
1640 /// \author Balazs Dezso |
|
1641 template <typename Digraph> |
1636 template <typename Digraph> |
1642 class SourceMap { |
1637 class SourceMap { |
1643 public: |
1638 public: |
1644 |
1639 |
1645 typedef typename Digraph::Node Value; |
1640 typedef typename Digraph::Node Value; |
1675 |
1670 |
1676 /// \brief Returns the target of the given arc. |
1671 /// \brief Returns the target of the given arc. |
1677 /// |
1672 /// |
1678 /// The TargetMap gives back the target Node of the given arc. |
1673 /// The TargetMap gives back the target Node of the given arc. |
1679 /// \see SourceMap |
1674 /// \see SourceMap |
1680 /// \author Balazs Dezso |
|
1681 template <typename Digraph> |
1675 template <typename Digraph> |
1682 class TargetMap { |
1676 class TargetMap { |
1683 public: |
1677 public: |
1684 |
1678 |
1685 typedef typename Digraph::Node Value; |
1679 typedef typename Digraph::Node Value; |
1715 |
1709 |
1716 /// \brief Returns the "forward" directed arc view of an edge. |
1710 /// \brief Returns the "forward" directed arc view of an edge. |
1717 /// |
1711 /// |
1718 /// Returns the "forward" directed arc view of an edge. |
1712 /// Returns the "forward" directed arc view of an edge. |
1719 /// \see BackwardMap |
1713 /// \see BackwardMap |
1720 /// \author Balazs Dezso |
|
1721 template <typename Graph> |
1714 template <typename Graph> |
1722 class ForwardMap { |
1715 class ForwardMap { |
1723 public: |
1716 public: |
1724 |
1717 |
1725 typedef typename Graph::Arc Value; |
1718 typedef typename Graph::Arc Value; |
1755 |
1748 |
1756 /// \brief Returns the "backward" directed arc view of an edge. |
1749 /// \brief Returns the "backward" directed arc view of an edge. |
1757 /// |
1750 /// |
1758 /// Returns the "backward" directed arc view of an edge. |
1751 /// Returns the "backward" directed arc view of an edge. |
1759 /// \see ForwardMap |
1752 /// \see ForwardMap |
1760 /// \author Balazs Dezso |
|
1761 template <typename Graph> |
1753 template <typename Graph> |
1762 class BackwardMap { |
1754 class BackwardMap { |
1763 public: |
1755 public: |
1764 |
1756 |
1765 typedef typename Graph::Arc Value; |
1757 typedef typename Graph::Arc Value; |
2094 ///and Tarjan's Splay tree for guarantee the logarithmic amortized |
2086 ///and Tarjan's Splay tree for guarantee the logarithmic amortized |
2095 ///time bound for arc lookups. This class also guarantees the |
2087 ///time bound for arc lookups. This class also guarantees the |
2096 ///optimal time bound in a constant factor for any distribution of |
2088 ///optimal time bound in a constant factor for any distribution of |
2097 ///queries. |
2089 ///queries. |
2098 /// |
2090 /// |
2099 ///\param G The type of the underlying digraph. |
2091 ///\tparam G The type of the underlying digraph. |
2100 /// |
2092 /// |
2101 ///\sa ArcLookUp |
2093 ///\sa ArcLookUp |
2102 ///\sa AllArcLookUp |
2094 ///\sa AllArcLookUp |
2103 template<class G> |
2095 template<class G> |
2104 class DynArcLookUp |
2096 class DynArcLookUp |
2535 ///\warning This class is static, so you should refresh() (or at least |
2527 ///\warning This class is static, so you should refresh() (or at least |
2536 ///refresh(Node)) this data structure |
2528 ///refresh(Node)) this data structure |
2537 ///whenever the digraph changes. This is a time consuming (superlinearly |
2529 ///whenever the digraph changes. This is a time consuming (superlinearly |
2538 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs). |
2530 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs). |
2539 /// |
2531 /// |
2540 ///\param G The type of the underlying digraph. |
2532 ///\tparam G The type of the underlying digraph. |
2541 /// |
2533 /// |
2542 ///\sa DynArcLookUp |
2534 ///\sa DynArcLookUp |
2543 ///\sa AllArcLookUp |
2535 ///\sa AllArcLookUp |
2544 template<class G> |
2536 template<class G> |
2545 class ArcLookUp |
2537 class ArcLookUp |
2648 ///\warning This class is static, so you should refresh() (or at least |
2640 ///\warning This class is static, so you should refresh() (or at least |
2649 ///refresh(Node)) this data structure |
2641 ///refresh(Node)) this data structure |
2650 ///whenever the digraph changes. This is a time consuming (superlinearly |
2642 ///whenever the digraph changes. This is a time consuming (superlinearly |
2651 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs). |
2643 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs). |
2652 /// |
2644 /// |
2653 ///\param G The type of the underlying digraph. |
2645 ///\tparam G The type of the underlying digraph. |
2654 /// |
2646 /// |
2655 ///\sa DynArcLookUp |
2647 ///\sa DynArcLookUp |
2656 ///\sa ArcLookUp |
2648 ///\sa ArcLookUp |
2657 template<class G> |
2649 template<class G> |
2658 class AllArcLookUp : public ArcLookUp<G> |
2650 class AllArcLookUp : public ArcLookUp<G> |