33 |
33 |
34 |
34 |
35 /// \brief Default traits class for MinCostArborescence class. |
35 /// \brief Default traits class for MinCostArborescence class. |
36 /// |
36 /// |
37 /// Default traits class for MinCostArborescence class. |
37 /// Default traits class for MinCostArborescence class. |
38 /// \param _Digraph Digraph type. |
38 /// \param GR Digraph type. |
39 /// \param _CostMap Type of cost map. |
39 /// \param CM Type of cost map. |
40 template <class _Digraph, class _CostMap> |
40 template <class GR, class CM> |
41 struct MinCostArborescenceDefaultTraits{ |
41 struct MinCostArborescenceDefaultTraits{ |
42 |
42 |
43 /// \brief The digraph type the algorithm runs on. |
43 /// \brief The digraph type the algorithm runs on. |
44 typedef _Digraph Digraph; |
44 typedef GR Digraph; |
45 |
45 |
46 /// \brief The type of the map that stores the arc costs. |
46 /// \brief The type of the map that stores the arc costs. |
47 /// |
47 /// |
48 /// The type of the map that stores the arc costs. |
48 /// The type of the map that stores the arc costs. |
49 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
49 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
50 typedef _CostMap CostMap; |
50 typedef CM CostMap; |
51 |
51 |
52 /// \brief The value type of the costs. |
52 /// \brief The value type of the costs. |
53 /// |
53 /// |
54 /// The value type of the costs. |
54 /// The value type of the costs. |
55 typedef typename CostMap::Value Value; |
55 typedef typename CostMap::Value Value; |
61 /// arborescence. It must meet the \ref concepts::WriteMap |
61 /// arborescence. It must meet the \ref concepts::WriteMap |
62 /// "WriteMap" concept. Initially it will be set to false on each |
62 /// "WriteMap" concept. Initially it will be set to false on each |
63 /// arc. After it will set all arborescence arcs once. |
63 /// arc. After it will set all arborescence arcs once. |
64 typedef typename Digraph::template ArcMap<bool> ArborescenceMap; |
64 typedef typename Digraph::template ArcMap<bool> ArborescenceMap; |
65 |
65 |
66 /// \brief Instantiates a ArborescenceMap. |
66 /// \brief Instantiates a \c ArborescenceMap. |
67 /// |
67 /// |
68 /// This function instantiates a \ref ArborescenceMap. |
68 /// This function instantiates a \c ArborescenceMap. |
69 /// \param digraph is the graph, to which we would like to |
69 /// \param digraph is the graph, to which we would like to |
70 /// calculate the ArborescenceMap. |
70 /// calculate the \c ArborescenceMap. |
71 static ArborescenceMap *createArborescenceMap(const Digraph &digraph){ |
71 static ArborescenceMap *createArborescenceMap(const Digraph &digraph){ |
72 return new ArborescenceMap(digraph); |
72 return new ArborescenceMap(digraph); |
73 } |
73 } |
74 |
74 |
75 /// \brief The type of the PredMap |
75 /// \brief The type of the \c PredMap |
76 /// |
76 /// |
77 /// The type of the PredMap. It is a node map with an arc value type. |
77 /// The type of the \c PredMap. It is a node map with an arc value type. |
78 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
78 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
79 |
79 |
80 /// \brief Instantiates a PredMap. |
80 /// \brief Instantiates a \c PredMap. |
81 /// |
81 /// |
82 /// This function instantiates a \ref PredMap. |
82 /// This function instantiates a \c PredMap. |
83 /// \param _digraph is the digraph, to which we would like to define the |
83 /// \param digraph The digraph to which we would like to define the |
84 /// PredMap. |
84 /// \c PredMap. |
85 static PredMap *createPredMap(const Digraph &digraph){ |
85 static PredMap *createPredMap(const Digraph &digraph){ |
86 return new PredMap(digraph); |
86 return new PredMap(digraph); |
87 } |
87 } |
88 |
88 |
89 }; |
89 }; |
96 /// %MinCostArborescence algorithm. The arborescence is a tree |
96 /// %MinCostArborescence algorithm. The arborescence is a tree |
97 /// which is directed from a given source node of the digraph. One or |
97 /// which is directed from a given source node of the digraph. One or |
98 /// more sources should be given for the algorithm and it will calculate |
98 /// more sources should be given for the algorithm and it will calculate |
99 /// the minimum cost subgraph which are union of arborescences with the |
99 /// the minimum cost subgraph which are union of arborescences with the |
100 /// given sources and spans all the nodes which are reachable from the |
100 /// given sources and spans all the nodes which are reachable from the |
101 /// sources. The time complexity of the algorithm is \f$ O(n^2+e) \f$. |
101 /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e). |
102 /// |
102 /// |
103 /// The algorithm provides also an optimal dual solution, therefore |
103 /// The algorithm provides also an optimal dual solution, therefore |
104 /// the optimality of the solution can be checked. |
104 /// the optimality of the solution can be checked. |
105 /// |
105 /// |
106 /// \param _Digraph The digraph type the algorithm runs on. The default value |
106 /// \param GR The digraph type the algorithm runs on. The default value |
107 /// is \ref ListDigraph. |
107 /// is \ref ListDigraph. |
108 /// \param _CostMap This read-only ArcMap determines the costs of the |
108 /// \param CM This read-only ArcMap determines the costs of the |
109 /// arcs. It is read once for each arc, so the map may involve in |
109 /// arcs. It is read once for each arc, so the map may involve in |
110 /// relatively time consuming process to compute the arc cost if |
110 /// relatively time consuming process to compute the arc cost if |
111 /// it is necessary. The default map type is \ref |
111 /// it is necessary. The default map type is \ref |
112 /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>". |
112 /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>". |
113 /// \param _Traits Traits class to set various data types used |
113 /// \param TR Traits class to set various data types used |
114 /// by the algorithm. The default traits class is |
114 /// by the algorithm. The default traits class is |
115 /// \ref MinCostArborescenceDefaultTraits |
115 /// \ref MinCostArborescenceDefaultTraits |
116 /// "MinCostArborescenceDefaultTraits<_Digraph, _CostMap>". See \ref |
116 /// "MinCostArborescenceDefaultTraits<GR, CM>". See \ref |
117 /// MinCostArborescenceDefaultTraits for the documentation of a |
117 /// MinCostArborescenceDefaultTraits for the documentation of a |
118 /// MinCostArborescence traits class. |
118 /// MinCostArborescence traits class. |
119 /// |
|
120 /// \author Balazs Dezso |
|
121 #ifndef DOXYGEN |
119 #ifndef DOXYGEN |
122 template <typename _Digraph = ListDigraph, |
120 template <typename GR = ListDigraph, |
123 typename _CostMap = typename _Digraph::template ArcMap<int>, |
121 typename CM = typename GR::template ArcMap<int>, |
124 typename _Traits = |
122 typename TR = |
125 MinCostArborescenceDefaultTraits<_Digraph, _CostMap> > |
123 MinCostArborescenceDefaultTraits<GR, CM> > |
126 #else |
124 #else |
127 template <typename _Digraph, typename _CostMap, typedef _Traits> |
125 template <typename GR, typename CM, typedef TR> |
128 #endif |
126 #endif |
129 class MinCostArborescence { |
127 class MinCostArborescence { |
130 public: |
128 public: |
131 |
129 |
132 /// The traits. |
130 /// The traits. |
133 typedef _Traits Traits; |
131 typedef TR Traits; |
134 /// The type of the underlying digraph. |
132 /// The type of the underlying digraph. |
135 typedef typename Traits::Digraph Digraph; |
133 typedef typename Traits::Digraph Digraph; |
136 /// The type of the map that stores the arc costs. |
134 /// The type of the map that stores the arc costs. |
137 typedef typename Traits::CostMap CostMap; |
135 typedef typename Traits::CostMap CostMap; |
138 ///The type of the costs of the arcs. |
136 ///The type of the costs of the arcs. |
438 |
436 |
439 /// @} |
437 /// @} |
440 |
438 |
441 /// \brief Constructor. |
439 /// \brief Constructor. |
442 /// |
440 /// |
443 /// \param _digraph The digraph the algorithm will run on. |
441 /// \param digraph The digraph the algorithm will run on. |
444 /// \param _cost The cost map used by the algorithm. |
442 /// \param cost The cost map used by the algorithm. |
445 MinCostArborescence(const Digraph& digraph, const CostMap& cost) |
443 MinCostArborescence(const Digraph& digraph, const CostMap& cost) |
446 : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false), |
444 : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false), |
447 _arborescence(0), local_arborescence(false), |
445 _arborescence(0), local_arborescence(false), |
448 _arc_order(0), _node_order(0), _cost_arcs(0), |
446 _arc_order(0), _node_order(0), _cost_arcs(0), |
449 _heap_cross_ref(0), _heap(0) {} |
447 _heap_cross_ref(0), _heap(0) {} |