IsMutable trait

[etiennedeg]

#88, #89, #85 raise the need to have a specific interface for mutable graph. This is useful to explicit the output type of the graph for function returning another graph. As a mutable graph could model any graph structure, the output of these functions would just be a graph of the same type as the input graph. Would fall under the IsMutable trait the graphs implementing [add|remove]_vertex!, [add|remove]_edge! and some non mandatory ones like zero, [add|remove]_vertices!, [add|remove]_edges! (zero could eventually be mandatory).

Maybe that for non mutable graph, we could add a method which would precise the expected return type of the graph under mutation.

There are still some corner cases like functions taking as input an undirected graph and returning a directed one, for which this trait will not help to get it generic.

[simonschoelly]

I wonder if it would make sense to have two different traits - one for mutable vertices, and one for mutable edges? Although I wonder how far it would make sense to have mutable vertices without mutable edges.

And later on also some traits for mutable metadata.

We could make these traits not part of the api, i.e. have them in some experimental submodule, so that we have some space to figure out the right abstraction and would not commit to early.

I also have some ideas how to deal with operators on graphs, when I find some time I will try to write these down in another issue.

[etiennedeg]

I don't understand the purpose of a trait for vertex mutability. Even if we suppose that a type with only vertex mutability might be useful, I don't see much methods that would benefit from this kind of filtering so it's probably better to keep the API simple. Conversely, mutability on edges allows graphs with this trait to be used by any function returning a new graph. It could also make sense to have trait for the mutability on weights. However, I'm not sure for metadata, it seems harder to find a generic answer on what it would mean, which methods we should implement.

[simonschoelly]

Yes, maybe it would make sense to have just a generic mutability trait in the beginning, and then we could add more later if needed.

[gdalle]

This is better than #80 so I'm closing that one.

[filchristou]

The only case I would care about mutability is for performance reasons. Is this the case here, because to me it seems not. Also, can you share a use case where non-mutability is needed ? And why can't a deep-copy be used instead ? Regarding functions returning a graph, we were speculating about a GraphView struct here https://github.com/JuliaGraphs/GraphsBase.jl/issues/8

[simonschoelly]

One example where mutability does not work is SpecialGraphs.jl

Also, not requiring someone to implement {add/remove}_{vertex}{edge!}, would make it easier for someone to quickly implement the graph interface, if they don't need mutability for their graph.