write_graphviz requires more concepts than the documentation states

[anonymous]

I wanted to use write_graphviz with my custom graph adapter that implements VertexListGraph as well as IncidenceGraph. The documentation states, that write_graphviz only requires a VertexListGraph. But inside, it uses an edge_iterator, and calls edges(g), both of which belong to the EdgeListGraph.

This discrepancy was confirmed at the boost mailing list.

First, the documentation should be updated.

But then I would also suggest to provide a second specialization for IncidenceGraph that calls out_deges() for each vertex instead of edges().

When I find time, I will prepare some code for my proposal.

[richi@…]

Here's the code that I had in mind :

template <typename EdgeListGraph, typename VertexPropertiesWriter,

typename EdgePropertiesWriter, typename GraphPropertiesWriter, typename VertexID>

static inline void write_graphviz_dispatch(std::ostream& out, const EdgeListGraph& g,

VertexPropertiesWriter vpw, EdgePropertiesWriter epw, GraphPropertiesWriter gpw, VertexID vertex_id, edge_list_graph_tag)

{

typedef typename graph_traits<EdgeListGraph>::directed_category cat_type; typedef graphviz_io_traits<cat_type> Traits; std::string name = "G"; out << Traits::name() << " " << name << " {" << std::endl;

gpw(out); print graph properties

typename graph_traits<EdgeListGraph>::vertex_iterator i, end;

for(tie(i,end) = vertices(g); i != end; ++i) {

out << get(vertex_id, *i); vpw(out, *i); print vertex attributes out << ";" << std::endl;

} typename graph_traits<EdgeListGraph>::edge_iterator ei, edge_end; for(tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {

out << get(vertex_id, source(*ei, g)) << Traits::delimiter() << get(vertex_id, target(*ei, g)) << " "; epw(out, *ei); print edge attributes out << ";" << std::endl;

} out << "}" << std::endl;

}

template <typename VertexListGraph, typename VertexPropertiesWriter,

typename EdgePropertiesWriter, typename GraphPropertiesWriter, typename VertexID>

inline void write_graphviz_dispatch(std::ostream& out, const VertexListGraph& g,

VertexPropertiesWriter vpw, EdgePropertiesWriter epw, GraphPropertiesWriter gpw, VertexID vertex_id, vertex_list_graph_tag)

{

typedef typename graph_traits<VertexListGraph>::directed_category cat_type; typedef graphviz_io_traits<cat_type> Traits; std::string name = "G"; out << Traits::name() << " " << name << " {" << std::endl;

gpw(out); print graph properties

typename graph_traits<VertexListGraph>::vertex_iterator i, end;

for(tie(i,end) = vertices(g); i != end; ++i) {

out << get(vertex_id, *i); vpw(out, *i); print vertex attributes out << ";" << std::endl;

}

for(tie(i,end) = vertices(g); i != end; ++i) {

typename graph_traits<VertexListGraph>::out_edge_iterator ei, edge_end; for(tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei) {

out << get(vertex_id, source(*ei, g)) << Traits::delimiter() << get(vertex_id, target(*ei, g)) << " "; epw(out, *ei); print edge attributes out << ";" << std::endl;

}

} out << "}" << std::endl;

}

dispatcher template <typename Graph, typename VertexPropertiesWriter,

typename EdgePropertiesWriter, typename GraphPropertiesWriter, typename VertexID>

inline void write_graphviz(std::ostream& out, const Graph& g,

VertexPropertiesWriter vpw, EdgePropertiesWriter epw, GraphPropertiesWriter gpw, VertexID vertex_id)

{

typedef typename graph_traits<Graph>::traversal_category cat_type; function_requires<IncidenceGraphConcept<Graph> >();

write_graphviz_dispatch(out, g, vpw, epw, gpw, vertex_id, cat_type());

}

works for me, but it's not extensively tested...

[Richard Ulrich <richi@…>]

looks better with the code tag :

template <typename EdgeListGraph, typename VertexPropertiesWriter,
	typename EdgePropertiesWriter, typename GraphPropertiesWriter,
	typename VertexID>
static inline void write_graphviz_dispatch(std::ostream& out, const EdgeListGraph& g,
	VertexPropertiesWriter vpw,
	EdgePropertiesWriter epw,
	GraphPropertiesWriter gpw,
	VertexID vertex_id,
	edge_list_graph_tag)
{
	typedef typename graph_traits<EdgeListGraph>::directed_category cat_type;
	typedef graphviz_io_traits<cat_type> Traits;
	std::string name = "G";
	out << Traits::name() << " " << name << " {" << std::endl;

	gpw(out); //print graph properties

	typename graph_traits<EdgeListGraph>::vertex_iterator i, end;

	for(tie(i,end) = vertices(g); i != end; ++i) {
		out << get(vertex_id, *i);
		vpw(out, *i); //print vertex attributes
		out << ";" << std::endl;
	}
	typename graph_traits<EdgeListGraph>::edge_iterator ei, edge_end;
	for(tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {
		out << get(vertex_id, source(*ei, g)) << Traits::delimiter() << get(vertex_id, target(*ei, g)) << " ";
		epw(out, *ei); //print edge attributes
		out << ";" << std::endl;
	}
	out << "}" << std::endl;
}


template <typename VertexListGraph, typename VertexPropertiesWriter,
	typename EdgePropertiesWriter, typename GraphPropertiesWriter,
	typename VertexID>
inline void write_graphviz_dispatch(std::ostream& out, const VertexListGraph& g,
	VertexPropertiesWriter vpw,
	EdgePropertiesWriter epw,
	GraphPropertiesWriter gpw,
	VertexID vertex_id,
	vertex_list_graph_tag)
{
	typedef typename graph_traits<VertexListGraph>::directed_category cat_type;
	typedef graphviz_io_traits<cat_type> Traits;
	std::string name = "G";
	out << Traits::name() << " " << name << " {" << std::endl;

	gpw(out); //print graph properties

	typename graph_traits<VertexListGraph>::vertex_iterator i, end;

	for(tie(i,end) = vertices(g); i != end; ++i) {
		out << get(vertex_id, *i);
		vpw(out, *i); //print vertex attributes
		out << ";" << std::endl;
	}

	for(tie(i,end) = vertices(g); i != end; ++i) 
	{
		typename graph_traits<VertexListGraph>::out_edge_iterator ei, edge_end;
		for(tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei) {
			out << get(vertex_id, source(*ei, g)) << Traits::delimiter() << get(vertex_id, target(*ei, g)) << " ";
			epw(out, *ei); //print edge attributes
			out << ";" << std::endl;
		}
	}
	out << "}" << std::endl;
}

// dispatcher
template <typename Graph, typename VertexPropertiesWriter,
	typename EdgePropertiesWriter, typename GraphPropertiesWriter,
	typename VertexID>
inline void write_graphviz(std::ostream& out, const Graph& g,
	VertexPropertiesWriter vpw,
	EdgePropertiesWriter epw,
	GraphPropertiesWriter gpw,
	VertexID vertex_id)
{
	typedef typename graph_traits<Graph>::traversal_category cat_type;
	function_requires<IncidenceGraphConcept<Graph> >();

	write_graphviz_dispatch(out, g, vpw, epw, gpw, vertex_id, cat_type());
}

[Andrew Sutton]

The specialization proposed by the reporter is somewhat interesting since it only applies to directed graphs. Using the suggested specialization with an undirected graph will cause each edge to be given twice. It may be worth considering a DirectedGraph concept that embodies this property of the out_edges() function. Conversely, an UndirectedGraph concept may provide a different guarantee.

However, the proposed solution - as given - won't work.

[Andrew Sutton]

Added a concept assertion on EdgeListGraph to the core write_graphviz function to ensure that it actually requires the concept. Updated documentation to reflect requirements on VertexAndEdgeListGraph (r54995).