Line data    Source code

       1             : // Copyright (c) 2009-2013 University of Twente
       2             : // Copyright (c) 2009-2013 Michael Weber <michaelw@cs.utwente.nl>
       3             : // Copyright (c) 2009-2013 Maks Verver <maksverver@geocities.com>
       4             : // Copyright (c) 2009-2013 Eindhoven University of Technology
       5             : //
       6             : // Distributed under the Boost Software License, Version 1.0.
       7             : // (See accompanying file LICENSE_1_0.txt or copy at
       8             : // http://www.boost.org/LICENSE_1_0.txt)
       9             : 
      10             : #ifndef MCRL2_PG_SCC_H
      11             : #define MCRL2_PG_SCC_H
      12             : 
      13             : #include "mcrl2/pg/SCC_impl.h"
      14             : 
      15             : /*! \ingroup ParityGameData
      16             : 
      17             :     Decomposition into strongly-connected components using Tarjan's algorithm.
      18             : 
      19             :     Decomposes the static graph into strongly connected components. Components
      20             :     are found in reverse topological order (i.e. if component j is found after
      21             :     component i, there is no path from a node in i to a node in j).
      22             : 
      23             :     For each component found, the callback functor is called with as arguments
      24             :     a list of vertex indices (`const verti[]`) and the size of the component
      25             :     (`std::size_t`).  The callback should return an integer: zero to continue
      26             :     enumerating components, or non-zero to abort.
      27             : 
      28             :     @return the last value returned by a call to callback
      29             : */
      30             : 
      31             : template<class Callback>
      32           0 : int decompose_graph(const StaticGraph &graph, Callback &callback)
      33             : {
      34           0 :     return SCC<Callback>(graph, callback).run();
      35             : }
      36             : 
      37             : /*! \ingroup ParityGameData
      38             : 
      39             :     A utility class to collect strongly connected components in a graph when
      40             :     used as the callback functor in the SCC class defined above.
      41             : 
      42             :     Note that it's usually more efficient to handle SCCs directly as they are
      43             :     found, rather than collect them explicitly, but this class may be easier to
      44             :     use in situation were performance is not critical.
      45             : 
      46             :     Usage example:
      47             :     \code
      48             :     SCCs sccs;
      49             :     decompose_graph(*this, sccs);
      50             :     std::cout << sccs.size() << " SCCs found!" << std::endl;
      51             :     \endcode
      52             : */
      53             : class SCCs
      54             : {
      55             :     std::vector<std::vector<verti> > sccs;
      56             : 
      57             : public:
      58             :     //! Clear the list of collected SCCs.
      59             :     void clear() { sccs.clear(); }
      60             : 
      61             :     //! @return the number of collected SCCs.
      62           0 :     std::size_t size() const { return sccs.size(); }
      63             : 
      64             :     //! @return the i-th SCC as vector of vertex indices.
      65           0 :     std::vector<verti> &operator[](std::size_t i) { return sccs[i]; }
      66             : 
      67             :     //! @return the i-th SCC as const vector of vertex indices.
      68             :     const std::vector<verti> &operator[](std::size_t i) const { return sccs[i]; }
      69             : 
      70             :     /*! Add a strongly connected component to the list.
      71             :         @param scc an array of length `size` giving indices of the vertices 
      72             :         @param size the size of the component
      73             :         @return zero */
      74           0 :     int operator()(const verti scc[], std::size_t size)
      75             :     {
      76           0 :         sccs.resize(sccs.size() + 1);
      77           0 :         sccs.back().assign(&scc[0], &scc[size]); 
      78           0 :         return 0;
      79             :     }
      80             : };
      81             : 
      82             : #endif /* ndef MCRL2_PG_SCC_H */