GraphView for subgraphs

[filchristou]

I am just thinking out loud here..
Quite commonly I need to deal with subgraphs (i.e. induced_subgraph) or merged graphs (i.e. merge_vertices).
It's quite handy to have the bank ! variations (i.e. merge_vertices vs merge_vertices!), but they are not consistent across Graphs.jl. E.g. induced_subgraph doesn't have a corresponding bank version.

Sometimes I want to operate on a resulted converted graph, without losing the original but still influencing it.
It's like a combination of a bank ! and without.
This basically means having a view of the original graph.
The whole idea is very similar to the DataFrames.jl view https://dataframes.juliadata.org/stable/man/basics/#Views

That might be more relevant for Metagraphs, since graphs will carry data that can be shallow- or deep-copied.
A view, e.g., should implement shallow copying (if not by reference)

Also it might be useful for different indexing, which might enable us to get rid of the vmap property that some functions return.

I know it's a lot; I just wanted to share since now a lot of discussions are taking place for a Graphs.jl 2.0
I am still not 100% persuaded on this, but it looks to me like there could be some value.
What do you think and could you see different use cases ?

[henrik-wolf]

One of the main gripes I have heard from people trying to get into graphs in julia were the comparably strange returns where you sometimes get arrays of arrays and sometimes a graph of a different type than you put in (bfs_tree and connected_components come to mind).

In my opinion, having graph views could really help making the whole experience a bit more "intuitive" and coherent. I was thinking about proposing this myself, but never found the time...
So: thank you for the proposition, I gladly second this motion. (Also, I volunteer myself as a tribute, should we decide we want to do something with that.)

[filchristou]

Thanks for mentioning bfs_tree; it really fits into that. Another ecosystem inconsistency is that bfs_tree returns a graph while all the spanning tree algorithms return a vector of edges. I think they should return the same type and a graph view looks indeed appealing.

What would you expect from connected_components to return though ?

[henrik-wolf]

Ah! Yes. Spanning trees is what I was actually looking for. I would say that connected_components could (should?) return a vector of views into the original graph, each corresponding to one component.

[filchristou]

spanning trees result as vector of edges is also touched elsewhere e.g. JuliaGraphs/Graphs.jl#130

[filchristou]

I would say that connected_components could (should?) return a vector of views into the original graph

I think that might be a bit of an overkill though. I mean, if the function was called connected_subgraphs I would understand, but right now I cannot see a better way around a vector of vector indices.

[henrik-wolf]

Fair. Maybe having the option of constructing a view from vertices like GraphView(g, verts) could be a compromise. Nonetheless, there still remain many places which could benefit from some kind of graph view.

[etiennedeg]

Related: JuliaGraphs/Graphs.jl#12

[jfb-h]

Just to chime in with another data point: GraphTool supports graph views and in-place filters. Haven't used that myself yet, but it seems like an interesting feature.

[gdalle]

Related:

• Standardized output for shortest path algorithms Graphs.jl#77
• Coherent return types for Kruskal vs Prim Graphs.jl#130