-1

I'm working on a gem called ActiveTouch. It's for creating complex touch or cache invalidation networks. Currently, I'm trying to determine a way of identifying loops within the network.

A simplified version of a dependency map is a hash where the key represents a Model, and the value represents models that are touched.

For example

{ 
  A => [B, C],
  B => [D, F],
  D => [A]
}

In this example we can see there is a dependency loop between A and D, A->B->D->A or D->A->B->D

In order to determine a loop, I need to see all possible paths. How can I see all possible paths, like this:

[
  [A, B, D, A],
  [A, B, F],
  [A, C],
  ...
  [D, A, B, D]
]

A response in Ruby would be great, but any language will suffice.

KPheasey
  • 1,765
  • 16
  • 22

1 Answers1

2

Basically your question boils down to finding a loop in a graph.

You already have your graph stored here, as an adjacency list representation. Detecting cycles is a standard procedure and can be done with a DFS algorithm. You start with some vertex and run DFS till you will see some vertex twice.

If you have disconnected graph, you do this on all the components.

Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
  • Thanks! Been a while since I have gotten to do fun programming like this and can't remember it from school! I looked a little further and found a ruby example of Tarjan's in another question - http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph – KPheasey Dec 19 '15 at 18:20