Determines whether a Graph can be divided in two groups, where the nodes in one group are not connected to the nodes in the second group

CanBeGrouped.rb

def assign_value(lib, left, right)
    lib[left]  = !lib[right] if lib[left]  == nil
    lib[right] = !lib[left]  if lib[right] == nil
    return lib
end

def can_be_grouped?(edges)
    
    # Initialize lib - use first edge / first node
    lib    = { edges[0][0].val => true } unless edges.empty?
    
    # If no edges given, default result is true
    result = true
    
    # loop through the edges given
    while edges.length > 0 && result do
      
        edge  = edges.shift   # Grab the first element of the array, assign it to 'edge'
        left  = edge[0].val   # Node on the left
        right = edge[1].val   # Node on the right
        
        # Add edge at the end of the list if none of its nodes are in the library
        if lib[left] == nil && lib[right] == nil
            edges << edge
            
        # If both are the same, the rule is broken, and the result is false
        elsif lib[left] == lib[right]
            result = false

        # look at the lib value for lib[left] & lib[right] and assign corresponding value
        else
            lib = assign_value(lib, left, right)
        end
        
    end
    
    return result
end

# Testing:

class Node
    attr_accessor :val
    
    def initialize(value)
        @val = value
    end
end

a = Node.new('A')
b = Node.new('B')
c = Node.new('C')
d = Node.new('D')
e = Node.new('E')
f = Node.new('F')
g = Node.new('G')
h = Node.new('H')
i = Node.new('I')


# This graph should return 'false'
#
# A(1) ———————— B(2)
# | \            |
# |  \           |
# |   \          |
# |    \         |
# C(2) — D(1) — E(x)

edges1 = [
    [a,b],
    [c,a],
    [d,e],
    [a,d],
    [c,d],
    [b,e]
]


# This graph should return 'true'
# 
# A(1) ———————— B(2)
# |   \          |
# |    \         |
# C(2)  D(2) —— F(1)
# |    /
# |   /
# E(1)
# 

edges2 = [
    [a,b],
    [d,f],
    [c,a],
    [d,e],
    [a,d],
    [b,f],
    [e,c]
]

# This graph should return 'true'
# 
# A(1) — B(2) ——— C(1)
# |      /  \       \ 
# |     /    \       \
# |   D(1)    \       \
# |  /   \     \       \
# | /     \     \       \
# E(2) ——————— F(1) ——— G(2)
# |         \   /
# |          \ /
# H(1)       I(2)
# 

edges3 = [
    [f,g],
    [b,c],
    [b,f],
    [e,a],
    [e,d],
    [b,a],
    [b,d],
    [f,i],
    [e,h],
    [i,d],
    [g,c]
]

# This graph should return 'false'
# 
# A(1) — B(2) ——— C(1)
# |      /  \       \ 
# |     /    \       \
# |   D(1)    \       \
# |  /         \       \
# | /           \       \
# E(2) ——————— F(1) ——— G(2)
# |   \         /
# |    \       /
# |     \     /
# H(1) —— I(x)
# 

edges4 = [
    [f,g],
    [b,c],
    [b,f],
    [e,a],
    [e,d],
    [b,a],
    [b,d],
    [f,i],
    [e,h],
    [e,i],
    [g,c],
    [h,i]
]


first  = can_be_grouped? edges1
second = can_be_grouped? edges2
third  = can_be_grouped? edges3
fourth = can_be_grouped? edges4

puts "\n\nResult:"
puts "empty: #{can_be_grouped?([])}"
puts "first  should be false: #{first}"
puts "second should be true:  #{second}"
puts "third  should be true:  #{third}"
puts "fourth should be false: #{fourth}"