We’ll maintain two types of graph data:
- A set of link files where each line represent an edge in the graph.
This file will be static.
- A set of path files where each line represent a path from one node
to another node. This file will be updated in each round of
The general idea is to grow the path file until either the path
cannot grow further, or the path contain a cycle, we’ll use two
global flags to keep track of that: “change” flag to keep track of
whether new path is discovered, and “cycle” flag to keep track
whether a cycle is detected.
Isn’t this approach very inneficient (by not being able to account or reuse already processed paths)?
Original title and link: Detecting Cycles in a Network Graph With MapReduce ( ©myNoSQL)