#include <iostream>
#include<boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/filtered_graph.hpp>

namespace boost {
  enum vertex_component_t { vertex_component = 111 };
  BOOST_INSTALL_PROPERTY(vertex, component);
}

using namespace boost;

template <typename ComponentMap>
struct vertexComponent {

  vertexComponent() {}

  vertexComponent(ComponentMap component, int f_component) : m_component(component), m_f_component(f_component) {}

  template <typename Vertex>
  bool operator()(const Vertex& v) const {
    return (get(m_component, v) == m_f_component);
  }

  ComponentMap m_component;
  int m_f_component;
};

template <typename ComponentMap, typename Graph>
struct edgeComponent {

  edgeComponent() {}

  edgeComponent(ComponentMap component, Graph g, int f_component) :  m_component(component), m_g(g), m_f_component(f_component) {}

  template <typename Edge>
  bool operator()(const Edge& e) const {
    return (get(m_component, source(e, m_g)) == m_f_component) &&
           (get(m_component, target(e, m_g)) == m_f_component);
  }

  ComponentMap m_component;
  Graph m_g;
  int m_f_component;
};

int main(int argc, char ** argv) {

  typedef adjacency_list<vecS, vecS, undirectedS,
                         property<vertex_component_t, int> > Graph;

  typedef property_map<Graph, vertex_component_t>::type ComponentMap;
  typedef filtered_graph<Graph,
                         edgeComponent<ComponentMap, Graph>,
                         vertexComponent<ComponentMap> > FilteredGraph;
  
  graph_traits < Graph >::vertex_iterator vi, vi_end;
  graph_traits < Graph >::out_edge_iterator oei, oei_end;
  graph_traits < FilteredGraph >::vertex_iterator fvi, fvi_end;
  graph_traits < FilteredGraph >::out_edge_iterator foei, foei_end;

  enum { A, B, C, D, E, F, G, H, I, N };
  const char* name = "ABCDEFGHI";
  Graph g(N);
  add_edge(A, B, g);
  add_edge(C, D, g);
  add_edge(D, E, g);
  add_edge(E, C, g);
  add_edge(F, A, g);
  add_edge(F, B, g);
  add_edge(G, H, g);
  add_edge(G, I, g);
  add_edge(H, I, g);

  std::cout<<std::endl<<"Graph out-edges:"<<std::endl;
  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
    std::cout<<name[*vi]<<" outedges - ";
    for(tie(oei, oei_end)=out_edges(*vi, g); oei != oei_end; ++oei) {
      std::cout<<name[source(*oei, g)]<<"-->"<<name[target(*oei, g)]<<"  ";
    }
    std::cout<<std::endl;
  }
  std::cout<<std::endl;

  std::vector<int> component(N);
  int numComponents = connected_components(g,
					   make_iterator_property_map(component.begin(),
								      get(vertex_index, g)));
  std::cout<<"Graph has "<<numComponents<<" components."<<std::endl<<std::endl;
  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) put(vertex_component, g, *vi, component[*vi]);

  for(int i=0; i<numComponents; i++) {
    edgeComponent<ComponentMap, Graph> efilter(get(vertex_component, g), g, i);
    vertexComponent<ComponentMap> vfilter(get(vertex_component, g), i);
    FilteredGraph fg(g, efilter, vfilter);

    std::cout<<"Filtered graph (component "<<i<<") out-edges:"<<std::endl;
    for (tie(fvi, fvi_end) = vertices(fg); fvi != fvi_end; ++fvi) {    
      std::cout<<name[*fvi]<<" outedges - ";    
      for(tie(foei, foei_end)=out_edges(*fvi, fg); foei != foei_end; ++foei) {
	std::cout<<name[source(*foei, fg)]<<"-->"<<name[target(*foei, fg)]<<"  ";
      }
      std::cout<<std::endl;
    }
    std::cout<<std::endl;
  }

  return EXIT_SUCCESS;
}