include/GTL/topsort.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   topsort.h
0005 //
0006 //==========================================================================
0007 // $Id: topsort.h,v 1.8 2000/09/11 07:36:43 raitner Exp $
0008
0009 #ifndef GTL_TOPSORT
0010 #define GTL_TOPSORT
0011
0012 #include <GTL/GTL.h>
0013 #include <GTL/dfs.h>
0014
0015 __GTL_BEGIN_NAMESPACE
0016
0017 /**
0018  * @short Topological sorting.
0019  *
0020  * Assigns to each node <code>n</code> a number <code>top_num</code> such
0021  * that for every edge <code>(u,v)</code> <code>top_num[u]</code> &lt;
0022  * <code>top_num[v]</code>, if possible, i.e. iff the directed graph is
0023  * acyclic.
0024  *
0025  * <p>
0026  * Similar to the testing of biconnectivity, which extends DFS to calculate
0027  * low-numbers, the topsort-algorithm extends DFS to calculate the new
0028  * numbering (and thus to test whether such a numbering is possible).
0029  *
0030  * <p>
0031  * In order to traverse all the nodes in the order of its top-numbers, a
0032  * new iterator, <code>topsort_iterator</code> is provided.
0033  */
0034
0035 class GTL_EXTERN topsort : public dfs
0036 {
0037 public:
0038     /**
0039      * default constructor; enables scanning of the whole_graph.
0040      *
0041      * @see dfs#dfs
0042      */
0043     topsort () : dfs () {whole_graph = true; acyclic = true;}
0044
0045     /**
0046      * Number in topological order.
0047      *
0048      * @param <code>n</code> node.
0049      * @return number in topological order.
0050      */
0051     int top_num (const node& n) const
0052     { return top_numbers[n]; }
0053
0054     /**
0055      * Tests if graph was acyclic.
0056      *
0057      * @return true iff graph was acyclic.
0058      */
0059     bool is_acyclic () const
0060     { return acyclic; }
0061
0062     /**
0063      * @internal
0064      */
0065     typedef list<node>::const_iterator topsort_iterator;
0066
0067     /**
0068      * Iterate through nodes in topsort-order.
0069      *
0070      * @return start-iterator.
0071      */
0072     topsort_iterator top_order_begin() const
0073     { return top_order.begin(); }
0074
0075     /**
0076      * Iterate through nodes in topsort-order.
0077      *
0078      * @return end-iterator.
0079      */
0080     topsort_iterator top_order_end() const
0081     { return top_order.end(); }
0082
0083     /**
0084      * Preconditions:
0085      * <ul>
0086      * <li> <code>G</code> is directed.
0087      * <li> DFS may be applied
0088      * </ul>
0089      *
0090      * @param <code>G</code> graph.
0091      * @return <code>algorithm::GTL_OK</code> if topsort may be applied to
0092      * <code>G</code>.
0093      * @see dfs#check
0094      */
0095     virtual int check (graph& G);
0096
0097     /**
0098      * Reset
0099      * @see dfs#reset
0100      */
0101     virtual void reset ();
0102
0103     /**
0104      * @internal
0105      */
0106     virtual void init_handler (graph& G);
0107
0108     /**
0109      * @internal
0110      */
0111     virtual void leave_handler (graph&, node&, node&);
0112
0113     /**
0114      * @internal
0115      */
0116     virtual void old_adj_node_handler (graph&, edge&, node&);
0117
0118 protected:
0119     /**
0120      * @internal
0121      */
0122     int act_top_num;
0123     /**
0124      * @internal
0125      */
0126     node_map<int> top_numbers;
0127     /**
0128      * @internal
0129      */
0130     list<node> top_order;
0131     /**
0132      * @internal
0133      */
0134     bool acyclic;
0135 };
0136
0137 __GTL_END_NAMESPACE
0138
0139 #endif // GTL_TOPSORT
0140
0141 //--------------------------------------------------------------------------
0142 //   end of file
0143 //--------------------------------------------------------------------------