[Boost-commit] svn:boost r38799 - sandbox/SOC/2007/graphs/boost/graph

From: asutton_at_[hidden]
Date: 2007-08-20 13:48:46

Author: asutton
Date: 2007-08-20 13:48:45 EDT (Mon, 20 Aug 2007)
New Revision: 38799
URL: http://svn.boost.org/trac/boost/changeset/38799

Log:
Added new tiernan functions for girth and circumference
Renamed radius_and_diameter in eccentricity

Text files modified: 
   sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp       |     2                                         
   sandbox/SOC/2007/graphs/boost/graph/new_graph_concepts.hpp |    95 +++++++++++++++++++++++++++++++++++++-- 
   sandbox/SOC/2007/graphs/boost/graph/tiernan_all_cycles.hpp |    72 +++++++++++++++++++++++++-----          
   3 files changed, 150 insertions(+), 19 deletions(-)

Modified: sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/eccentricity.hpp	2007-08-20 13:48:45 EDT (Mon, 20 Aug 2007)
@@ -114,7 +114,7 @@
     template <typename Graph, typename EccentricityMap>
     inline std::pair<typename property_traits<EccentricityMap>::value_type,
                      typename property_traits<EccentricityMap>::value_type>
-    radius_diameter(const Graph& g, EccentricityMap ecc)
+    radius_and_diameter(const Graph& g, EccentricityMap ecc)
     {
         function_requires< VertexListGraphConcept<Graph> >();
         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

Modified: sandbox/SOC/2007/graphs/boost/graph/new_graph_concepts.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/new_graph_concepts.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/new_graph_concepts.hpp	2007-08-20 13:48:45 EDT (Mon, 20 Aug 2007)
@@ -9,18 +9,72 @@
 
 #include <boost/property_map.hpp>
 #include <boost/graph/graph_concepts.hpp>
+#include <boost/graph/graph_traits.hpp>
 #include <boost/graph/numeric_values.hpp>
 
 #include <boost/concept/detail/concept_def.hpp>
 namespace boost
 {
-    // The DegreeMeasure is its own concept because it does, in a way
-    // specialize the semantics of an AdaptableBinaryFunction. Specifically,
-    // it is templated over a single type - a graph and derives its result
-    // and argument types from that graph.
-
     namespace concepts
     {
+        BOOST_concept(VertexIndexGraph,(Graph))
+        {
+            BOOST_CONCEPT_USAGE(VertexIndexGraph)
+            {
+                // TODO: This relaxes the constraints so that the only
+                // thing it actually requires is access to the property map
+                // and indices.
+                typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+                typedef typename property_map<Graph, vertex_index_t>::type Map;
+                typedef unsigned Index; // This should be Graph::vertex_index_type
+                Map m = get(vertex_index, g);
+                Index x = get(vertex_index, g, Vertex());
+                ignore_unused_variable_warning(x);
+
+                // This is relaxed
+                renumber_vertex_indices(g);
+
+                const_constraints(g);
+            }
+            void const_constraints(const Graph& g)
+            {
+                typedef typename property_map<Graph, vertex_index_t>::const_type Map;
+                Map m = get(vertex_index, g);
+                ignore_unused_variable_warning(m);
+            }
+        private:
+            Graph g;
+        };
+
+        BOOST_concept(EdgeIndexGraph,(Graph))
+        {
+            BOOST_CONCEPT_USAGE(EdgeIndexGraph)
+            {
+                // TODO: This relaxes the constraints so that the only
+                // thing it actually requires is access to the property map
+                // and indices.
+                typedef typename graph_traits<Graph>::edge_descriptor Edge;
+                typedef typename property_map<Graph, edge_index_t>::type Map;
+                typedef unsigned Index; // This should be Graph::vertex_index_type
+                Map m = get(edge_index, g);
+                Index x = get(edge_index, g, Edge());
+                ignore_unused_variable_warning(x);
+
+                // This is relaxed
+                renumber_edge_indices(g);
+
+                const_constraints(g);
+            }
+            void const_constraints(const Graph& g)
+            {
+                typedef typename property_map<Graph, edge_index_t>::const_type Map;
+                Map m = get(edge_index, g);
+                ignore_unused_variable_warning(m);
+            }
+        private:
+            Graph g;
+        };
+
         BOOST_concept(NumericValue,(Numeric))
         {
             BOOST_CONCEPT_USAGE(NumericValue)
@@ -38,6 +92,7 @@
             {
                 typedef typename Measure::degree_type Degree;
                 typedef typename Measure::vertex_type Vertex;
+
                 Degree d = m(Vertex(), g);
                 ignore_unused_variable_warning(d);
             }
@@ -59,11 +114,39 @@
             Measure m;
             Graph g;
         };
-    }
 
+        BOOST_concept(CycleVisitor,(Visitor)(Path)(Graph))
+        {
+            BOOST_CONCEPT_USAGE(CycleVisitor)
+            {
+                vis.cycle(p, g);
+            }
+        private:
+            Visitor vis;
+            Graph g;
+            Path p;
+        };
+
+        BOOST_concept(CliqueVisitor,(Visitor)(Clique)(Graph))
+        {
+            BOOST_CONCEPT_USAGE(CliqueVisitor)
+            {
+                vis.clique(k, g);
+            }
+        private:
+            Visitor vis;
+            Graph g;
+            Clique k;
+        };
+}
+
+    using boost::concepts::VertexIndexGraphConcept;
+    using boost::concepts::EdgeIndexGraphConcept;
     using boost::concepts::NumericValueConcept;
     using boost::concepts::DistanceMeasureConcept;
     using boost::concepts::DegreeMeasureConcept;
+    using boost::concepts::CycleVisitorConcept;
+    using boost::concepts::CliqueVisitorConcept;
 }
 #include <boost/concept/detail/concept_undef.hpp>
 

