How to group two value arrays to n value arrays in the below example?

Question

I already have many two value arrays for example in the below

ary = [[1, 2], [2, 3], [1, 3], [4, 5], [5, 6], [4, 7], [7, 8], [4, 8]]

I want to group them into

[1, 2, 3], [4, 5], [5, 6], [4, 7, 8]

Because the meaning is 1 and 2 have relationship, 2 and 3 have relationship,1 and 3 have relationship,so 1,2,3 all have relationship

How can I do this by ruby lib or any algorithm?

Answer 1

Here is a Ruby implementation of the basic Bron–Kerbosch algorithm:

class Graph
  def initialize(edges)
    @edges = edges
  end

  def find_maximum_cliques
    @cliques ||= []
    bron_kerbosch([], nodes, []) if @cliques.empty?

    @cliques
  end

  private

  def nodes
    @nodes ||= @edges.flatten.uniq
  end

  def neighbours
    @neighbours ||= nodes.map do |node|
      node_neighbours =
        @edges.select { |edge| edge.include? node }.flatten - [node]

      [node, node_neighbours]
    end.to_h
  end

  def bron_kerbosch(re, pe, xe)
    @cliques << re if pe.empty? && xe.empty?

    pe.each do |ve|
      bron_kerbosch(re | [ve], pe & neighbours[ve], xe & neighbours[ve])
      pe -= [ve]
      xe |= [ve]
    end
  end
end

---

edges = [[1, 2], [2, 3], [1, 3], [4, 5], [5, 6], [4, 7], [7, 8], [4, 8]]

Graph.new(edges).find_maximum_cliques # => [[1, 2, 3], [4, 5], [4, 7, 8], [5, 6]]

There is a an optimization that can get it to O(3^n/3).

Answer 2

Your array can be seen as a Graph (e.g. Node 1 and Node 2 are connected by an Edge, as well as Node 2 and 3, ...)

You're looking for an Array of all the maximum cliques. A clique cover is an array of maximum cliques which contains every Node exactly once. This problem is hard.

A clique is a subset of your graph in which every node is connected to each other. If a node isn't connected to any other, it forms a clique with just one node, itself. A maximum clique is a clique which cannot be enlarged by adding another node.

This gem might be able to help you, with the all_max_cliques method. Here's a script you could write at the root of the Clique project :

require_relative 'src/graph.rb'
require_relative 'src/bron.rb'
require_relative 'src/max_clique.rb'
require_relative 'src/util.rb'
require 'set'

ary = [[1,2],[2,3],[1,3],[4,5],[5,6],[4,7],[7,8],[4,8]]

graph = Graph.new
graph = ary.each_with_object(Graph.new){|(n1,n2),graph| graph.insert(n1, [n2])}

all_max_cliques(graph.graph)

It outputs :

intersections after sort!: {3=>[2], 2=>[3]}
cliqueeee[3, 2, 1]
intersections after sort!: {3=>[1], 1=>[3]}
...
...
cliqueeee[6, 5]
intersections after sort!: {5=>[]}
cliqueeee[5, 6]
largest clique!: [6, 5]
[[3, 2, 1], [8, 7, 4], [6, 5]]

Note that if you want a clique cover, (i.e. a partition), every node should appear exactly once. 5 and 6 form a maximum clique, and 4 is already inside [4,7,8], so there's no need for [4,5].

Here's a very basic bruteforce solution. Don't use it for anything big!

require 'set'

class Graph
  attr_reader :nodes, :edges

  def initialize(edges)
    @nodes = edges.flatten.sort.uniq
    @edges = edges.map(&:sort).to_set
  end

  def minimum_clique_cover
    partitions.select{ |p| all_cliques?(p) }.min_by(&:size)
  end

  private

  def partitions(array = nodes)
    if array.length == 1
      [[array]]
    else
      *head, tail = array
      partitions(head).inject([]) do |result, partition|
        result + (0..partition.length).collect do |index_to_add_at|
          new_partition = partition.dup
          new_partition[index_to_add_at] = (new_partition[index_to_add_at] || []) + [tail]
          new_partition
        end
      end
    end
  end

  def all_cliques?(partition)
    partition.all?{ |subset| clique?(subset) }
  end

  def clique?(subset)
    subset.permutation(2).select{ |n1, n2| n2 > n1 }.all?{ |edge| edges.include?(edge) }
  end
end

p Graph.new([[1, 2], [2, 3], [1, 3], [4, 5], [5, 6], [4, 7], [7, 8], [4, 8]]).minimum_clique_cover
# => [[4, 7, 8], [5, 6], [1, 2, 3]]

It returns a minimum clique cover, which is harder than just an Array of maximum cliques. Don't ask me about the complexity of this script, and I won't have to lie.