Finding connected components without building the graph first

Question

What are good algorithms for finding connected components in a graph defined by a set of elements X, where each x in X is itself a set of features f and a Boolean connectivity function (defined by generalization/subsumption) c(x,x')?

c(x,x') = True if generalizes(x,x') or generalizes(x',x) else False

generalizes(x,x') = True if x-x'==set([]) else False

The point is not to build the entire graph (partially ordered set) in the first place but to use c(x,x') as an oracle to query while computing component labels on the fly.

This can also be seen as finding weakly connected components of the DAG given by the partial order of the subset relation, but I think perhaps for this algorithm it could be better to have c return True more often, so I view the DAG as undirected and then define the task.

Answer 1

I have an idea for the algorithm that's slightly better than a simple dfs based on the fact that the relationship is transitive. From transitivity follows that $a \sim b \land b \sim c \Rightarrow a \sim c$. For our undirected graph this implies that every node in a connected component is connected to every other node. This yields following simple algorithm:

component = 1
mark = array of size n; initialized with 0
for i = 1 to n:
  if mark[i] == 0:
    mark[i] = component
    for j = i+1 to n:
      if i != j and mark[j] == 0 and c(X[i],X[j]):
        mark[j] = component
    component += 1

$mark$ now assigns every node a component. The runtime of the algo is $O(cn)$ where $c$ is the number of components. This would usually considerably faster than a dfs. Notice in the worst case every node is its own component leading to $O(n^2)$. But if this even occurs depends on the properties of your $c(x,y)$ function.

EDIT: The algorithm doesn't work since c(x,y) isn't transitive. My bad.

Answer 2

Okay I'm writing another answer for the sake of tidiness. I suppose that the elements of your sets are integers. Otherwise one could just use pointers to the items.

// INPUT
sets    := vector of your sets 
// BUILDING INVERTED INDEX
sets_of := map of int (an item) to vector of int (indices of all sets containing it)
for i, set in enumerate(sets):
   for item in set:
      sets_of[item].add(i)
// GETTING THE POSSIBLE SUPERSETS
possible_supersets := array (id of a sets as indices) of maps (see below)
for i, set in enumerate(sets):
   possible_supersets[i] := map int (id of a set) to int (occurrence count)
   for item in set:
      for j in sets_of[item]: 
         if j != i:
            possible_supersets[i][j]++
// VERIFYING SUPERSETS
uf := union-find-structure of size length(sets)
for i, set in enumerate(sets):
   for j in possible_supersets[i]:
      if possible_supersets[i][j] == length(set):
         uf.unify(i,j)

uf now contains all your components. The first phase takes $O(N)$ time, where $N = \sum_{i=1}^n |ith-set|$. The time taken by the second phase is a lot harder to estimate. Let's assume $a$ is the average number of sets an item is contained in. Now the second phase would have an approx. runtime of $O(Na)$ assuming amortized $O(1)$ for hash-maps.

This algo has actually a better runtime than the last one I proposed because I didn't include how long it takes to calculate $c(x,y)$ and the described algo now takes care of set intersections itself.