include/GTL/min_tree.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   min_tree.cpp
0005 //
0006 //==========================================================================
0007 // $Id: min_tree.h,v 1.3 2001/06/21 10:55:08 chris Exp $
0008
0009 #ifndef GTL_MIN_TREE_H
0010 #define GTL_MIN_TREE_H
0011
0012 #include <GTL/GTL.h>
0013 #include <GTL/algorithm.h>
0014 #include <GTL/edge_map.h>
0015 #include <set>
0016
0017 __GTL_BEGIN_NAMESPACE
0018
0019 /**
0020  * @brief Kruskal's %algorithm for finding minimal spanning tree
0021  * of a %graph.
0022  *
0023  * @author Marcus Raitner
0024  */
0025 class min_tree: public algorithm {
0026
0027 public:
0028
0029     /**
0030      * @brief Constructor
0031      */
0032     min_tree ();
0033
0034     /**
0035      * @brief Destructor
0036      */
0037     virtual ~min_tree () {};
0038
0039     /**
0040      * @brief Checks whether %algorithm can be applied.
0041      *
0042      * The %graph must
0043      *    - be undirected
0044      *    - be connected
0045      *    - have more than 2 nodes
0046      *
0047      * Additionally the weights of the edges must have been set
0048      * in advance using min_tree::set_distances.
0049      *
0050      * @param g graph
0051      * @return algorithm::GTL_OK if %algorithm can be applied
0052      * algorithm::GTL_ERROR otherwise.
0053      */
0054     int check (graph& g);
0055
0056     int run (graph& g);
0057
0058     virtual void reset ();
0059
0060     /**
0061      * @brief Sets %edge weights.
0062      *
0063      * Setting of %edge weights must be done before calling
0064      * min_tree::check and min_tree::run.
0065      *
0066      * @param dist %edge weigths.
0067      */
0068     void set_distances (const edge_map<int>& dist);
0069
0070     /**
0071      * @brief Edges of minimal spanning tree calculated in the
0072      * last call of min_tree::run.
0073      *
0074      * @return Set of edges of representing the minimal spanning
0075      * tree
0076      */
0077     set<edge> get_min_tree();
0078
0079     /**
0080      * @brief Weight of minimal spanning tree.
0081      *
0082      * @return weight of minimal spanning tree.
0083      */
0084     int get_min_tree_length();
0085
0086 private:
0087     typedef pair<int, node::adj_edges_iterator> TSP_A_VALUE;
0088
0089     class input_comp {
0090     public:
0091     bool operator()(TSP_A_VALUE x, TSP_A_VALUE y)
0092         { return x.first > y.first;}
0093     };
0094
0095     edge_map<int> dist;
0096     int weight;
0097     set<edge> tree;
0098     bool is_set_distances;
0099 };
0100
0101 __GTL_END_NAMESPACE
0102
0103 #endif // GTL_MIN_TREE_H
0104
0105
0106
0107
0108