Modified: sandbox/SOC/2007/graphs/boost/graph/tiernan_all_cycles.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/tiernan_all_cycles.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/tiernan_all_cycles.hpp	2007-08-20 13:48:45 EDT (Mon, 20 Aug 2007)
@@ -8,10 +8,10 @@
 #define BOOST_GRAPH_CYCLE_HXX
 
 #include <vector>
-#include <limits>
 
-#include <boost/utility.hpp>
+#include <boost/graph/new_graph_concepts.hpp>
 #include <boost/graph/graph_traits.hpp>
+#include <boost/graph/properties.hpp>
 
 namespace boost
 {
@@ -64,17 +64,26 @@
 
     struct cycle_visitor
     {
-        template <class Vertex, class Graph>
-        inline void start_vertex(Vertex v, Graph& g)
+        template <typename Path, typename Graph>
+        inline void cycle(const Path& p, const Graph& g)
         { }
+    };
 
-        template <class Vertex, class Graph>
-        inline void finish_vertex(Vertex v, Graph& g)
+    struct min_max_cycle_visitor
+    {
+        min_max_cycle_visitor(std::size_t& min, std::size_t& max)
+            : minimum(min), maximum(max)
         { }
 
-        template <class Path, class Graph>
-        inline void cycle(const Path& p, Graph& g)
-        { }
+        template <typename Path, typename Graph>
+        inline void cycle(const Path& p, const Graph& g)
+        {
+            std::size_t len = p.size();
+            minimum = std::min(minimum, len);
+            maximum = std::max(maximum, len);
+        }
+        std::size_t& minimum;
+        std::size_t& maximum;
     };
 
     namespace detail
@@ -112,6 +121,8 @@
                         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
@@ -135,6 +146,7 @@
         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;
 
@@ -162,6 +174,7 @@
                     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;
@@ -190,6 +203,7 @@
         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
@@ -215,21 +229,24 @@
             }
         }
 
-        template <typename Graph, typename Vertex, typename Visitor>
+        template <typename Graph, typename Visitor>
         inline void
         all_cycles_from_vertex(const Graph& g,
-                               Vertex v,
+                               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());
-            const Vertex null = graph_traits<Graph>::null_vertex();
+            Vertex null = graph_traits<Graph>::null_vertex();
 
             // each path investigation starts at the ith vertex
             p.push_back(v);
@@ -267,6 +284,7 @@
                        std::size_t minlen,
                        std::size_t maxlen)
     {
+        function_requires< VertexListGraphConcept<Graph> >();
         typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
 
         VertexIterator i, end;
@@ -292,6 +310,36 @@
                            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;
+        min_max_cycle_visitor vis(min, max);
+        tiernan_all_cycles(g, vis);
+
+        // 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;
+    }
 }
 
 #endif