gtl/src/bfs.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   bfs.cpp
0005 //
0006 //==========================================================================
0007 // $Id: bfs.cpp,v 1.11 2001/11/07 13:58:09 pick Exp $
0008
0009 #include <GTL/bfs.h>
0010 #include <GTL/edge_map.h>
0011
0012 #ifdef __GTL_MSVCC
0013 #   ifdef _DEBUG
0014 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0015 #   error SEARCH NOT ENABLED
0016 #   endif
0017 #   define new DEBUG_NEW
0018 #   undef THIS_FILE
0019     static char THIS_FILE[] = __FILE__;
0020 #   endif   // _DEBUG
0021 #endif  // __GTL_MSVCC
0022
0023 __GTL_BEGIN_NAMESPACE
0024
0025 //--------------------------------------------------------------------------
0026 //   Con-/Destructors
0027 //--------------------------------------------------------------------------
0028
0029 bfs::bfs () : algorithm ()
0030 {
0031     level_number = 0;
0032     preds = 0;
0033     non_tree = 0;
0034     act_bfs_num = 1;
0035     reached_nodes = 0;
0036     whole_graph = false;
0037 }
0038
0039 bfs::~bfs ()
0040 {
0041     if (level_number) delete level_number;
0042     if (preds) delete preds;
0043     if (non_tree) delete non_tree;
0044 }
0045
0046
0047 //--------------------------------------------------------------------------
0048 //   Parameters
0049 //--------------------------------------------------------------------------
0050
0051 void bfs::calc_level (bool set)
0052 {
0053     if (set && !level_number) {
0054     level_number = new node_map<int>;
0055     } else if (!set && level_number) {
0056     delete level_number;
0057     level_number = 0;
0058     }
0059 }
0060
0061 void bfs::store_preds (bool set)
0062 {
0063     if (set && !preds) {
0064     preds = new node_map<node>;
0065     } else if (!set && preds) {
0066     delete preds;
0067     preds = 0;
0068     }
0069 }
0070
0071 void bfs::store_non_tree_edges (bool set)
0072 {
0073     if (set && !non_tree) {
0074     non_tree = new list<edge>;
0075     } else if (!set && non_tree) {
0076     delete non_tree;
0077     non_tree = 0;
0078     }
0079 }
0080
0081 //--------------------------------------------------------------------------
0082 //   GTL_Algorithm - Interface
0083 //--------------------------------------------------------------------------
0084
0085 void bfs::reset ()
0086 {
0087     act_bfs_num = 1;
0088     tree.erase (tree.begin(), tree.end());
0089     bfs_order.erase (bfs_order.begin(), bfs_order.end());
0090     roots.erase (roots.begin(), roots.end());
0091     reached_nodes = 0;
0092     if (non_tree) {
0093     non_tree->erase (non_tree->begin(), non_tree->end());
0094     }
0095 }
0096
0097
0098 int bfs::run (graph& G) {
0099
0100     bfs_number.init (G, 0);
0101
0102     if (level_number) {
0103     level_number->init (G);
0104     }
0105
0106     if (preds) {
0107     preds->init (G, node());
0108     }
0109
0110     edge_map<int> *used = 0;
0111
0112     if (non_tree) {
0113     used = new edge_map<int> (G, 0);
0114     }
0115
0116     init_handler (G);
0117
0118     //
0119     // Set start-node
0120     //
0121
0122     if (start == node()) {
0123     start = G.choose_node();
0124     }
0125
0126     new_start_handler (G, start);
0127
0128     bfs_sub (G, start, used);
0129
0130     node curr;
0131
0132     if (whole_graph && reached_nodes < G.number_of_nodes()) {
0133     forall_nodes (curr, G) {
0134         if (bfs_number[curr] == 0) {
0135
0136         new_start_handler (G, curr);
0137
0138         bfs_sub (G, curr, used);
0139         }
0140     }
0141     }
0142
0143     if (non_tree) {
0144     delete used;
0145     }
0146
0147     end_handler (G);
0148
0149     return 1;
0150 }
0151
0152
0153
0154 //--------------------------------------------------------------------------
0155 //   PRIVATE
0156 //--------------------------------------------------------------------------
0157
0158
0159 void bfs::bfs_sub (graph& G, const node& st, edge_map<int>* used)
0160 {
0161     qu.push_back (st);
0162     bfs_number[st] = act_bfs_num;
0163     ++act_bfs_num;
0164
0165     if (level_number) {
0166     (*level_number)[st] = 0;
0167     }
0168
0169     while (!qu.empty()) {
0170     node tmp = qu.front();
0171     qu.pop_front();
0172     ++reached_nodes;
0173
0174     if (tmp == st) {
0175         roots.push_back (bfs_order.insert (bfs_order.end(), tmp));
0176     } else {
0177         bfs_order.push_back (tmp);
0178     }
0179
0180     popped_node_handler (G, tmp);
0181
0182     node::adj_edges_iterator it = tmp.adj_edges_begin();
0183     node::adj_edges_iterator end = tmp.adj_edges_end();
0184
0185     for (; it != end; ++it) {
0186         edge curr = *it;
0187         node opp = tmp.opposite (curr);
0188
0189         if (bfs_number[opp] == 0) {
0190         bfs_number[opp] = act_bfs_num;
0191         ++act_bfs_num;
0192         tree.push_back (curr);
0193
0194         if (non_tree) {
0195             (*used)[curr] = 1;
0196         }
0197
0198         if (level_number) {
0199             (*level_number)[opp] = (*level_number)[tmp] + 1;
0200         }
0201
0202         if (preds) {
0203             (*preds)[opp] = tmp;
0204         }
0205
0206         qu.push_back (opp);
0207
0208         unused_node_handler (G, opp, tmp);
0209
0210         } else {
0211         if (non_tree && !(*used)[curr]) {
0212             (*used)[curr] = 1;
0213             non_tree->push_back(curr);
0214         }
0215
0216         used_node_handler (G, opp, tmp);
0217         }
0218     }
0219
0220     finished_node_handler (G, tmp);
0221     }
0222 }
0223
0224 __GTL_END_NAMESPACE
0225
0226 //--------------------------------------------------------------------------
0227 //   end of file
0228 //--------------------------------------------------------------------------