0

I have a finite directed graph (of several weakly connected components).

Having two elements I need to check if there is a path from the first one to the second one.

The easiest solution is to create the incidence matrix and then using it calculate the connectivity matrix (the further is obvious). But I feel it is not the most efficient way in terms of startup time and memory space.

What is a more efficient way (taking into account that there are several components between which there are no links)?

Moreover the following may be used for optimization: In each connected component K, existence of a path needs to be checked only from a fixed vertex B(K) to other elements of K only. And it is expected to never check if there is a path (we know that there is none by definition of connected components, however) from an element of one connected component to an element of another connected component.

I write in Ada.

porton
  • 752
  • 1
  • 7
  • 20
  • Some examples and diagrams would probably help us understand you here. – candied_orange Oct 29 '17 at 00:54
  • If I am understanding right you just want to check if a path exists between two points in your graph but only check direct links, no connections via transitivity. – Hangman4358 Oct 29 '17 at 06:27
  • @Hangman4358 You misunderstand. I need to check "connections via transitivity" between two gives vertices. – porton Oct 29 '17 at 12:04
  • Ok, I might be getting confused by the explanation of weakly linked components. Are you saying that you have a graph consisting of multiple disjoint subgraphs? Like A>B>C and D>E without a connection between nodes C and D, thereby giving us two disjoint subgraphs? – Hangman4358 Oct 29 '17 at 14:27
  • @Hangman4358 "Are you saying that you have a graph consisting of multiple disjoint subgraphs?" - Yes – porton Oct 29 '17 at 16:00

0 Answers0