Last active
November 21, 2017 22:30
-
-
Save Ethan826/36c2037995ad8e43c7079c8eeae55e29 to your computer and use it in GitHub Desktop.
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
# frozen_string_literal: true | |
require "set" | |
require "minitest/autorun" | |
# Helper method for `get_levels`. Using a breadth-first search, traverse up the | |
# parent entries in the adjacency list, setting entries in the `levels` hashmap | |
# and adding relatives to the `level_known` set. Relies on Ruby's | |
# pass-by-reference semantics for objects to mutate arguments `levels` and | |
# `level_known` (which is the point of calling the function). | |
# | |
# The traversal works exactly like a normal iterative breadth-first search, see, | |
# e.g. https://goo.gl/tXAMmS, except that we don't need a `visited` data | |
# structure because a family without cosanguineous marriage is guaranteed to be | |
# acyclic. | |
# rubocop:disable Metrics/MethodLength | |
def get_levels_bfs(family, current, level, levels, level_known) | |
frontier = [current] | |
until frontier.empty? | |
level += 1 | |
frontier.each_with_object([]) do |next_node, next_frontier| | |
family[next_node].each do |further_node| | |
next_frontier << further_node | |
level_known << further_node | |
levels[further_node] = level | |
end | |
end | |
frontier = next_frontier | |
end | |
end | |
# rubocop:enable Metrics/MethodLength | |
# Given an array of paths, traverse up one further level, updating paths. Drop | |
# paths that cannot go up a level. | |
# | |
# @param family [Hash{Symbol => Array<Symbol>}] | |
def go_up_one_level(family, paths) | |
paths.each_with_object([]) do |path, result| | |
family[path.last]&.each do |next_node| | |
result << (path.clone << next_node) | |
end | |
end | |
end | |
# Reverse a path between relatives. Given a path of the form | |
# [[:son, :father, :grandfather, :uncle], [:up, :up, :down]], | |
# return | |
# [[:uncle, :grandfather, :father, :son], [:up, :down, :down]] | |
# | |
# @param path [Array<Array<Symbol>] | |
# @return [Array<Array<Symbol>>] | |
def reverse_path(path) | |
[ | |
path.first.reverse, | |
path.last.reverse.map do |e| | |
unless %i[down up].include?(e) | |
raise ArgumentError, | |
"Directions must be `:up` or `:down`; #{e} is invalid" | |
end | |
e == :up ? :down : :up | |
end | |
] | |
end | |
# Simple path-building bfs. See https://goo.gl/df7G2F | |
# | |
# @param family [Hash{Symbol => Set<Symbol>}] | |
# @param start_node [Symbol] | |
# @param end_node [Symbol] | |
# @return [Array<Array<Symbol>>] | |
def get_up_path(family, start_node, end_node) | |
paths = [[start_node]] | |
until paths.empty? | |
path = paths.pop | |
next_node = path[-1] | |
return [path, Array.new(path.length.pred, :up)] if next_node == end_node | |
family[next_node]&.each do |adjacent| | |
paths << (path.clone << adjacent) | |
end | |
end | |
[] | |
end | |
# Helper method for `get_up_down_paths`. Given a family adjacency list, a | |
# relative at a lower generation, a relative at a higher generation, and a | |
# hashset containing the generational levels of all family members, walk up the | |
# family from both nodes until reaching one generation above the higher node, | |
# returning the paths from each node to that common generation. | |
# | |
# @param family [Hash{Symbol => Set<Symbol>}] | |
# @param levels [Hash{Symbol => Integer}] | |
# @param low_node [Symbol] | |
# @param high_node [Symbol] | |
# @return [Hash{Symbol => Array<Array<Symbol>>}] | |
def initialize_high_low_node_paths(family, levels, low_node, high_node) | |
low_node_paths = [[low_node]] | |
high_node_paths = [[high_node]] | |
(levels[high_node] - levels[low_node]).succ.times do | |
low_node_paths = go_up_one_level(family, low_node_paths) | |
end | |
high_node_paths = go_up_one_level(family, high_node_paths) | |
{ high_node_paths: high_node_paths, low_node_paths: low_node_paths } | |
end | |
# Given paths going up the generations from each of two relatives, combine the | |
# paths to reflect routes going up from the relative in a later generation to | |
# the common ancestors, then down from the common ancestors to the relative in | |
# the earlier generation. The result is an array of all the routes, each route | |
# comprising a two-element array with the first element representing a path of | |
# length n and the second element an array of n-1 elements, each representing | |
# the direction to traverse from each relative to the next relative. | |
# | |
# @example | |
# combine_up_down_paths( | |
# [[:proband, :father, :grandmother]], [[:uncle, :grandmother]] | |
# ) # => [[[:proband, :father, :grandmother, :uncle], [:up, :up, :down]]] | |
# | |
# @param low_node_paths_to_merge [Array<Array<Symbol>>] | |
# @param high_node_paths_to_merge [Array<Array<Symbol>>] | |
# @return [Array<Array<Array<Symbol>>>] | |
def combine_up_down_paths(low_node_paths_to_merge, high_node_paths_to_merge) | |
low_node_paths_to_merge.flat_map do |s| | |
high_node_paths_to_merge.map do |e| | |
[s + e.reverse.drop(1), | |
Array.new(s.length.pred, :up) + Array.new(e.length.pred, :down)] | |
end | |
end | |
end | |
# Helper method for `get_up_down_paths`. Given a path through generations, | |
# combine the paths on all common ancestors if any exist, else nil. | |
# | |
# @param low_node_paths [Array<Symbol>] | |
# @param high_node_paths [Array<Symbol>] | |
# @return [Array<Array<Array<Symbol>>>, nil] | |
def combine_paths(low_node_paths, high_node_paths) | |
overlap = low_node_paths.map(&:last) & high_node_paths.map(&:last) | |
unless overlap.empty? # rubocop:disable Style/GuardClause | |
overlap.flat_map do |overlapping_element| | |
predicate = ->(path) { path.last == overlapping_element } | |
low_node_paths_to_merge = low_node_paths.select(&predicate) | |
high_node_paths_to_merge = high_node_paths.select(&predicate) | |
combine_up_down_paths(low_node_paths_to_merge, high_node_paths_to_merge) | |
end | |
end | |
end | |
# We go up with a bfs from the lower node to the level of the higher node. Then | |
# we traverse up one layer from each until we hit a level with common ancestry. | |
# At that point, we | |
def get_up_down_paths(family, levels, low_node, high_node) | |
high_node_paths, low_node_paths = | |
initialize_high_low_node_paths(family, levels, low_node, high_node) | |
.values_at(:high_node_paths, :low_node_paths) | |
until low_node_paths.empty? || high_node_paths.empty? | |
combined_paths = combine_paths(low_node_paths, high_node_paths) | |
return combined_paths if combined_paths | |
low_node_paths = go_up_one_level(family, low_node_paths) | |
high_node_paths = go_up_one_level(family, high_node_paths) | |
end | |
[] | |
end | |
# Helper method for `build_paths`. Mutates the `paths` argument. Note that for | |
# optimization purposes, `up_path` is passed by value. | |
# | |
# @param low_node [Symbol] | |
# @param high_node [Symbol] | |
# @param up_path [Array<Symbol>] | |
# @param paths[Hash{Array<Symbol> => Array<Symbol>}] | |
def handle_direct_lineage(low_node, high_node, up_path, paths) | |
paths[[low_node, high_node]] = [up_path] | |
paths[[high_node, low_node]] = [reverse_path(up_path)] | |
end | |
# Helper method for `build_paths`. Mutates the `paths` argument. | |
# | |
# @param low_node [Symbol] | |
# @param high_node [Symbol] | |
# @param levels [Hash{Symbol => Integer}] | |
# @param paths[Hash{Array<Symbol> => Array<Symbol>}] | |
def handle_no_direct_lineage(low_node, high_node, levels, paths) | |
up_down_paths = get_up_down_paths(family, levels, low_node, high_node) | |
if !up_down_paths.empty? | |
paths[[low_node, high_node]] = up_down_paths | |
paths[[high_node, low_node]] = | |
up_down_paths.map { |path| reverse_path(path) } | |
else | |
paths[[low_node, high_node]] = [] | |
paths[[high_node, low_node]] = [] | |
end | |
end | |
# Given a `family` adjacency list and a `levels` hashmap, construct an hashmap | |
# with keys as `[start_node, end_node]` and values as | |
# `[[[:path, :through, :family], [:up, :down]], | |
# [[:other, :path, :through], [:up :down]]]` | |
# | |
# @param family [Hash{Symbol => Array<Symbol>}] | |
# @param levels [Hash{Symbol => Integer}] | |
# @return [Array<Array<Array<Symbol>>>] | |
def build_paths(family, levels) | |
family.keys.combination(2) | |
.each_with_object({}) do |(start_node, end_node), paths| | |
low_node, high_node = [start_node, end_node].sort_by { |node| levels[node] } | |
up_path = get_up_path(family, low_node, high_node) | |
if up_path.empty? | |
handle_no_direct_lineage(low_node, high_node, levels, paths) | |
else | |
handle_direct_lineage(low_node, high_node, up_path, paths) | |
end | |
end | |
end | |
# Given a hashmap of type T keys and sets of type T values, each representing | |
# one family member, compute the "level" of each family member, with internally | |
# consistent but arbitrary indexing (the indices will include 0, but may contain | |
# positive or negative numbers). | |
def get_levels(family) # rubocop:disable Metrics/MethodLength Metrics/AbcSize | |
# Table-setting before the first iteration | |
level = 0 | |
levels = family.keys.reduce({}) { |a, k| a.merge(k => nil) } | |
current = family.keys.first | |
level_known = Set.new | |
# We will be done once the `length_known` set has every member of the family. | |
# Before each iteration, `current` has been added to the `levels` hashmap. | |
until level_known.length == family.keys.length | |
# Update data structures to reflect our knowledge of `current`. | |
levels[current] = level | |
level_known << current | |
# Run a depth-first search to update the levels of all family members above | |
# `current` in the family. | |
get_levels_bfs(family, current, level, levels, level_known) | |
# Now we need to find a way to traverse down the family. We'll find a child | |
# with a parent in the `levels` hashmap whose level isn't known. That's a | |
# person in the `levels` hashmap for whom (1) the value is `nil`, and (2) | |
# who has at least one parent in the `levels` hashmap with a non-nil level | |
# (we'll need to cross-reference the `family` hashmap to look up parents). | |
# Having found that person, we can set the person's level to be one lower | |
# than their parent's, set that person to be the new `current`, and loop | |
# back through the `get_levels_bfs` function. | |
levels.each do |k, v| | |
next unless v.nil? # No point working with someone whose level we do know. | |
# Take the set intersection of the unknown person's parents with the | |
# people whose levels are known. If there is at least one member of the | |
# set intersection, we know we have a child of someone with a known level. | |
parent = (family[k] & level_known).first | |
if parent | |
current = k | |
level = levels[parent].pred | |
end | |
end | |
end | |
levels | |
end | |
# :nodoc: | |
class TestUncleFamily < Minitest::Test | |
attr_reader :levels, :family | |
def setup # rubocop:disable Metrics/MethodLength | |
@levels = { proband: 0, | |
mother: 1, | |
father: 1, | |
grandmother: 2, | |
grandfather: 2, | |
uncle: 1 } | |
@family = { proband: Set.new(%i[mother father]), | |
mother: Set.new, | |
father: Set.new(%i[grandmother grandfather]), | |
grandmother: Set.new, | |
grandfather: Set.new, | |
uncle: Set.new(%i[grandfather grandmother]) } | |
end | |
def test_go_up_one_level | |
paths = [[:proband]] | |
up_one_level = go_up_one_level(family, paths).sort | |
assert_equal(up_one_level, [%i[proband mother], %i[proband father]].sort) | |
assert_equal( | |
go_up_one_level(family, up_one_level), | |
[%i[proband father grandmother], %i[proband father grandfather]] | |
) | |
end | |
def test_get_up_down_paths | |
assert_equal( | |
[[%i[proband father grandmother uncle], %i[up up down]], | |
[%i[proband father grandfather uncle], %i[up up down]]], | |
get_up_down_paths(family, levels, :proband, :uncle) | |
) | |
end | |
def test_reverse_path | |
assert_equal( | |
[%i[uncle grandmother father proband], %i[up down down]], | |
reverse_path([%i[proband father grandmother uncle], %i[up up down]]) | |
) | |
end | |
def test_get_up_path | |
assert_equal( | |
[%i[proband father grandmother], %i[up up]], | |
get_up_path(family, :proband, :grandmother) | |
) | |
end | |
end | |
# :nodoc: | |
class TestMyFamily < Minitest::Test | |
attr_reader :levels, :family | |
def setup # rubocop:disable Metrics/MethodLength | |
@family = { | |
marshall: Set.new, | |
belle: Set.new(%i[ethan madigan]), | |
betty: Set.new, | |
red: Set.new, | |
nancy: Set.new, | |
clara: Set.new(%i[ethan madigan]), | |
ethan: Set.new(%i[steve judy]), | |
jonathan: Set.new(%i[betty marshall]), | |
judy: Set.new, | |
madigan: Set.new(%i[jonathan maggie]), | |
maggie: Set.new(%i[red nancy]), | |
milo: Set.new(%i[ethan madigan]), | |
nick: Set.new(%i[jonathan maggie]), | |
steve: Set.new | |
} | |
@levels = { marshall: 0, | |
belle: -3, | |
betty: 0, | |
red: 0, | |
nancy: 0, | |
clara: -3, | |
ethan: -2, | |
jonathan: -1, | |
judy: -1, | |
madigan: -2, | |
maggie: -1, | |
milo: -3, | |
nick: -2, | |
steve: -1 } | |
end | |
def test_foo | |
pp build_paths(family, levels) | |
end | |
end |
Author
Ethan826
commented
Nov 19, 2017
•
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment