Tuesday, July 19, 2016

get weakly related items given strongly related items map

Given a map of strongly related items for items, get weakly related items for any item.
a - [b, c, d]
b - [a, c]
c - [a, b, e]
d - [a]
e - [c, f]
f - [e]
g - []

strong(a) = [b, c, d]
So, weak(a) = [e, f]
The weakly related items are item's descendants (subtree) except the item and item's children (direct descendants). As the relations are a graph, the set weak acts as a visited set too.
weakitems(id, map):
    set weak = new
    weakitems(id, map, weak)
    weak.remove(id)
    for sid in map[id]:
        weak.remove(sid)
    return weak

weakitems(id, map, visited):
    if visited.has(id):
        return
    visited.add(id)
    for sid in map[id]:
        weakitems(sid, map, visited)

No comments:

Post a Comment