compressed_row_matrix_graph.hpp

图论必用

			typedef std::pair < typename g_traits::edge_iterator, typename g_traits::edge_iterator >
				edges_ret;
		};
	}

	template <class RowIter, class ColIter, class ValIter>
	inline typename boost::graph_traits< yasmic::compressed_row_matrix<RowIter, ColIter, ValIter> >::vertices_size_type
		num_vertices(const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g) 
	{
		return nrows(g);
	}  

	template <class RowIter, class ColIter, class ValIter>
	inline typename boost::graph_traits< yasmic::compressed_row_matrix<RowIter, ColIter, ValIter> >::vertices_size_type
		num_edges(const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g)
	{
		return nnz(g);
	}  

	template <class RowIter, class ColIter, class ValIter>
	inline typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::vertex_descriptor
	source(
		typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::edge_descriptor e,
		const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g)
	{
		return (e._row);
	}

	template <class RowIter, class ColIter, class ValIter>
	inline typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::vertex_descriptor
	target(
		typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::edge_descriptor e,
		const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g)
	{
		return (e._column);
	}


	template <class RowIter, class ColIter, class ValIter>
	inline typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::out_edges_ret
		out_edges(typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::vertex_descriptor v,
			  const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g)
	{
		return (row_nonzeros(v,g));

		/*typedef typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::out_edge_iterator Iter;
		typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::out_edges_ret return_type;

		typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::smatrix_traits::row_nonzero_iterator rnzi, rnziend;

		tie(rnzi, rnziend) = yasmic::row_nonzeros(v, g);

		typedef typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::out_edge_iterator iter;

		return std::make_pair(iter(rnzi), iter(rnziend));*/


		/*typedef typename detail::val_out_edge_iter<EdgeList>::type Iter;
		typedef typename detail::val_out_edge_ret<EdgeList>::type return_type;
		return return_type(Iter(v, ++g[v].begin(), *(g[v].begin())),
    		Iter(v, g[v].end(), *(g[v].begin())));*/
	}

	template <class RowIter, class ColIter, class ValIter>
	typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::degree_size_type
	out_degree(
		typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::vertex_descriptor v,
		const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g)
	{
		return (g._rstart[v+1] - g._rstart[v]);

		/*typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::smatrix_traits::row_nonzero_iterator rnzi, rnziend;

		tie(rnzi, rnziend) = yasmic::row_nonzeros(v, g);

		typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::smatrix_traits::size_type rval = 0;
		while (rnzi != rnziend) { ++rnzi; ++rval; }

		return (rval);*/


	}

	template <class RowIter, class ColIter, class ValIter>
	inline typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::adjacent_ret 
		adjacent_vertices(
			typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::vertex_descriptor v,
			const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g)
	{
		typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::smatrix_traits::row_nonzero_iterator rnzi, rnziend;

		tie(rnzi, rnziend) = yasmic::row_nonzeros(v, g);

		typedef typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::adjacency_iterator iter;

		return std::make_pair(iter(rnzi), iter(rnziend));
	}

	// source() and target() already provided for pairs in graph_traits.hpp

	template <class RowIter, class ColIter, class ValIter>
	inline typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::vertices_ret 
		vertices(const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g)
	{
		//typedef typename boost::integer_range<typename EdgeList::value_type>
		//::iterator Iter;
		typedef typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::vertex_iterator iter;
		return std::make_pair(iter(0), iter(nrows(g)));
	}

	template <class RowIter, class ColIter, class ValIter>
	inline typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::edges_ret 
		edges(const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g)
	{
		//typedef typename boost::integer_range<typename EdgeList::value_type>
		//::iterator Iter;
		//typedef typename impl::crm_graph_ret<RowIter, ColIter, ValIter>::g_traits::vertex_iterator iter;
		//return std::make_pair(iter(0), iter(nrows(g)));

		return (nonzeros(g));
	}

	template <class RowIter, class ColIter, class ValIter>
	class compressed_row_matrix_graph_id_map
		: public put_get_helper<
			typename yasmic::smatrix_traits< typename impl::crm_graph<RowIter, ColIter, ValIter>::type >::size_type,
    		compressed_row_matrix_graph_id_map<RowIter, ColIter, ValIter> >
	{
	protected:
  		typedef typename yasmic::smatrix_traits< typename impl::crm_graph<RowIter, ColIter, ValIter>::type >::size_type S;
	public:
  		typedef readable_property_map_tag category;
  		typedef S value_type;
  		typedef S reference;
		typedef typename graph_traits< typename impl::crm_graph<RowIter, ColIter, ValIter>::type >::edge_descriptor key_type;
		//typedef typename impl::crm_graph_edge<RowIter, ColIter, ValIter>::type key_type;
  		//typedef typename detail::crm_graph_edge<RowIter, ColIter, ValIter>::type key_type;
	  	
  		compressed_row_matrix_graph_id_map() { }
  		template <class T> S operator [] (T x) const { return x._nzi; }
	};


	  
	template <class RowIter, class ColIter, class ValIter>
	inline identity_property_map get(vertex_index_t, 
		const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g)
	{
  		identity_property_map pmap;
  		return (pmap);	
	}
	  
	template <class RowIter, class ColIter, class ValIter>
	inline compressed_row_matrix_graph_id_map<RowIter, ColIter, ValIter> get(edge_index_t, 
  		const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g)
	{
  		compressed_row_matrix_graph_id_map<RowIter, ColIter, ValIter> pmap;
  		//return (vector_graph_id_map<EdgeList>());
  		return (pmap);
	}

	
	  
	template <class Tag>
	struct compressed_row_matrix_graph_property_map { };
	  
	template <>
	struct compressed_row_matrix_graph_property_map<vertex_index_t> {
  		template <class RowIter, class ColIter, class ValIter>
  		struct bind_ {
  			typedef identity_property_map type;
  			typedef identity_property_map const_type;
  		};
	};
	  
	template <>
	struct compressed_row_matrix_graph_property_map<edge_index_t> {
  		template <class RowIter, class ColIter, class ValIter>
  		struct bind_ {
  			typedef compressed_row_matrix_graph_id_map<RowIter, ColIter, ValIter> type;
  			typedef compressed_row_matrix_graph_id_map<RowIter, ColIter, ValIter> const_type;
  		};
	};

	template <>
	struct compressed_row_matrix_graph_property_map<edge_weight_t> {
		template <class RowIter, class ColIter, class ValIter>
		struct bind_ {
			typedef iterator_property_map<ValIter, compressed_row_matrix_graph_id_map<RowIter, ColIter, ValIter> > type;
			typedef iterator_property_map<ValIter, compressed_row_matrix_graph_id_map<RowIter, ColIter, ValIter> > const_type;
		};
	};
	  
	template <class RowIter, class ColIter, class ValIter, class Tag>
	struct property_map<yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>, Tag> {
  		typedef typename compressed_row_matrix_graph_property_map<Tag>::template 
  			bind_<RowIter, ColIter, ValIter> map_gen;
  		typedef typename map_gen::type type;
  		typedef typename map_gen::const_type const_type;
	};
	
	template <class RowIter, class ColIter, class ValIter>
	inline typename property_map<yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>, edge_weight_t>::type
		get(edge_weight_t, const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g)
	{
  		return (make_iterator_property_map(g.begin_values(), get(edge_index, g)));
	}

    /*template <class Tag, class RowIter, class ColIter, class ValIter, class Key>
    inline typename typename property_map<yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>, Tag>::value_type
		get(Tag t, const yasmic::compressed_row_matrix<RowIter, ColIter, ValIter>& g, Key key)
	{
        return get(get(t, g), key);
  		//return (make_iterator_property_map(g.begin_values(), get(edge_index, g)));
	}*/

}

#if _MSC_VER >= 1400
	// disable the warning for deprecated c++ commands
	#pragma warning( pop )
#endif // _MSC_VER >= 1400

#endif // YASMIC_COMPRESSED_ROW_MATRIX_GRAPH