# Cutting graphs at bridges
**URL:** https://discourse.julialang.org/t/cutting-graphs-at-bridges/114533
**Category:** Graphs
**Tags:** graphs
**Created:** [May 21, 2024, 10:38pm UTC](https://discourse.julialang.org/t/cutting-graphs-at-bridges/114533 "2024-05-21T22:38:03Z")
**Posts on this page:** 5
**Page:** 1
### Author:  [@Ken\_Williams](https://discourse.julialang.org/u/Ken_Williams)
#### Post date: [May 21, 2024, 10:38pm UTC](https://discourse.julialang.org/t/cutting-graphs-at-bridges/114533/1 "2024-05-21T22:38:03Z")
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!
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [May 22, 2024, 6:20am UTC](https://discourse.julialang.org/t/cutting-graphs-at-bridges/114533/2 "2024-05-22T06:20:12Z")
> [@Ken\_Williams](#):
>
> I’m not seeing how to efficiently compute those couple of quantities mentioned above, though.
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?
---
### Author:  [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)
#### Post date: [May 22, 2024, 7:58am UTC](https://discourse.julialang.org/t/cutting-graphs-at-bridges/114533/3 "2024-05-22T07:58:32Z")
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](https://github.com/JuliaGraphs/Graphs.jl/pull/376) is merged, you will be able to use an `UndirectedView` to avoid allocating with `Graph`.
---
### Author:  [@Ken\_Williams](https://discourse.julialang.org/u/Ken_Williams)
#### Post date: [May 22, 2024, 2:55pm UTC](https://discourse.julialang.org/t/cutting-graphs-at-bridges/114533/4 "2024-05-22T14:55:14Z")
> [@gdalle](#):
>
> Does it scale sufficiently well for your problem size?
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.
---
### Author:  [@Ken\_Williams](https://discourse.julialang.org/u/Ken_Williams)
#### Post date: [May 22, 2024, 2:57pm UTC](https://discourse.julialang.org/t/cutting-graphs-at-bridges/114533/5 "2024-05-22T14:57:31Z")
> [@etienne\_dg](#):
>
> Why do you say if cannot be computed for MetaGraph?
The issue does seem to be the directedness, as you suggested:
```julia
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
```
> [@etienne\_dg](#):
>
> once [ReverseView and UndirectedView by etiennedeg · Pull Request #376 · JuliaGraphs/Graphs.jl · GitHub](https://github.com/JuliaGraphs/Graphs.jl/pull/376) is merged, you will be able to use an `UndirectedView` to avoid allocating with `Graph`.
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!