graph_algorithm.hpp

Go to the documentation of this file.

/*
  CLAW - a C++ Library Absolutely Wonderful
 
  CLAW is a free library without any particular aim but being useful to
  anyone.
 
  Copyright (C) 2005-2011 Julien Jorge
 
  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.
 
  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.
 
  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 
  contact: julien.jorge@stuff-o-matic.com
*/
#ifndef __CLAW_GRAPH_ALGORITHM_HPP__
#define __CLAW_GRAPH_ALGORITHM_HPP__
 
#include <map>
 
namespace claw
{
  //*************************** graph::scan_events ****************************

  template <class Graph>
  class scan_events
  {
  public:
    typedef typename Graph::vertex_type vertex_type;
 
  public:
    void init(const Graph& g)
    {}
    void start_vertex(const vertex_type& v)
    {}
    void visit_edge(const vertex_type& v1, const vertex_type& v2)
    {}
    void end_vertex(const vertex_type& v)
    {}
  }; // class scan_events
 
  //************************** breadth_scan ***********************************

  template <class Graph, class Events = scan_events<Graph> >
  class breadth_scan
  {
  public:
    typedef typename Graph::vertex_type vertex_type;
    typedef typename Graph::vertex_iterator vertex_iterator;
    typedef std::map<vertex_type, int, typename Graph::vertex_compare>
        coloration;
 
  public:
    breadth_scan(const Graph& g, const vertex_type& source, Events& events);
 
    void operator()();
 
  private:
    const Graph& m_g;
    const vertex_type& m_source;
    Events& m_events;
  }; // class breadth_scan
 
  //**************************** depth_scan ***********************************

  template <class Graph, class Events = typename Graph::scan_events>
  class depth_scan
  {
  public:
    typedef typename Graph::vertex_type vertex_type;
    typedef typename Graph::vertex_iterator vertex_iterator;
    typedef std::map<vertex_type, int, typename Graph::vertex_compare>
        coloration;
 
  public:
    depth_scan(const Graph& g, Events& events);
 
    void operator()();
 
  private:
    void recursive_scan(const vertex_type& s, coloration& seen_vertices);
 
  private:
    const Graph& m_g;
    Events& m_events;
  }; // class depth_scan
 
  //********************** topological_sort ***********************************

  template <class Graph>
  class topological_sort : public scan_events<Graph>
  {
  public:
    typedef typename scan_events<Graph>::vertex_type vertex_type;
    typedef std::vector<vertex_type> result_type;
    typedef typename result_type::const_iterator const_iterator;
    typedef topological_sort<Graph> self_type;
 
  public:
    void init(const Graph& g);
    void end_vertex(const vertex_type& s);
 
    void operator()(const Graph& g);
    const vertex_type& operator[](unsigned int index) const;
 
    const_iterator begin() const;
    const_iterator end() const;
 
  private:
    result_type m_result;
    int m_next_index;
  }; // class topological_sort
 
}
 
#include <claw/graph_algorithm.tpp>
 
#endif // __CLAW_GRAPH_ALGORITHM_HPP__