Finding connected components without building the graph first 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.
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.