Algorithm to partition graph into complete subgraphs

Question

I need an algorithm to partition the vertices of an undirected graph into one or more subgraphs, such that each subgraph is a complete graph (every vertex adjacent to every other vertex). Each vertex needs to be in exactly one of the subgraphs.

Here's an example:

input = [
    (A, B),
    (B, C),
    (A, C),
    (B, D),
    (D, E),
]
output = myalgo(input)  # [(A, B, C), (D, E)]

Here's an image that better describes the problem:

The input list is sorted in decreasing order by distance, that's why I connect A-B-C instead of B-D.

I thought this might be called "strongly connected components", and have already tried the following solutions:

• Finding a Strongly Connected Components in unDirected Graphs: it's looking for something different

• Finding all cycles in undirected graphs: it gives me many cycles and not the best, it doesn't care about the input order.

• An algorithm to create clusters from data pairs in python: it connects all the components, just because there is a path between them (A-B-C-D-E).

• Kosaraju's algorithm: it works only with a directed graph.

Answer 1

Here's a class that implements the segmentation into complete subgraphs. It's by no means optimized and can likely be improved significantly, but it's a starting point

class SCCManager:
    def __init__(self, edges):
        self.clusters = []
        self.edges = edges

    def clusters_in(self, conn):
        first, second = conn
        f_clust = None
        s_clust = None
        for i, clust in enumerate(self.clusters):
            if first in clust:
                f_clust = i
            if second in clust:
                s_clust = i
            # break early if both already found
            if f_clust and s_clust:
                break
        return (f_clust, s_clust)

    def all_connected(self, cluster, vertex):
        for v in cluster:
            connected = (v, vertex) in self.edges or (vertex, v) in self.edges
            # break early if any element is not connected to the candidate
            if not connected:
                return False
        return True

    def get_scc(self):
        for edge in self.edges:
            c_first, c_second = self.clusters_in(edge)

            # case 1: none of the vertices are in an existing cluster
            # -> create new cluster containing the vertices
            if c_first == c_second == None:
                self.clusters.append([edge[0], edge[1]])
                continue

            # case 2: first is in a cluster, second isn't
            # -> add to cluster if eligible
            if c_first != None and c_second == None:
                # check if the second is connected to all cluster components
                okay = self.all_connected(self.clusters[c_first], edge[1])
                # add to cluster if eligible
                if okay:
                    self.clusters[c_first].append(edge[1])
                continue

            # case 3: other way round
            if c_first == None and c_second != None:
                okay = self.all_connected(self.clusters[c_second], edge[0])
                if okay:
                    self.clusters[c_second].append(edge[0])
                continue

            # case 4: both are in different clusters
            # -> merge clusters if allowed
            if c_first != c_second:
                # check if clusters can be merged
                for v in self.clusters[c_first]:
                    merge = self.all_connected(self.clusters[c_second], v)
                    # break if any elements are not connected
                    if not merge:
                        break
                # merge if allowed
                if merge:
                    self.clusters[c_first].extend(self.clusters[c_second])
                    self.clusters.remove(self.clusters[c_second])

            # case 5: both are in the same cluster
            # won't happen if input is sane, but doesn't require an action either way


        return self.clusters

... and here's a working example:

inp = [
    ('A', 'B'),
    ('B', 'C'),
    ('A', 'C'),
    ('B', 'D'),
    ('D', 'E'),
    ('C', 'E')
]

test = SCCManager(inp)
print(test.get_scc())

[['A', 'B', 'C'], ['D', 'E']]