# Test if two vertices are connected in a graph
**URL:** https://discourse.julialang.org/t/test-if-two-vertices-are-connected-in-a-graph/107675
**Category:** Graphs
**Tags:** question, graphs
**Created:** [December 15, 2023, 3:29pm UTC](https://discourse.julialang.org/t/test-if-two-vertices-are-connected-in-a-graph/107675 "2023-12-15T15:29:50Z")
**Posts on this page:** 5
**Page:** 1
### Author:  [@jonlym](https://discourse.julialang.org/u/jonlym)
#### Post date: [December 15, 2023, 3:29pm UTC](https://discourse.julialang.org/t/test-if-two-vertices-are-connected-in-a-graph/107675/1 "2023-12-15T15:29:50Z")
Hello all,
I would like to create a graph with no weights and efficiently test if vertices are connected (not necessarily neighbors).
I learned I can do this using [shortest\_path](https://juliagraphs.org/Graphs.jl/dev/advanced/experimental/#Graphs.Experimental.ShortestPaths.shortest_paths-Tuple%7BAbstractGraph,%20Any,%20Graphs.Experimental.ShortestPaths.ShortestPathAlgorithm%7D) algorithms and [connected\_components](https://juliagraphs.org/Graphs.jl/dev/algorithms/connectivity/#Graphs.connected_components-Union%7BTuple%7BAbstractGraph%7BT%7D%7D,%20Tuple%7BT%7D%7D%20where%20T) but I wanted to see if there was a more efficient way, especially as the graph complexity grows.
MWE:
```julia
using BenchmarkTools
using Graphs
using Random
function is_connected_using_shortest_path(g, source, sink)
# If there's a more efficient algorithm than a_star, let me know please
paths = a_star(g, source, sink);
return length(paths) > 0;
end
function is_connected_using_connected_components(g, source, sink)
for cluster in connected_components(g)
if source in cluster && sink in cluster
return true;
end
end
return false;
end
# Creating graph: (1)--(2)--(3) (4)--(5)
g = path_graph(5);
rem_edge!(g, 3, 4);
Random.seed!(1234);
display(@benchmark is_connected_using_shortest_path(g, data[1], data[2]) setup=(data=rand(collect(1:5), 2)))
Random.seed!(1234);
display(@benchmark is_connected_using_connected_components(g, data[1], data[2]) setup=(data=rand(collect(1:5), 2)))
```
Output
```julia
BenchmarkTools.Trial: 10000 samples with 186 evaluations.
Range (min … max): 555.914 ns … 29.407 μs ┊ GC (min … max): 0.00% … 93.17%
Time (median): 694.086 ns ┊ GC (median): 0.00%
Time (mean ± σ): 825.910 ns ± 1.122 μs ┊ GC (mean ± σ): 8.80% ± 6.43%
▃ ▆█▇▆▇
█▆██████▄▂▂▃▂▂▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
556 ns Histogram: frequency by time 2.24 μs <
Memory estimate: 1.09 KiB, allocs estimate: 12.
BenchmarkTools.Trial: 10000 samples with 189 evaluations.
Range (min … max): 523.810 ns … 42.610 μs ┊ GC (min … max): 0.00% … 95.61%
Time (median): 593.651 ns ┊ GC (median): 0.00%
Time (mean ± σ): 811.357 ns ± 1.622 μs ┊ GC (mean ± σ): 14.10% ± 7.06%
█▇▆▆▆▄▂▂▄▄▃▃▂▁▁▁▁▁ ▁ ▁ ▂
███████████████████████▇████████████▇▇▆▇▇▆▆▆▅▅▅▆▅▅▆▅▅▄▅▅▃▃▅▄ █
524 ns Histogram: log(frequency) by time 2.07 μs <
Memory estimate: 1.31 KiB, allocs estimate: 15.
```
EDIT1: Removed NetworkX link. I thought they have a function to do this.
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [December 15, 2023, 7:58pm UTC](https://discourse.julialang.org/t/test-if-two-vertices-are-connected-in-a-graph/107675/2 "2023-12-15T19:58:39Z")
How many times will you call this function? (if many, some pre-processing steps could help)
---
### Author:  [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)
#### Post date: [December 15, 2023, 8:15pm UTC](https://discourse.julialang.org/t/test-if-two-vertices-are-connected-in-a-graph/107675/3 "2023-12-15T20:15:09Z")
The canonical algorithm is union find.
An example implementation is available [here](https://juliacollections.github.io/DataStructures.jl/stable/disjoint_sets/).
A word of warning: `is_connected` will often not be thread-safe, due to amortized lazy updates (“often” means: In many implementations in many programming languages; no idea what datastructures.jl; does).
---
### Author:  [@jonlym](https://discourse.julialang.org/u/jonlym)
#### Post date: [December 18, 2023, 2:31am UTC](https://discourse.julialang.org/t/test-if-two-vertices-are-connected-in-a-graph/107675/4 "2023-12-18T02:31:37Z")
Thank you for the suggestions, @Dan and @foobar_lv2! Hopefully I incorporated your thoughts correctly. Here is my new code:
```julia
using BenchmarkTools
using DataStructures
using Graphs
using Random
function is_connected_using_shortest_path(g, source, sink)
# If there's a more efficient algorithm than a_star, let me know please
paths = a_star(g, source, sink);
return length(paths) > 0;
end
function is_connected_using_connected_components(g, source, sink)
for cluster in connected_components(g)
if source in cluster && sink in cluster
return true;
end
end
return false;
end
function is_connected_using_disjointed_sets(disjoint_set, source, sink)
return in_same_set(disjoint_set, source, sink);
end
# Creating graph: (1)--(2)--(3) (4)--(5)
n_vertices = 5;
removed_edge = n_vertices ÷ 2;
g = path_graph(n_vertices);
rem_edge!(g, removed_edge, removed_edge + 1);
# Create disjointed sets beforehand
clusters = connected_components(g);
g_disjoint_sets = IntDisjointSets(nv(g));
for cluster in clusters
map(i_vertex -> union!(g_disjoint_sets, cluster[1], i_vertex), cluster);
end
Random.seed!(1234);
println("SHORTEST PATHS METHOD");
display(@benchmark is_connected_using_shortest_path(g, data[1], data[2]) setup=(data=rand(collect(1:n_vertices), 2)))
Random.seed!(1234);
println("\n\nCONNECTED COMPONENTS METHOD");
display(@benchmark is_connected_using_connected_components(g, data[1], data[2]) setup=(data=rand(collect(1:n_vertices), 2)))
Random.seed!(1234);
println("\n\nDISJOINTED SETS METHOD");
display(@benchmark is_connected_using_disjointed_sets(g_disjoint_sets, data[1], data[2]) setup=(data=rand(collect(1:n_vertices), 2)))
```
And here are the results:
```julia
SHORTEST PATHS METHOD
BenchmarkTools.Trial: 10000 samples with 181 evaluations.
Range (min … max): 572.928 ns … 37.107 μs ┊ GC (min … max): 0.00% … 93.94%
Time (median): 797.238 ns ┊ GC (median): 0.00%
Time (mean ± σ): 959.663 ns ± 1.255 μs ┊ GC (mean ± σ): 8.15% ± 6.35%
▃▄▆▇▇███▇▇▅▄▃▃▂▂▃▂▂▁▁▁ ▁▁▁ ▃
█████████████████████████████▇▇▇▇▇███▇▆█▇▇▇▇██▇▇▇▅▅▅▄▆▄▆▂▄▃▄ █
573 ns Histogram: log(frequency) by time 2.56 μs <
Memory estimate: 1.09 KiB, allocs estimate: 12.
CONNECTED COMPONENTS METHOD
BenchmarkTools.Trial: 10000 samples with 191 evaluations.
Range (min … max): 542.408 ns … 47.443 μs ┊ GC (min … max): 0.00% … 97.71%
Time (median): 675.393 ns ┊ GC (median): 0.00%
Time (mean ± σ): 863.796 ns ± 1.762 μs ┊ GC (mean ± σ): 14.74% ± 7.14%
▃▇█▃
▃▄█████▅▄▃▃▃▃▃▃▃▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂▂ ▃
542 ns Histogram: frequency by time 2.01 μs <
Memory estimate: 1.31 KiB, allocs estimate: 15.
DISJOINTED SETS METHOD
BenchmarkTools.Trial: 10000 samples with 991 evaluations.
Range (min … max): 39.051 ns … 320.081 ns ┊ GC (min … max): 0.00% … 0.00%
Time (median): 48.436 ns ┊ GC (median): 0.00%
Time (mean ± σ): 50.928 ns ± 14.828 ns ┊ GC (mean ± σ): 0.00% ± 0.00%
▃▂▄▄▅▆▇█▆▅▂▁ ▁ ▂
███████████████▇████▆▆▆▆▆▅▅▅▆▆▆▅▅▅▃▂▃▆▅▅▅▅▅▆▇▂▅▆▅▆▅▆▇█▅▇▅▄▅▄ █
39.1 ns Histogram: log(frequency) by time 116 ns <
Memory estimate: 0 bytes, allocs estimate: 0.
```
I’m still new to Julia so is the memory estimate of 0 bytes for the last method expected? Also, I tried testing different number of vertices and it seems to scale really well:
| | | Mean Time | |
| --- | --- | --- | --- |
| Number of vertices | Shortest Path | Connected Components | Disjoined Set Method |
| 10 | 1.227 μs | 1.152 μs | 56.596 ns |
| 100 | 2.137 μs | 6.008 μs | 57.994 ns |
| 1000 | 56.033 μs | 49.573 μs | 58.809 ns |
Of course, this doesn’t take into account the time to create the disjointed sets and the graph is still pretty simple but I think it’ll translate to more complex graphs well.
Thanks again!
---
### Author:  [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)
#### Post date: [December 18, 2023, 10:34am UTC](https://discourse.julialang.org/t/test-if-two-vertices-are-connected-in-a-graph/107675/5 "2023-12-18T10:34:27Z")
> [@jonlym](#):
>
> Of course, this doesn’t take into account the time to create the disjointed sets
FWIW, the way of building that is
```julia
julia> function unionfind(g)
dj = IntDisjointSets(nv(g))
for idx = 1:nv(g)
for other in neighbors(g, idx)
union!(dj, idx, other)
end
end
dj
end
```
You don’t need to compute clusters beforehand.
The magic of unionfind is that it can be updated via edge addition (not removal, though!).
The correct way using Graphs only is
```julia
julia> function labelmake(g)
labels = zeros(Int, nv(g))
Graphs.connected_components!(labels, g)
labels
end
labelmake (generic function with 1 method)
julia> isconnected(labels, i, j) = labels[i]==labels[j]
isconnected (generic function with 1 method)
```
The `connected_components!` method is not exported in graphs. I found it via @less connected\_components(g) `.
It is very advisable to always skim the code of all interesting functions you are using, before you start using clever workarounds for API shortcomings like your `is_connected_using_connected_components` that iterates over the clusters. If the API sucks for your purpose, then there is a chance that it internally uses a better API!
(not all packages / libraries have code where you can easily take a peek. Some code is heavy in non-ascii unicode or macros or has lots of indirections, or is generally hard to read. But it costs you at most 60 seconds to check whether one minute is enough to see what is happening under the hood)