Indirect Connected vertices in a digraph

Specific Domains Graphs
,
1

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 :slight_smile:

2

Maybe this example helps you:

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
Also the documentation might help:
https://juliagraphs.org/Graphs.jl/dev/pathing/

3 Likes
3

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.

4

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

5

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.

6

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.