Here are some observations that may help you improve this code.
Fix the obvious errors
The Graph::set_color() routine says that it returns a Color but it doesn't return anything. The obvious fix is to simply add return color; to that function. Alternatively, change the signature to return void. The same problem exists with set_payload.
Iterate over const references where possible
In the to_gv_dot() routine, the for loops should iterate over const references instead of forcing temporary copies. In other words, change the code from this:
for (auto j : i.second) {
to this:
for (auto const &j : i.second) {
Use defaults when sensible
The Vertex operator= is essentially the same as that which would have been generated by the compiler. To reduce the chance of error, it can be simply eliminated. If you wish to make it explicit that this is being done, use this:
Vertex &operator=(Vertex& ) = default;
Also note that it is not necessary to write Vertex<PayloadT> in this context because the compiler can infer that from the context. Omitting it makes it easer for humans to read and understand and eliminates one possibility for error.
Consider adding debug-friendly methods
The Vertex class can be more easily debugged by adding a few lines of code. First this code just below the Color enum:
static const char *colorname[] = { "white", "gray", "black", "red", "none" };
Then these class members in the Vertex class:
const char *get_color_name() const { return colorname[color]; }
friend std::ostream &operator<<(std::ostream &out, const Vertex &v) {
return out << "{ " << v.get_payload() << ", " << v.get_color_name()
<< " }\n";
}
The get_color_name() routine can also be used to enhance the existing output for dot. In the to_gv_dot() routine, the line after the first for can be this:
stm << "\t" << i.first.get_payload() << "[style=filled,fillcolor="
<< i.first.get_color_name() << "];\n";
Have public methods return user-centric values
Graph has a get_size() function which seems like it ought to return the number of vertices or the number of edges, but it does neither. Instead it returns the number of unique nodes which are sources of directed edges to other nodes. It would make more sense for this function to return something such as number of nodes or number of edges which would make sense to the user of the graph.
Fix rm_vertex
The rm_vertex() method of Graph purports to remove a vertex, but in fact, it only eliminates part of the internal data structure. If one has the graph
a -> b -> c
and then calls rm_vertex(b) the resulting graph will be
a -> b
even though the user just asked to delete that vertex. That can't be right.
Consider the user when designing the interface
There is no way to simultaneously set the contents and the color when constructing a Vertex. Also, once a Vertex is created and inserted into a Graph, there's no way to get it back or refer to it.
Avoid using a leading underscore for items in global namespace
As you can read in this answer, global names that begin with an underscore are "reserved to the implementation;" that is, they are for your compiler rather than for you.
Consider providing iterators
An obvious thing to do with a graph is to iterate over edges or nodes. It would be nice for your interface to provide this.
Decide if nodes that differ only in color are actually different
Right now, if two nodes differ only in color, the operator== for the Vertex class reports that they are not equal. However, if two nodes differ only in color, they will be shown on the dot graph as only a single node.