gtl/src/min_tree.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   min_tree.cpp
0005 //
0006 //==========================================================================
0007 // $Id: min_tree.cpp,v 1.4 2001/11/07 13:58:10 pick Exp $
0008
0009 #include <GTL/graph.h>
0010 #include <stack>
0011 #include <queue>
0012 #include <GTL/min_tree.h>
0013
0014 #ifdef __GTL_MSVCC
0015 #   ifdef _DEBUG
0016 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0017 #   error SEARCH NOT ENABLED
0018 #   endif
0019 #   define new DEBUG_NEW
0020 #   undef THIS_FILE
0021     static char THIS_FILE[] = __FILE__;
0022 #   endif   // _DEBUG
0023 #endif  // __GTL_MSVCC
0024
0025 __GTL_BEGIN_NAMESPACE
0026
0027 min_tree::min_tree () {
0028     is_set_distances = false;
0029     weight = 0;
0030 }
0031
0032 int min_tree::check (graph& g) {
0033     if (g.is_directed()) return GTL_ERROR;
0034     else if (g.number_of_nodes() < 2) return GTL_ERROR;
0035     else if (!g.is_connected()) return GTL_ERROR;
0036     else if (!is_set_distances) return GTL_ERROR;
0037     else return GTL_OK;
0038 }
0039
0040 void min_tree::set_distances (const edge_map<int>& dist) {
0041     this->dist = dist;
0042     is_set_distances = true;
0043 }
0044
0045 set<edge> min_tree::get_min_tree() {
0046     return this->tree;
0047 }
0048
0049 int min_tree::get_min_tree_length() {
0050     int sum;
0051     set<edge>::iterator tree_it;
0052
0053     sum = 0;
0054
0055     for (tree_it = tree.begin(); tree_it != tree.end(); tree_it++)
0056     sum += dist[*tree_it];
0057
0058     return sum;
0059 }
0060
0061 int min_tree::run (graph& g) {
0062     priority_queue <TSP_A_VALUE, vector<TSP_A_VALUE>, input_comp> node_distances;
0063     node::adj_edges_iterator adj_it, adj_end;
0064     set<node> tree_nodes;
0065     set<node>::iterator tree_it;
0066     edge curr;
0067     node new_node;
0068     graph::edge_iterator edge_it, edges_end;
0069     unsigned int number_of_nodes;
0070     int min_dist;
0071
0072
0073     // making out the start edge
0074
0075     edge_it = g.edges_begin();
0076     edges_end = g.edges_end();
0077
0078     curr = *edge_it;
0079     min_dist = dist[*edge_it];
0080
0081     for (; edge_it != edges_end; edge_it++) {
0082     if (dist[*edge_it] < min_dist) {
0083         curr = *edge_it;
0084         min_dist = dist[*edge_it];
0085     }
0086     }
0087
0088     tree.insert(curr);
0089
0090     tree_nodes.insert(curr.source());
0091     tree_nodes.insert(curr.target());
0092
0093
0094     for (tree_it = tree_nodes.begin(); tree_it != tree_nodes.end(); tree_it++) {
0095     adj_it = (*tree_it).adj_edges_begin();
0096     adj_end = (*tree_it).adj_edges_end();
0097
0098     for (; adj_it != adj_end; adj_it++) {
0099         node_distances.push(TSP_A_VALUE(dist[*adj_it], adj_it));
0100     }
0101     }
0102
0103     // create the min_tree
0104
0105     number_of_nodes = g.number_of_nodes();
0106
0107     while(tree.size() < number_of_nodes - 1) {
0108     curr = *((node_distances.top()).second);
0109
0110     node_distances.pop();
0111
0112     if (tree_nodes.find(curr.source()) != tree_nodes.end() &&
0113         tree_nodes.find(curr.target()) != tree_nodes.end()) {
0114     } else {
0115         tree.insert(curr);
0116         weight += dist[curr];
0117
0118         if (tree_nodes.find(curr.source()) != tree_nodes.end()) {
0119         new_node = curr.target();
0120         } else {
0121         new_node = curr.source();
0122         }
0123
0124         tree_nodes.insert(new_node);
0125
0126         adj_it = new_node.adj_edges_begin();
0127         adj_end = new_node.adj_edges_end();
0128
0129         for (; adj_it != adj_end; adj_it++) {
0130         node_distances.push(TSP_A_VALUE(dist[*adj_it], adj_it));
0131         }
0132     }
0133     }
0134
0135     return GTL_OK;
0136 }
0137
0138 void min_tree::reset() {
0139     tree.erase (tree.begin(), tree.end());
0140     weight = 0;
0141 }
0142
0143 __GTL_END_NAMESPACE
0144
0145
0146
0147
0148
0149
0150
0151
0152