gtl/src/topsort.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   topsort.cpp
0005 //
0006 //==========================================================================
0007 // $Id: topsort.cpp,v 1.7 2001/11/07 13:58:12 pick Exp $
0008
0009 #include <GTL/topsort.h>
0010
0011 #ifdef __GTL_MSVCC
0012 #   ifdef _DEBUG
0013 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0014 #   error SEARCH NOT ENABLED
0015 #   endif
0016 #   define new DEBUG_NEW
0017 #   undef THIS_FILE
0018     static char THIS_FILE[] = __FILE__;
0019 #   endif   // _DEBUG
0020 #endif  // __GTL_MSVCC
0021
0022 __GTL_BEGIN_NAMESPACE
0023
0024 //--------------------------------------------------------------------------
0025 //   algorithm - interface
0026 //--------------------------------------------------------------------------
0027
0028
0029 void topsort::reset ()
0030 {
0031     dfs::reset();
0032     acyclic = true;
0033     top_order.erase (top_order.begin(), top_order.end());;
0034 }
0035
0036 int topsort::check (graph& G)
0037 {
0038     return G.is_directed() ? GTL_OK : GTL_ERROR;
0039 }
0040
0041
0042
0043 //--------------------------------------------------------------------------
0044 //   Handler
0045 //--------------------------------------------------------------------------
0046
0047
0048 void topsort::init_handler (graph& G)
0049 {
0050     top_numbers.init (G, 0);
0051     act_top_num = G.number_of_nodes();
0052 }
0053
0054
0055 void topsort::leave_handler (graph& G, node& n, node& f)
0056 {
0057     top_numbers[n] = act_top_num;
0058     act_top_num--;
0059     top_order.push_front (n);
0060 }
0061
0062
0063 void topsort::old_adj_node_handler (graph& G, edge& adj, node& opp)
0064 {
0065     if (top_numbers[opp] == 0) {
0066     acyclic = false;
0067     }
0068 }
0069
0070 __GTL_END_NAMESPACE
0071
0072 //--------------------------------------------------------------------------
0073 //   end of file
0074 //--------------------------------------------------------------------------