Graph Transitivity Java

user_8162281 0
Viewed 125

I'm using a custom graph to represent a set of data, as shown in the figure:

enter image description here

I have already created several methods that allow me to fill the structure. The main objective of this type of representation is to know quickly if a specific path exists. I have the following problem with the path search method:

For example, if I consider the paths "A-> D-> X", "B-> D -> #", "A-> E -> #", "A-> D -> #", then I would like to obtain the existence of the paths. However, if I consider the path "B -> D -> X", I would like to get that the path does not exist.

Do you have any suggestions for developing this type of method without considering the initial data set?

graph data-structures java
2 Answers

If the only available paths are the ones in your table, you can use any implementation of a set data structure, like HashSet or TreeSet in Java. Just add all the paths to the set, and then use the Set.contains method to check if a path is valid.

This will work reasonably well as long as the valid paths are short or there is a small number of them. If there is a large number of paths, and they are long, you'll get better performance with other data structures.

For example a trie is a collection for sequences of items, that lets you check if a sequence is present in time proportional to the length of the sequence. It has been traditionally used for strings, but you can easily use it for graph paths. In this usage, the nodes in the trie would store nodes of your graph, so that a path in the trie corresponds to a valid path in your graph.

user_3187580

Making two assumptions here:

  1. The edges are bidirectional;
  2. Unlike the examples you have listed, you are not looking for 3-node (or 2-edge) paths only, meaning A->E->#->D->B is also a valid path and should return true.

The Disjoint Sets / Union-Find Data Structure gives you just that ability.

In this DS, which has more than one underlying implementations, all connected nodes will be in the same set. Thus If you have n connected components, then you will have as many disjoint-sets.

To find if there is a path between node-1 and node-2, just see if they are in the same set.

user_18357690
Related