A draft algorithm for finding connected components in an undirected graft

AdjacencyExperiment.py

import numpy
import json
import argparse
import select, sys
from copy import deepcopy
from itertools import product

# usage:
#
# ❯ python AdjacencyExperiment.py AB,CD
#
#     This graph has  2 connected components.
#     [["C", "D"],["A", "B"]]
#
# or
#
# ❯ echo '[["A","B"],["C","D"]]' | python AdjacencyExperiment.py
#
#     This graph has  2 connected components.
#     [["C", "D"],["A", "B"]]


class Graph:

    def __init__(self, edge_list):
        """
        Initialize a graph from a list of edges
        Each edge is a pair of objects that represent nodes

        e.g. [(A,B), (C,D)] indicates a four-node graph with two edges and two
        connected components.
        """

        # get unique vertices and edges
        self.vertices = set()
        self.edges = set()
        for edge in edge_list:
            if len(edge) != 2:
                raise Exception(f"{edge} doesn't look like an edge")
            if edge[0] != edge[1]:
                self.edges.add(edge)

            self.vertices.add(edge[0])
            self.vertices.add(edge[1])

        # store lookups:
        # node -> idx
        self.idx_of = {}
        for i, vertex in enumerate(sorted(list(self.vertices))):
            self.idx_of[vertex] = i

        # idx -> node
        self.node_at = { v : k for k, v in self.idx_of.items() }

        # initialize adjacency matrix with 0's
        side_len = len(self.vertices)
        empty_row = [0 for _ in range(side_len) ]
        self.adjacency = [ deepcopy(empty_row) for _ in range(side_len) ]


        # a list of cell coordinates in the adjacency matrix
        n = len(self.vertices)
        self.adjacency_indices = list(product(range(n), range(n)))

        # populate adjacency matrix diagonal with 1's
        #for i in range(n):
        #    self.adjacency[i][i] = 1

        # populate adjacency matrix
        for edge in edge_list:
            one = self.idx_of[edge[0]]
            other = self.idx_of[edge[1]]
            self.adjacency[one][other] = 1
            self.adjacency[other][one] = 1

    def from_string(comma_sep):
        """
        Initialize a graph from a comma-separated string of edges
        Each node gets a one letter name
        Each edge is a two-letter string
        """

        # comma_sep
        # AB,CD

        edge_strs = comma_sep.split(',')
        #["AB", "CD"]

        edges = list(map(lambda x: tuple(x), edge_strs))
        #[("A", "B"), ("C", "D")]

        return Graph(edges)

    def to_string(self):
        edgs_strs = list(map(lambda x: f"{x[0]}{x[1]}"))
        return ','.join(edge_strs)


    def components(self):

        MA = numpy.matrix(self.adjacency)

        def zs(M):
            l = []
            for (i, j) in self.adjacency_indices:
                if (numpy.array_equal(numpy.matrix(M[i,j]),numpy.matrix([[0]]))):
                    l.append([i,j])
            return l

        C = MA
        D = MA
        while True:
            D = numpy.add(numpy.matmul(MA,C),C)
            if zs(C) == zs(D):
                break
            else:
                C = D

        def zs1(M):
            l = []
            for a in range(len(self.vertices)):
                if (numpy.array_equal(numpy.matrix(M[0,a]),numpy.matrix([[0]]))):
                    l.append(self.node_at[a])
            return l
        ocold = []
        for k in range(len(self.vertices)):
            if zs1(C[k]) not in ocold:
                ocold.append(zs1(C[k]))
        print('This graph has ',len(ocold), 'connected components.', file=sys.stderr)

        return ocold


if __name__ == "__main__":

    # if stdin has data, read it as json
    if select.select([sys.stdin,], [], [], 0.0)[0]:
        graph = Graph(list(map(tuple, json.loads(sys.stdin.read()))))

    # if data is an arg, read it as string
    else:
        parser = argparse.ArgumentParser()
        parser.add_argument("edges", help="edges like: AB,CD,BF")
        args = parser.parse_args()
        graph = Graph.from_string(args.edges)

    print(json.dumps(graph.components(), indent=2))

test cases

# with no trivial components, all is well:
❯ python AdjacencyExperiment2.py AB,CD         
These were the trivial nodes: set()
These were the nontrivial nodes: {'D', 'A', 'B', 'C'}
The graph has  2 connected components.
[
  [
    "C",
    "D"
  ],
  [
    "A",
    "B"
  ]
]

# with trivial components, the count is right but the composition is wrong
❯ python AdjacencyExperiment2.py AB,CD,EE,FA,ZZ
These were the trivial nodes: {'E', 'Z'}
These were the nontrivial nodes: {'F', 'A', 'B', 'C', 'D'}
The graph has  4 connected components.
[
  [
    "C",
    "D",
    "E", <-- included in error
    "Z"  <-- included in errror
  ],
  [
    "A",
    "B",
    "E", <-- included in error
    "F",
    "Z"  <-- included in error
  ],
  [     <-- this one should show the complement instead, 'E' only
    "A",
    "B",
    "C",
    "D",
    "F",
    "Z"
  ],
  [     <-- this one should show the complement instead, 'Z' only
    "A",
    "B",
    "C",
    "D",
    "E",
    "F"
  ]
]