6
$\begingroup$

I'm looking to find / develop a simple parallel algorithm that does this:

Input:

  • vs: list of root vertices
  • max_length: max cycle length
  • max_dist: max distance to root

Variants

  • one variant of the algorithm should support directed graphs
  • the other variant should support undirected graphs (or treat a directed graph as undirected)

Output:

  • for each vertex in the root vertices, "numberOfCycles" should be set for the number of cycles (I assume the right term is elementary cycles) that pass via the root, that are no more than max_length length, and no more than max_dist (shortest path) from the root (e.g. all vertices in the path are up to max_dist distance from the root, if even one is more, then the cycle is ignored).

What I thought of so far:

I'm sure this can be highly optimized, (this is why I asked the question) and probably very native and perhaps incorrect, please be patient with me :)

  • first, do a parallel BFS starting from the roots running for max_dist iterations (e.g. pregel for shortest paths for N iterations on GraphX), mark all nodes within that range with their distance from the root (using a map as a node can be in the proximity of more than one root) - this is covered with built in Spark ShortestPaths code (a little modified to allow for limiting number of iterations + support treating a directed graph as undirected)

This is where I am not sure how to continue.

  • if it's a directed graph, then strongly connected components is the answer? but won't it find only one cycle (the largest one I assume?) e.g. each vertex can only be in one strongly connected component, right?

  • should I find bridges using Tarjan's algorithm?

  • do a DFS and keep track of the path depth, and add + 1 when I reach back root node or any node that reached the root node? if I'm running a pregel - like paralel algorithm, when should I stop? when all nodes in the radius of max_distance were visited?

  • how do I filter out cycles that are too long? save the cycles in a list and filter it out? or some other way?

Related questions:

  1. https://mathematica.stackexchange.com/questions/9434/finding-elementary-cycles-of-directed-graphs

  2. single algorithm to work on both directed and undirected graph to detect cycles?

  3. https://stackoverflow.com/questions/546655/finding-all-cycles-in-graph

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.