Cutting graphs at bridges

Specific Domains Graphs
1

I’ve got a directed MetaGraphNext object g, which I’d like to run some algorithms on. I’ve run b = bridges(Graph(g.graph)) (since bridges apparently can’t be computed on a MetaGraph or a directed graph) to get a list of all bridges (edges that would increase the number of connected components if deleted). Now I want to do some modifications based on properties of the two components on either side of each bridge.

I know there’s just a single connected component in the graph before cutting, so cutting at a bridge will always create 2 components.

The things I need to examine include:

  • How many vertices are in each of the 2 components on either side of the bridge?
  • Do all the vertex/edge components on the smaller side have some property (checking some of their Meta information in g.vertex_properties and g.edge_data)

and then I will need to ablate the graph at the bridge (cut off & discard the smaller part) if certain conditions are met. I’m not seeing how to efficiently compute those couple of quantities mentioned above, though. Anyone have any pointers?

BTW, everything I’ve mentioned here basically deals with the graph in an undirected way, but for other reasons my graph is directed, and handling that sometimes seems to get a little dicey too (e.g. the result of bridges() has various edges flipped). I think I’ve got that covered but if I’m missing any conveniences that would help, let me know.

Thanks!

2

I don’t know if it will be efficient, but you can certainly delete each edge, find the connected components and then perform your analysis. Does it scale sufficiently well for your problem size?

3

Why do you say if cannot be computed for MetaGraph? If the MetaGraph is undirected, this should not pose problem. Maybe it can make sense to allow this method for directed graphs (this would return all bridges, not only strong bridges). Note that once ReverseView and UndirectedView by etiennedeg · Pull Request #376 · JuliaGraphs/Graphs.jl · GitHub is merged, you will be able to use an UndirectedView to avoid allocating with Graph.

4

I can give it a shot and test empirically, but I was hoping that some of the work would already have been done by bridges(), or perhaps that I could compute the bridges a different way that gives me more information that I can use for this.

Another idea is something like gdistances(Graph(g.graph), a) .> gdistances(Graph(g.graph), b) where a and b are the endpoints of a bridge. I assume that would be O[n] for each bridge, and the graph is nearly a tree so I generally have O[n] bridges, so O[n^2] total.

5

The issue does seem to be the directedness, as you suggested:

infil> g
Meta graph based on a SimpleDiGraph{Int64} with vertex labels of type String, vertex metadata of type X, edge metadata of type Y, graph metadata given by "", and default weight 1.0

infil> bridges(g)
ERROR: MethodError: no method matching bridges(::Type{IsDirected{…}}, ::MetaGraph{Int64, SimpleDiGraph{…}, String, Union{…}, Vector{…}, String, MetaGraphsNext.var"#11#13", Float64})

Closest candidates are:
  bridges(::Type{SimpleTraits.Not{IsDirected{AG}}}, ::AG) where {T, AG<:AbstractGraph{T}}
   @ Graphs ~/.julia/packages/Graphs/FXxqo/src/biconnectivity/bridge.jl:27

Stacktrace:
 [1] bridges(g::MetaGraph{Int64, SimpleDiGraph{…}, String, Union{…}, Vector{…}, String, MetaGraphsNext.var"#11#13", Float64})
   @ Graphs ~/.julia/packages/SimpleTraits/l1ZsK/src/SimpleTraits.jl:331
 [2] top-level scope
   @ none:1

I had already wondered whether there was a wrapper or flag that could turn a directed graph into an undirected graph without reconstructing it - that would be great!