third_party/boost/include/boost/graph/tiernan_all_cycles.hpp - webm/webmlive - Git at Google

 // (C) Copyright 2007-2009 Andrew Sutton
 //
 // Use, modification and distribution are subject to the
 // Boost Software License, Version 1.0 (See accompanying file
 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)

 #ifndef BOOST_GRAPH_CYCLE_HPP
 #define BOOST_GRAPH_CYCLE_HPP

 #include <vector>

 #include <boost/config.hpp>
 #include <boost/graph/graph_concepts.hpp>
 #include <boost/graph/graph_traits.hpp>
 #include <boost/graph/properties.hpp>

 #include <boost/concept/detail/concept_def.hpp>
 namespace boost {
     namespace concepts {
         BOOST_concept(CycleVisitor,(Visitor)(Path)(Graph))
         {
             BOOST_CONCEPT_USAGE(CycleVisitor)
             {
                 vis.cycle(p, g);
             }
         private:
             Visitor vis;
             Graph g;
             Path p;
         };
     } /* namespace concepts */
 using concepts::CycleVisitorConcept;
 } /* namespace boost */
 #include <boost/concept/detail/concept_undef.hpp>


 namespace boost
 {

 // The implementation of this algorithm is a reproduction of the Teirnan
 // approach for directed graphs: bibtex follows
 //
 //     @article{362819,
 //         author = {James C. Tiernan},
 //         title = {An efficient search algorithm to find the elementary circuits of a graph},
 //         journal = {Commun. ACM},
 //         volume = {13},
 //         number = {12},
 //         year = {1970},
 //         issn = {0001-0782},
 //         pages = {722--726},
 //         doi = {http://doi.acm.org/10.1145/362814.362819},
 //             publisher = {ACM Press},
 //             address = {New York, NY, USA},
 //         }
 //
 // It should be pointed out that the author does not provide a complete analysis for
 // either time or space. This is in part, due to the fact that it's a fairly input
 // sensitive problem related to the density and construction of the graph, not just
 // its size.
 //
 // I've also taken some liberties with the interpretation of the algorithm - I've
 // basically modernized it to use real data structures (no more arrays and matrices).
 // Oh... and there's explicit control structures - not just gotos.
 //
 // The problem is definitely NP-complete, an an unbounded implementation of this
 // will probably run for quite a while on a large graph. The conclusions
 // of this paper also reference a Paton algorithm for undirected graphs as being
 // much more efficient (apparently based on spanning trees). Although not implemented,
 // it can be found here:
 //
 //     @article{363232,
 //         author = {Keith Paton},
 //         title = {An algorithm for finding a fundamental set of cycles of a graph},
 //         journal = {Commun. ACM},
 //         volume = {12},
 //         number = {9},
 //         year = {1969},
 //         issn = {0001-0782},
 //         pages = {514--518},
 //         doi = {http://doi.acm.org/10.1145/363219.363232},
 //             publisher = {ACM Press},
 //             address = {New York, NY, USA},
 //         }

 /**
  * The default cycle visitor providse an empty visit function for cycle
  * visitors.
  */
 struct cycle_visitor
 {
     template <typename Path, typename Graph>
     inline void cycle(const Path& p, const Graph& g)
     { }
 };

 /**
  * The min_max_cycle_visitor simultaneously records the minimum and maximum
  * cycles in a graph.
  */
 struct min_max_cycle_visitor
 {
     min_max_cycle_visitor(std::size_t& min_, std::size_t& max_)
         : minimum(min_), maximum(max_)
     { }

     template <typename Path, typename Graph>
     inline void cycle(const Path& p, const Graph& g)
     {
         BOOST_USING_STD_MIN();
         BOOST_USING_STD_MAX();
         std::size_t len = p.size();
         minimum = min BOOST_PREVENT_MACRO_SUBSTITUTION (minimum, len);
         maximum = max BOOST_PREVENT_MACRO_SUBSTITUTION (maximum, len);
     }
     std::size_t& minimum;
     std::size_t& maximum;
 };

 inline min_max_cycle_visitor
 find_min_max_cycle(std::size_t& min_, std::size_t& max_)
 { return min_max_cycle_visitor(min_, max_); }

 namespace detail
 {
     template <typename Graph, typename Path>
     inline bool
     is_vertex_in_path(const Graph&,
                         typename graph_traits<Graph>::vertex_descriptor v,
                         const Path& p)
     {
         return (std::find(p.begin(), p.end(), v) != p.end());
     }

     template <typename Graph, typename ClosedMatrix>
     inline bool
     is_path_closed(const Graph& g,
                     typename graph_traits<Graph>::vertex_descriptor u,
                     typename graph_traits<Graph>::vertex_descriptor v,
                     const ClosedMatrix& closed)
     {
         // the path from u to v is closed if v can be found in the list
         // of closed vertices associated with u.
         typedef typename ClosedMatrix::const_reference Row;
         Row r = closed[get(vertex_index, g, u)];
         if(find(r.begin(), r.end(), v) != r.end()) {
             return true;
         }
         return false;
     }

     template <typename Graph, typename Path, typename ClosedMatrix>
     inline bool
     can_extend_path(const Graph& g,
                     typename graph_traits<Graph>::edge_descriptor e,
                     const Path& p,
                     const ClosedMatrix& m)
     {
         function_requires< IncidenceGraphConcept<Graph> >();
         function_requires< VertexIndexGraphConcept<Graph> >();
         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

         // get the vertices in question
         Vertex
             u = source(e, g),
             v = target(e, g);

         // conditions for allowing a traversal along this edge are:
         // 1. the index of v must be greater than that at which the
         //    the path is rooted (p.front()).
         // 2. the vertex v cannot already be in the path
         // 3. the vertex v cannot be closed to the vertex u

         bool indices = get(vertex_index, g, p.front()) < get(vertex_index, g, v);
         bool path = !is_vertex_in_path(g, v, p);
         bool closed = !is_path_closed(g, u, v, m);
         return indices && path && closed;
     }

     template <typename Graph, typename Path>
     inline bool
     can_wrap_path(const Graph& g, const Path& p)
     {
         function_requires< IncidenceGraphConcept<Graph> >();
         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
         typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;

         // iterate over the out-edges of the back, looking for the
         // front of the path. also, we can't travel along the same
         // edge that we did on the way here, but we don't quite have the
         // stringent requirements that we do in can_extend_path().
         Vertex
             u = p.back(),
             v = p.front();
         OutIterator i, end;
         for(tie(i, end) = out_edges(u, g); i != end; ++i) {
             if((target(*i, g) == v)) {
                 return true;
             }
         }
         return false;
     }

     template <typename Graph,
         typename Path,
         typename ClosedMatrix>
     inline typename graph_traits<Graph>::vertex_descriptor
     extend_path(const Graph& g,
                 Path& p,
                 ClosedMatrix& closed)
     {
         function_requires< IncidenceGraphConcept<Graph> >();
         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
         typedef typename graph_traits<Graph>::edge_descriptor Edge;
         typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;

         // get the current vertex
         Vertex u = p.back();
         Vertex ret = graph_traits<Graph>::null_vertex();

         // AdjacencyIterator i, end;
         OutIterator i, end;
         for(tie(i, end) = out_edges(u, g); i != end; ++i) {
             Vertex v = target(*i, g);

             // if we can actually extend along this edge,
             // then that's what we want to do
             if(can_extend_path(g, *i, p, closed)) {
                 p.push_back(v);         // add the vertex to the path
                 ret = v;
                 break;
             }
         }
         return ret;
     }

     template <typename Graph, typename Path, typename ClosedMatrix>
     inline bool
     exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
     {
         function_requires< GraphConcept<Graph> >();
         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

         // if there's more than one vertex in the path, this closes
         // of some possible routes and returns true. otherwise, if there's
         // only one vertex left, the vertex has been used up
         if(p.size() > 1) {
             // get the last and second to last vertices, popping the last
             // vertex off the path
             Vertex last, prev;
             last = p.back();
             p.pop_back();
             prev = p.back();

             // reset the closure for the last vertex of the path and
             // indicate that the last vertex in p is now closed to
             // the next-to-last vertex in p
             closed[get(vertex_index, g, last)].clear();
             closed[get(vertex_index, g, prev)].push_back(last);
             return true;
         }
         else {
             return false;
         }
     }

     template <typename Graph, typename Visitor>
     inline void
     all_cycles_from_vertex(const Graph& g,
                             typename graph_traits<Graph>::vertex_descriptor v,
                             Visitor vis,
                             std::size_t minlen,
                             std::size_t maxlen)
     {
         function_requires< VertexListGraphConcept<Graph> >();
         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
         typedef std::vector<Vertex> Path;
         function_requires< CycleVisitorConcept<Visitor,Path,Graph> >();
         typedef std::vector<Vertex> VertexList;
         typedef std::vector<VertexList> ClosedMatrix;

         Path p;
         ClosedMatrix closed(num_vertices(g), VertexList());
         Vertex null = graph_traits<Graph>::null_vertex();

         // each path investigation starts at the ith vertex
         p.push_back(v);

         while(1) {
             // extend the path until we've reached the end or the
             // maxlen-sized cycle
             Vertex j = null;
             while(((j = detail::extend_path(g, p, closed)) != null)
                     && (p.size() < maxlen))
                 ; // empty loop

             // if we're done extending the path and there's an edge
             // connecting the back to the front, then we should have
             // a cycle.
             if(detail::can_wrap_path(g, p) && p.size() >= minlen) {
                 vis.cycle(p, g);
             }

             if(!detail::exhaust_paths(g, p, closed)) {
                 break;
             }
         }
     }

     // Select the minimum allowable length of a cycle based on the directedness
     // of the graph - 2 for directed, 3 for undirected.
     template <typename D> struct min_cycles { enum { value = 2 }; };
     template <> struct min_cycles<undirected_tag> { enum { value = 3 }; };
 } /* namespace detail */

 template <typename Graph, typename Visitor>
 inline void
 tiernan_all_cycles(const Graph& g,
                     Visitor vis,
                     std::size_t minlen,
                     std::size_t maxlen)
 {
     function_requires< VertexListGraphConcept<Graph> >();
     typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;

     VertexIterator i, end;
     for(tie(i, end) = vertices(g); i != end; ++i) {
         detail::all_cycles_from_vertex(g, *i, vis, minlen, maxlen);
     }
 }

 template <typename Graph, typename Visitor>
 inline void
 tiernan_all_cycles(const Graph& g, Visitor vis, std::size_t maxlen)
 {
     typedef typename graph_traits<Graph>::directed_category Dir;
     tiernan_all_cycles(g, vis, detail::min_cycles<Dir>::value, maxlen);
 }

 template <typename Graph, typename Visitor>
 inline void
 tiernan_all_cycles(const Graph& g, Visitor vis)
 {
     typedef typename graph_traits<Graph>::directed_category Dir;
     tiernan_all_cycles(g, vis, detail::min_cycles<Dir>::value,
                        (std::numeric_limits<std::size_t>::max)());
 }

 template <typename Graph>
 inline std::pair<std::size_t, std::size_t>
 tiernan_girth_and_circumference(const Graph& g)
 {
     std::size_t
         min_ = (std::numeric_limits<std::size_t>::max)(),
         max_ = 0;
     tiernan_all_cycles(g, find_min_max_cycle(min_, max_));

     // if this is the case, the graph is acyclic...
     if(max_ == 0) max_ = min_;

     return std::make_pair(min_, max_);
 }

 template <typename Graph>
 inline std::size_t
 tiernan_girth(const Graph& g)
 { return tiernan_girth_and_circumference(g).first; }

 template <typename Graph>
 inline std::size_t
 tiernan_circumference(const Graph& g)
 { return tiernan_girth_and_circumference(g).second; }

 } /* namespace boost */

 #endif
	// (C) Copyright 2007-2009 Andrew Sutton
	//
	// Use, modification and distribution are subject to the
	// Boost Software License, Version 1.0 (See accompanying file
	// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)

	#ifndef BOOST_GRAPH_CYCLE_HPP
	#define BOOST_GRAPH_CYCLE_HPP

	#include <vector>

	#include <boost/config.hpp>
	#include <boost/graph/graph_concepts.hpp>
	#include <boost/graph/graph_traits.hpp>
	#include <boost/graph/properties.hpp>

	#include <boost/concept/detail/concept_def.hpp>
	namespace boost {
	namespace concepts {
	BOOST_concept(CycleVisitor,(Visitor)(Path)(Graph))
	{
	BOOST_CONCEPT_USAGE(CycleVisitor)
	{
	vis.cycle(p, g);
	}
	private:
	Visitor vis;
	Graph g;
	Path p;
	};
	} /* namespace concepts */
	using concepts::CycleVisitorConcept;
	} /* namespace boost */
	#include <boost/concept/detail/concept_undef.hpp>


	namespace boost
	{

	// The implementation of this algorithm is a reproduction of the Teirnan
	// approach for directed graphs: bibtex follows
	//
	// @article{362819,
	// author = {James C. Tiernan},
	// title = {An efficient search algorithm to find the elementary circuits of a graph},
	// journal = {Commun. ACM},
	// volume = {13},
	// number = {12},
	// year = {1970},
	// issn = {0001-0782},
	// pages = {722--726},
	// doi = {http://doi.acm.org/10.1145/362814.362819},
	// publisher = {ACM Press},
	// address = {New York, NY, USA},
	// }
	//
	// It should be pointed out that the author does not provide a complete analysis for
	// either time or space. This is in part, due to the fact that it's a fairly input
	// sensitive problem related to the density and construction of the graph, not just
	// its size.
	//
	// I've also taken some liberties with the interpretation of the algorithm - I've
	// basically modernized it to use real data structures (no more arrays and matrices).
	// Oh... and there's explicit control structures - not just gotos.
	//
	// The problem is definitely NP-complete, an an unbounded implementation of this
	// will probably run for quite a while on a large graph. The conclusions
	// of this paper also reference a Paton algorithm for undirected graphs as being
	// much more efficient (apparently based on spanning trees). Although not implemented,
	// it can be found here:
	//
	// @article{363232,
	// author = {Keith Paton},
	// title = {An algorithm for finding a fundamental set of cycles of a graph},
	// journal = {Commun. ACM},
	// volume = {12},
	// number = {9},
	// year = {1969},
	// issn = {0001-0782},
	// pages = {514--518},
	// doi = {http://doi.acm.org/10.1145/363219.363232},
	// publisher = {ACM Press},
	// address = {New York, NY, USA},
	// }

	/**
	* The default cycle visitor providse an empty visit function for cycle
	* visitors.
	*/
	struct cycle_visitor
	{
	template <typename Path, typename Graph>
	inline void cycle(const Path& p, const Graph& g)
	{ }
	};

	/**
	* The min_max_cycle_visitor simultaneously records the minimum and maximum
	* cycles in a graph.
	*/
	struct min_max_cycle_visitor
	{
	min_max_cycle_visitor(std::size_t& min_, std::size_t& max_)
	: minimum(min_), maximum(max_)
	{ }

	template <typename Path, typename Graph>
	inline void cycle(const Path& p, const Graph& g)
	{
	BOOST_USING_STD_MIN();
	BOOST_USING_STD_MAX();
	std::size_t len = p.size();
	minimum = min BOOST_PREVENT_MACRO_SUBSTITUTION (minimum, len);
	maximum = max BOOST_PREVENT_MACRO_SUBSTITUTION (maximum, len);
	}
	std::size_t& minimum;
	std::size_t& maximum;
	};

	inline min_max_cycle_visitor
	find_min_max_cycle(std::size_t& min_, std::size_t& max_)
	{ return min_max_cycle_visitor(min_, max_); }

	namespace detail
	{
	template <typename Graph, typename Path>
	inline bool
	is_vertex_in_path(const Graph&,
	typename graph_traits<Graph>::vertex_descriptor v,
	const Path& p)
	{
	return (std::find(p.begin(), p.end(), v) != p.end());
	}

	template <typename Graph, typename ClosedMatrix>
	inline bool
	is_path_closed(const Graph& g,
	typename graph_traits<Graph>::vertex_descriptor u,
	typename graph_traits<Graph>::vertex_descriptor v,
	const ClosedMatrix& closed)
	{
	// the path from u to v is closed if v can be found in the list
	// of closed vertices associated with u.
	typedef typename ClosedMatrix::const_reference Row;
	Row r = closed[get(vertex_index, g, u)];
	if(find(r.begin(), r.end(), v) != r.end()) {
	return true;
	}
	return false;
	}

	template <typename Graph, typename Path, typename ClosedMatrix>
	inline bool
	can_extend_path(const Graph& g,
	typename graph_traits<Graph>::edge_descriptor e,
	const Path& p,
	const ClosedMatrix& m)
	{
	function_requires< IncidenceGraphConcept<Graph> >();
	function_requires< VertexIndexGraphConcept<Graph> >();
	typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

	// get the vertices in question
	Vertex
	u = source(e, g),
	v = target(e, g);

	// conditions for allowing a traversal along this edge are:
	// 1. the index of v must be greater than that at which the
	// the path is rooted (p.front()).
	// 2. the vertex v cannot already be in the path
	// 3. the vertex v cannot be closed to the vertex u

	bool indices = get(vertex_index, g, p.front()) < get(vertex_index, g, v);
	bool path = !is_vertex_in_path(g, v, p);
	bool closed = !is_path_closed(g, u, v, m);
	return indices && path && closed;
	}

	template <typename Graph, typename Path>
	inline bool
	can_wrap_path(const Graph& g, const Path& p)
	{
	function_requires< IncidenceGraphConcept<Graph> >();
	typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
	typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;

	// iterate over the out-edges of the back, looking for the
	// front of the path. also, we can't travel along the same
	// edge that we did on the way here, but we don't quite have the
	// stringent requirements that we do in can_extend_path().
	Vertex
	u = p.back(),
	v = p.front();
	OutIterator i, end;
	for(tie(i, end) = out_edges(u, g); i != end; ++i) {
	if((target(*i, g) == v)) {
	return true;
	}
	}
	return false;
	}

	template <typename Graph,
	typename Path,
	typename ClosedMatrix>
	inline typename graph_traits<Graph>::vertex_descriptor
	extend_path(const Graph& g,
	Path& p,
	ClosedMatrix& closed)
	{
	function_requires< IncidenceGraphConcept<Graph> >();
	typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
	typedef typename graph_traits<Graph>::edge_descriptor Edge;
	typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;

	// get the current vertex
	Vertex u = p.back();
	Vertex ret = graph_traits<Graph>::null_vertex();

	// AdjacencyIterator i, end;
	OutIterator i, end;
	for(tie(i, end) = out_edges(u, g); i != end; ++i) {
	Vertex v = target(*i, g);

	// if we can actually extend along this edge,
	// then that's what we want to do
	if(can_extend_path(g, *i, p, closed)) {
	p.push_back(v); // add the vertex to the path
	ret = v;
	break;
	}
	}
	return ret;
	}

	template <typename Graph, typename Path, typename ClosedMatrix>
	inline bool
	exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
	{
	function_requires< GraphConcept<Graph> >();
	typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

	// if there's more than one vertex in the path, this closes
	// of some possible routes and returns true. otherwise, if there's
	// only one vertex left, the vertex has been used up
	if(p.size() > 1) {
	// get the last and second to last vertices, popping the last
	// vertex off the path
	Vertex last, prev;
	last = p.back();
	p.pop_back();
	prev = p.back();

	// reset the closure for the last vertex of the path and
	// indicate that the last vertex in p is now closed to
	// the next-to-last vertex in p
	closed[get(vertex_index, g, last)].clear();
	closed[get(vertex_index, g, prev)].push_back(last);
	return true;
	}
	else {
	return false;
	}
	}

	template <typename Graph, typename Visitor>
	inline void
	all_cycles_from_vertex(const Graph& g,
	typename graph_traits<Graph>::vertex_descriptor v,
	Visitor vis,
	std::size_t minlen,
	std::size_t maxlen)
	{
	function_requires< VertexListGraphConcept<Graph> >();
	typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
	typedef std::vector<Vertex> Path;
	function_requires< CycleVisitorConcept<Visitor,Path,Graph> >();
	typedef std::vector<Vertex> VertexList;
	typedef std::vector<VertexList> ClosedMatrix;

	Path p;
	ClosedMatrix closed(num_vertices(g), VertexList());
	Vertex null = graph_traits<Graph>::null_vertex();

	// each path investigation starts at the ith vertex
	p.push_back(v);

	while(1) {
	// extend the path until we've reached the end or the
	// maxlen-sized cycle
	Vertex j = null;
	while(((j = detail::extend_path(g, p, closed)) != null)
	&& (p.size() < maxlen))
	; // empty loop

	// if we're done extending the path and there's an edge
	// connecting the back to the front, then we should have
	// a cycle.
	if(detail::can_wrap_path(g, p) && p.size() >= minlen) {
	vis.cycle(p, g);
	}

	if(!detail::exhaust_paths(g, p, closed)) {
	break;
	}
	}
	}

	// Select the minimum allowable length of a cycle based on the directedness
	// of the graph - 2 for directed, 3 for undirected.
	template <typename D> struct min_cycles { enum { value = 2 }; };
	template <> struct min_cycles<undirected_tag> { enum { value = 3 }; };
	} /* namespace detail */

	template <typename Graph, typename Visitor>
	inline void
	tiernan_all_cycles(const Graph& g,
	Visitor vis,
	std::size_t minlen,
	std::size_t maxlen)
	{
	function_requires< VertexListGraphConcept<Graph> >();
	typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;

	VertexIterator i, end;
	for(tie(i, end) = vertices(g); i != end; ++i) {
	detail::all_cycles_from_vertex(g, *i, vis, minlen, maxlen);
	}
	}

	template <typename Graph, typename Visitor>
	inline void
	tiernan_all_cycles(const Graph& g, Visitor vis, std::size_t maxlen)
	{
	typedef typename graph_traits<Graph>::directed_category Dir;
	tiernan_all_cycles(g, vis, detail::min_cycles<Dir>::value, maxlen);
	}

	template <typename Graph, typename Visitor>
	inline void
	tiernan_all_cycles(const Graph& g, Visitor vis)
	{
	typedef typename graph_traits<Graph>::directed_category Dir;
	tiernan_all_cycles(g, vis, detail::min_cycles<Dir>::value,
	(std::numeric_limits<std::size_t>::max)());
	}

	template <typename Graph>
	inline std::pair<std::size_t, std::size_t>
	tiernan_girth_and_circumference(const Graph& g)
	{
	std::size_t
	min_ = (std::numeric_limits<std::size_t>::max)(),
	max_ = 0;
	tiernan_all_cycles(g, find_min_max_cycle(min_, max_));

	// if this is the case, the graph is acyclic...
	if(max_ == 0) max_ = min_;

	return std::make_pair(min_, max_);
	}

	template <typename Graph>
	inline std::size_t
	tiernan_girth(const Graph& g)
	{ return tiernan_girth_and_circumference(g).first; }

	template <typename Graph>
	inline std::size_t
	tiernan_circumference(const Graph& g)
	{ return tiernan_girth_and_circumference(g).second; }

	} /* namespace boost */

	#endif