gtl/src/dfs.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   dfs.cpp
0005 //
0006 //==========================================================================
0007 // $Id: dfs.cpp,v 1.18 2001/11/07 13:58:09 pick Exp $
0008
0009 #include <GTL/dfs.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 dfs::dfs () : algorithm ()
0030 {
0031     act_dfs_num = 1;
0032     act_comp_num = 1;
0033     reached_nodes = 0;
0034     whole_graph = false;
0035     comp_number = 0;
0036     preds = 0;
0037     used = 0;
0038     back_edges = 0;
0039 }
0040
0041 dfs::~dfs ()
0042 {
0043     if (comp_number) delete comp_number;
0044     if (preds) delete preds;
0045     if (back_edges) {
0046     delete back_edges;
0047     delete used;
0048     }
0049 }
0050
0051 //--------------------------------------------------------------------------
0052 //   GTL_Algorithm - Interface
0053 //--------------------------------------------------------------------------
0054
0055
0056 void dfs::reset ()
0057 {
0058     act_dfs_num = 1;
0059     act_comp_num = 1;
0060     reached_nodes = 0;
0061     tree.erase (tree.begin(), tree.end());
0062     dfs_order.erase (dfs_order.begin(), dfs_order.end());
0063     roots.erase (roots.begin(), roots.end());
0064     start = node();
0065
0066     if (back_edges) {
0067     back_edges->erase (back_edges->begin(), back_edges->end());
0068     }
0069 }
0070
0071
0072 int dfs::check (graph& G)
0073 {
0074     return GTL_OK;
0075 }
0076
0077 int dfs::run (graph& G)
0078 {
0079     //
0080     // initialization
0081     //
0082
0083     node curr;
0084     node dummy;
0085
0086     dfs_number.init (G, 0);
0087
0088     if (comp_number) {
0089     comp_number->init (G);
0090     }
0091
0092     if (preds) {
0093     preds->init (G, node());
0094     }
0095
0096     if (back_edges) {
0097     used = new edge_map<int> (G, 0);
0098     }
0099
0100     init_handler (G);
0101
0102     //
0103     // Set start-node
0104     //
0105
0106     if (G.number_of_nodes() == 0) {
0107     return GTL_OK;
0108     }
0109
0110     if (start == node()) {
0111     start = G.choose_node();
0112     }
0113
0114     new_start_handler (G, start);
0115
0116     dfs_sub (G, start, dummy);
0117
0118     if (whole_graph && reached_nodes < G.number_of_nodes()) {
0119
0120     //
0121     // Continue DFS with next unused node.
0122     //
0123
0124     forall_nodes (curr, G) {
0125         if (dfs_number[curr] == 0) {
0126         new_start_handler (G, curr);
0127         dfs_sub (G, curr, dummy);
0128         }
0129     }
0130     }
0131
0132     if (back_edges) {
0133     delete used;
0134     used = 0;
0135     }
0136
0137     end_handler(G);
0138
0139     return GTL_OK;
0140 }
0141
0142
0143 //--------------------------------------------------------------------------
0144 //   PRIVATE
0145 //--------------------------------------------------------------------------
0146
0147
0148 void dfs::dfs_sub (graph& G, node& curr, node& father)
0149 {
0150     node opp;
0151     edge adj;
0152
0153     if (father == node()) {
0154     roots.push_back (dfs_order.insert (dfs_order.end(), curr));
0155     } else {
0156     dfs_order.push_back (curr);
0157     }
0158
0159     dfs_number[curr] = act_dfs_num;
0160     reached_nodes++;
0161
0162     if (preds) {
0163     (*preds)[curr] = father;
0164     }
0165
0166     entry_handler (G, curr, father);
0167
0168     ++act_dfs_num;
0169     node::adj_edges_iterator it = curr.adj_edges_begin();
0170     node::adj_edges_iterator end = curr.adj_edges_end();
0171
0172     while (it != end) {
0173     adj = *it;
0174     opp = curr.opposite(adj);
0175
0176     if (dfs_number[opp] == 0) {
0177         tree.push_back (adj);
0178
0179         if (back_edges) {
0180         (*used)[adj] = 1;
0181         }
0182
0183         before_recursive_call_handler (G, adj, opp);
0184         dfs_sub (G, opp, curr);
0185         after_recursive_call_handler (G, adj, opp);
0186
0187     } else {
0188         if (back_edges && !(*used)[adj]) {
0189         (*used)[adj] = 1;
0190         back_edges->push_back (adj);
0191         }
0192
0193         old_adj_node_handler (G, adj, opp);
0194     }
0195
0196     ++it;
0197     }
0198
0199     leave_handler (G, curr, father);
0200
0201     if (comp_number) {
0202     (*comp_number)[curr] = act_comp_num;
0203     ++act_comp_num;
0204     }
0205 }
0206
0207 //--------------------------------------------------------------------------
0208 //   Parameters
0209 //--------------------------------------------------------------------------
0210
0211 void dfs::calc_comp_num (bool set)
0212 {
0213     if (set && !comp_number) {
0214     comp_number = new node_map<int>;
0215     } else if (!set && comp_number) {
0216     delete comp_number;
0217     comp_number = 0;
0218     }
0219 }
0220
0221 void dfs::store_preds (bool set)
0222 {
0223     if (set && !preds) {
0224     preds = new node_map<node>;
0225     } else if (!set && preds) {
0226     delete preds;
0227     preds = 0;
0228     }
0229 }
0230
0231 void dfs::store_non_tree_edges (bool set)
0232 {
0233     if (set && !back_edges) {
0234     back_edges = new list<edge>;
0235     } else if (!set && back_edges) {
0236     delete back_edges;
0237     back_edges = 0;
0238     }
0239 }
0240
0241 __GTL_END_NAMESPACE
0242
0243 //--------------------------------------------------------------------------
0244 //   end of file
0245 //--------------------------------------------------------------------------