//====== file_dep_graph.h ======
/*
#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <vector>
#include <iterator>
#include <numeric>
using namespace std;
#include <boost/graph/adjacency_list.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/property_iter_range.hpp>
using namespace boost;
*/
//==============================
#include "file_dep_graph.h"
typedef string Name;
typedef float CompileCost;
namespace boost {
enum vertex_compile_cost_t { vertex_compile_cost = 111 };
BOOST_INSTALL_PROPERTY( vertex, compile_cost );
}
typedef adjacency_list<
listS,
listS,
directedS,
property<vertex_name_t, Name,
property<vertex_compile_cost_t, CompileCost,
property<vertex_distance_t, float,
property<vertex_color_t, default_color_type> > > >,
property<edge_weight_t, float>
> file_dep_graph2;
typedef graph_traits<file_dep_graph2>::vertex_descriptor vertex_d;
typedef graph_traits<file_dep_graph2>::vertex_iterator vertex_i;
typedef graph_traits<file_dep_graph2>::edge_descriptor edge_d;
typedef graph_traits<file_dep_graph2>::edge_iterator edge_i;
typedef property_map<file_dep_graph2, vertex_name_t>::type name_map_t;
typedef property_map<file_dep_graph2, vertex_compile_cost_t>::type compile_cost_map_t;
typedef property_map<file_dep_graph2, vertex_distance_t>::type distance_map_t;
typedef property_map<file_dep_graph2, vertex_color_t>::type color_map_t;
typedef map<Name, vertex_d> Name2Vertex;
typedef pair<Name, CompileCost> TargetProperties;
typedef vector<TargetProperties> TargetsProperties;
typedef istream_iterator<TargetProperties> TargetsPropertiesInputIterator;
typedef ostream_iterator<TargetProperties> TargetsPropertiesOutputIterator;
namespace std {
istream& operator>> ( istream& is, TargetProperties& target_propertices )
{
is >> target_propertices.first >> target_propertices.second;
return is;
}
ostream& operator<< ( ostream& os, const TargetProperties& target_propertices )
{
os << target_propertices.first << ' ' << target_propertices.second;
return os;
}
}
typedef pair<Name, Name> Dependency;
typedef vector<Dependency> Dependencies;
typedef istream_iterator<Dependency> DependenciesInputIterator;
typedef ostream_iterator<Dependency> DependenciesOutputIterator;
namespace std {
istream& operator>> ( istream& is, Dependency& dependency )
{
is >> dependency.first >> dependency.second;
return is;
}
ostream& operator<< ( ostream& os, const Dependency& dependency)
{
os << dependency.first << ' ' << dependency.second;
return os;
}
}
template <typename Graph, typename ColorMap, typename Visitor>
void dfs_v2( const Graph& g,
typename graph_traits<Graph>::vertex_desciptor u,
ColorMap color, Visitor vis )
{
typedef typename property_traits<ColorMap>::value_type color_type;
typedef color_traits<color_type> ColorT;
color[ u ] = ColorT::gray();
vis.discover_vertex( u, g );
typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
for( tie( ei, ei_end ) = out_edges( u, g ); ei != ei_end; ei++ )
if( color[ target( *ei, g ) ] = ColorT::white() )
{
vis.tree_edge( *ei, g );
dfs_v2( g, target( *ei, g ), color, vis );
}
else
if( color[ target( *ei, g ) ] == ColorT::gray() )
vis.back_edge( *ei, g );
else
vis.forward_or_cross_edge( *ei, g );
color[ u ] = ColorT::black();
vis.finish_vertex( u, g );
}
template <typename Graph, typename Visitor, typename ColorMap>
void generic_dfs_v2( const Graph& g, Visitor vis, ColorMap color )
{
typedef color_traits<typename property_traits<ColorMap>::value_type> ColorT;
typename graph_traits<Graph>::vertex_iterator vi, vi_end;
for( tie( vi, vi_end ) = vertices( g ); vi != vi_end; vi++ )
color[ *vi ] = ColorT::white();
for( tie( vi, vi_end ) = vertices( g ); vi != vi_end; vi++ )
if( color[ *vi ] == ColorT::white() )
dfs_v2( g, *vi, color, vis );
}
struct default_dfs_visitor {
template <typename V, typename G>
void discover_vertex( V, const G& ) {}
template <typename E, typename G>
void tree_edge( E, const G& ) {}
template <typename E, typename G>
void back_edge( E, const G& ) {}
template <typename E, typename G>
void forward_or_cross_edge( E, const G& ) {}
template <typename V, typename G>
void finish_vertex( V, const G& ) {}
};
template <typename OutputIterator>
struct topo_visitor : public default_dfs_visitor {
topo_visitor( OutputIterator& order )
:topo_order( order ) {}
template <typename Graph>
void finish_vertex( typename graph_traits<Graph>::vertex_descriptor u, const Graph& )
{
*topo_order++ = u;
}
OutputIterator& topo_order;
};
template <typename Graph, typename OutputIterator, typename ColorMap>
void topo_sort( const Graph& g, OutputIterator topo_order, ColorMap color )
{
topo_visitor<OutputIterator> vis( topo_order );
generic_dfs_v2( g, vis, color );
}
int main()
{
// ====== input data from file =======
ifstream ifile( "makefile_target_properties.dat" );
TargetsPropertiesInputIterator it( ifile ), it_end;
TargetsProperties targets_properties( it, it_end );
ifile.close();
ifstream ifile_dep( "makefile_dependencies.dat" );
DependenciesInputIterator it_dep( ifile_dep ), it_dep_end;
Dependencies dependencies( it_dep, it_dep_end );
ifile_dep.close();
// ======= create graph ======
file_dep_graph2 g( targets_properties.size() );
vertex_i vi, vi_end;
tie( vi, vi_end ) = vertices( g );
Name2Vertex name2vertex;
for( int i = 0; vi != vi_end; vi++, i++ )
name2vertex[ targets_properties[ i ].first ] = *vi;
for( int i = 0; i < dependencies.size(); i++ )
add_edge( name2vertex[ dependencies[ i ].first ],
name2vertex[ dependencies[ i ].second ], g );
// ======== set properties ========
tie( vi, vi_end ) = vertices( g );
name_map_t name_map = get( vertex_name, g ) ;
for( int i = 0; vi != vi_end; vi++, i++ )
name_map[ *vi ] = targets_properties[ i ].first;
tie( vi, vi_end ) = vertices( g );
compile_cost_map_t compile_cost_map = get( vertex_compile_cost, g );
for( int i = 0; vi != vi_end; vi++, i++ )
compile_cost_map[ *vi ] = targets_properties[ i ].second;
graph_property_iter_range<file_dep_graph2, vertex_name_t>::iterator ni, ni_end;
tie( ni, ni_end ) = get_property_iter_range( g, vertex_name );
for( ;ni != ni_end; ni++ )
cout << *ni << endl;
graph_property_iter_range<file_dep_graph2, vertex_compile_cost_t>::iterator ci, ci_end;
tie( ci, ci_end ) = get_property_iter_range( g, vertex_compile_cost );
cout << accumulate( ci, ci_end, 0.0 ) << endl;
vector<vertex_d> order( num_vertices( g ) );
color_map_t color_map = get( vertex_color, g );
topo_sort( g, order.rbegin(), color_map );
return 0;
}
[root@zml file_dep_graph]#g++ -o file_dep_graph2 file_dep_graph2.cpp
file_dep_graph2.cpp: In function 'void generic_dfs_v2(const Graph&, Visitor, ColorMap) [with Graph = boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::property<boost::vertex_compile_cost_t, float, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_color_t, boost::default_color_type, boost::no_property> > > >, boost::property<boost::edge_weight_t, float, boost::no_property>, boost::no_property, boost::listS>, Visitor = topo_visitor<std::reverse_iterator<__gnu_cxx::__normal_iterator<void**, std::vector<void*, std::allocator<void*> > > > >, ColorMap = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::property<boost::vertex_compile_cost_t, float, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_color_t, boost::default_color_type, boost::no_property> > > >, boost::property<boost::edge_weight_t, float, boost::no_property>, boost::no_property, boost::listS>, boost::default_color_type, boost::default_color_type&, boost::vertex_color_t>]':
file_dep_graph2.cpp:165: instantiated from 'void topo_sort(const Graph&, OutputIterator, ColorMap) [with Graph = file_dep_graph2, OutputIterator = std::reverse_iterator<__gnu_cxx::__normal_iterator<void**, std::vector<void*, std::allocator<void*> > > >, ColorMap = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::property<boost::vertex_compile_cost_t, float, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_color_t, boost::default_color_type, boost::no_property> > > >, boost::property<boost::edge_weight_t, float, boost::no_property>, boost::no_property, boost::listS>, boost::default_color_type, boost::default_color_type&, boost::vertex_color_t>]'
file_dep_graph2.cpp:225: instantiated from here
file_dep_graph2.cpp:132: error: no matching function for call to 'dfs_v2(const boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::property<boost::vertex_compile_cost_t, float, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_color_t, boost::default_color_type, boost::no_property> > > >, boost::property<boost::edge_weight_t, float, boost::no_property>, boost::no_property, boost::listS>&, void*&, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::property<boost::vertex_compile_cost_t, float, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_color_t, boost::default_color_type, boost::no_property> > > >, boost::property<boost::edge_weight_t, float, boost::no_property>, boost::no_property, boost::listS>, boost::default_color_type, boost::default_color_type&, boost::vertex_color_t>&, topo_visitor<std::reverse_iterator<__gnu_cxx::__normal_iterator<void**, std::vector<void*, std::allocator<void*> > > > >&)'