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)
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.
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.