Last active
June 4, 2018 23:39
-
-
Save brezniczky/5c65ee8cf2a56aaced3c9ae73f6007b7 to your computer and use it in GitHub Desktop.
Finding reciprocally connected nodes in a graph using map-reduce, psuedocode
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def mapper(input): | |
for each edge node1 -> node2 in input: | |
emit (key: node1, node1 -> node2) | |
emit (key: node2, node2 <- node1) | |
def reducer(key: node, edges): | |
for each distinct edge node1 -> node2 in edges: | |
if node1 <= node2: | |
if node2 <- node1 in edges: | |
emit(node1, node2) | |
# --> improvement: filter against communicating redundant connections between map and reduce | |
def mapper(input): | |
# only emit in/out edges to the smaller node | |
# (reduces transport costs) | |
for each edge node1 -> node2 in input: | |
if node1 <= node2: | |
emit (key: node1, node1 -> node2) | |
if node2 >= node1: | |
emit (key: node1, node1 <- node2) | |
def reducer(key: node, edges): | |
for each distinct edge node1 -> node2 in edges: | |
if node1 <- node2 in edges: | |
emit(node1, node2) | |
emit(node2, node1) | |
""" | |
--> could improve (but it's getting late): | |
only communicate if it's an in or out edge, not | |
the two nodes comprising the edge, plus the | |
smaller node as key - since "node1" is a duplicate | |
information between mapper and reducer, instead | |
a single bit could depict the direction of the edge | |
""" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment