Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-01-30 09:42:54

0001 //=======================================================================
0002 // Copyright 2002 Indiana University.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 
0010 #ifndef BOOST_CREATE_CONDENSATION_GRAPH_HPP
0011 #define BOOST_CREATE_CONDENSATION_GRAPH_HPP
0012 
0013 #include <boost/graph/graph_traits.hpp>
0014 #include <boost/property_map/property_map.hpp>
0015 
0016 namespace boost
0017 {
0018 
0019 template < typename Graph, typename ComponentLists, typename ComponentNumberMap,
0020     typename CondensationGraph, typename EdgeMultiplicityMap >
0021 void create_condensation_graph(const Graph& g, const ComponentLists& components,
0022     ComponentNumberMap component_number, CondensationGraph& cg,
0023     EdgeMultiplicityMap edge_mult_map)
0024 {
0025     typedef typename graph_traits< Graph >::vertex_descriptor vertex;
0026     typedef typename graph_traits< Graph >::vertices_size_type size_type;
0027     typedef
0028         typename graph_traits< CondensationGraph >::vertex_descriptor cg_vertex;
0029     std::vector< cg_vertex > to_cg_vertex(components.size());
0030     for (size_type s = 0; s < components.size(); ++s)
0031         to_cg_vertex[s] = add_vertex(cg);
0032 
0033     for (size_type si = 0; si < components.size(); ++si)
0034     {
0035         cg_vertex s = to_cg_vertex[si];
0036         std::vector< cg_vertex > adj;
0037         for (size_type i = 0; i < components[si].size(); ++i)
0038         {
0039             vertex u = components[s][i];
0040             typename graph_traits< Graph >::adjacency_iterator v, v_end;
0041             for (boost::tie(v, v_end) = adjacent_vertices(u, g); v != v_end;
0042                  ++v)
0043             {
0044                 cg_vertex t = to_cg_vertex[component_number[*v]];
0045                 if (s != t) // Avoid loops in the condensation graph
0046                     adj.push_back(t);
0047             }
0048         }
0049         std::sort(adj.begin(), adj.end());
0050         if (!adj.empty())
0051         {
0052             size_type i = 0;
0053             cg_vertex t = adj[i];
0054             typename graph_traits< CondensationGraph >::edge_descriptor e;
0055             bool inserted;
0056             boost::tie(e, inserted) = add_edge(s, t, cg);
0057             put(edge_mult_map, e, 1);
0058             ++i;
0059             while (i < adj.size())
0060             {
0061                 if (adj[i] == t)
0062                     put(edge_mult_map, e, get(edge_mult_map, e) + 1);
0063                 else
0064                 {
0065                     t = adj[i];
0066                     boost::tie(e, inserted) = add_edge(s, t, cg);
0067                     put(edge_mult_map, e, 1);
0068                 }
0069                 ++i;
0070             }
0071         }
0072     }
0073 }
0074 
0075 template < typename Graph, typename ComponentLists, typename ComponentNumberMap,
0076     typename CondensationGraph >
0077 void create_condensation_graph(const Graph& g, const ComponentLists& components,
0078     ComponentNumberMap component_number, CondensationGraph& cg)
0079 {
0080     create_condensation_graph(
0081         g, components, component_number, cg, dummy_property_map());
0082 }
0083 
0084 } // namespace boost
0085 
0086 #endif // BOOST_CREATE_CONDENSATION_GRAPH_HPP