# Indirect Connected vertices in a digraph

**URL:** <https://discourse.julialang.org/t/indirect-connected-vertices-in-a-digraph/77631>\
**Category:** Graphs\
**Tags:** lightgraphs, graphs\
**Created:** [March 9, 2022, 1:05pm UTC](https://discourse.julialang.org/t/indirect-connected-vertices-in-a-digraph/77631 "2022-03-09T13:05:32Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![Temi-Tory](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/temi-tory/32/29716_2.png) [@Temi-Tory](https://discourse.julialang.org/u/Temi-Tory)\
**Post date:** [March 9, 2022, 1:05pm UTC](https://discourse.julialang.org/t/indirect-connected-vertices-in-a-digraph/77631/1 "2022-03-09T13:05:32Z")

</div>

Hi guys,  
This may be an obvious or silly question but I cannot seem to figure out how to do so.  
I’m not sure how to do this especially for graphs with large number of vertices, where I want to check if there is a path from some source node to a destination node.  
so I will give an example using a small simple graph.

Say I have a directed graph G  
with some vertices [A,B,C,D,E]  
connected by edges [A-\>B, B-\>C,C-\>D,D-\>E]

I am trying to check that there exists a path that A-\>D i.e ( A-\>B-\>C-\>D-\>E)

or what if i wanted to check if a path B-\>D exist ie (B-\>C-\>D)

Thank you 🙂

---

<div class="post-metadata">

**Author:** ![Rudi79](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rudi79/32/3884_2.png) [@Rudi79](https://discourse.julialang.org/u/Rudi79)\
**Post date:** [March 9, 2022, 1:30pm UTC](https://discourse.julialang.org/t/indirect-connected-vertices-in-a-digraph/77631/2 "2022-03-09T13:30:19Z")

</div>

Maybe this example helps you:

```julia
using Graphs
G = CliqueGraph(3,4)
has_path(G,1,2)

```

It is much easier to help you if you post the code you already tried. See e.g. [Please read: make it easier to help you](https://discourse.julialang.org/t/please-read-make-it-easier-to-help-you/14757)  
Also the documentation might help:  
[https://juliagraphs.org/Graphs.jl/dev/pathing/](https://juliagraphs.org/Graphs.jl/dev/pathing/)

---

<div class="post-metadata">

**Author:** ![opera\_malenky](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/opera_malenky/32/8213_2.png) [@opera\_malenky](https://discourse.julialang.org/u/opera_malenky)\
**Post date:** [March 9, 2022, 2:01pm UTC](https://discourse.julialang.org/t/indirect-connected-vertices-in-a-digraph/77631/3 "2022-03-09T14:01:35Z")

</div>

Besides whatever tools the Graphs package provides (almost certainly a better option for you), you can also do it easily by hand, if you have an upper bound to the distance between nodes you are willing to set.

If you have your graph in a matrix format, you can simply look at the powers of the matrix. Per Wasserman and Faust (p. 160), raising a (binary) matrix to the _n_-th power gives you a matrix whose elements give you the number of (possibly directed) walks of length _n_ between any given pair of nodes.

---

<div class="post-metadata">

**Author:** ![etienne\_dg](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)\
**Post date:** [March 9, 2022, 2:13pm UTC](https://discourse.julialang.org/t/indirect-connected-vertices-in-a-digraph/77631/4 "2022-03-09T14:13:31Z")

</div>

This is very inefficient though, detecting a path is done by a simple DFS in the graph.

---

<div class="post-metadata">

**Author:** ![opera\_malenky](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/opera_malenky/32/8213_2.png) [@opera\_malenky](https://discourse.julialang.org/u/opera_malenky)\
**Post date:** [March 9, 2022, 2:40pm UTC](https://discourse.julialang.org/t/indirect-connected-vertices-in-a-digraph/77631/5 "2022-03-09T14:40:08Z")

</div>

Absolutely - but it’s always nice to know how to do things like this directly, for times when you don’t have easy access to software with the optimal algorithms. Plus, for people like me, who work with smaller social networks (\<1000 people), the speed/storage issue will be less important.

---

<div class="post-metadata">

**Author:** ![Temi-Tory](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/temi-tory/32/29716_2.png) [@Temi-Tory](https://discourse.julialang.org/u/Temi-Tory)\
**Post date:** [March 9, 2022, 2:53pm UTC](https://discourse.julialang.org/t/indirect-connected-vertices-in-a-digraph/77631/6 "2022-03-09T14:53:58Z")

</div>

> [@Rudi79](#):
>
> `has_path(G,1,2)`

Thank you

This was exactly what I needed. I was wondering about the `has_path` function. For some reason I missed that section when i was looking at documentation.