Detecting Cycles in a Network Graph With MapReduce
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 map/reduce.
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)
via: http://horicky.blogspot.com/2013/01/mapreduce-detecting-cycles-in-network.html
