0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A simple greedy algorithm that picks a vertex at random and then BFS/DFS from it should do the job, you don't need to build the graph beforehand for it. Did you try something simple like that ? $\endgroup$ – m.raynal Jul 6 at 11:02
  • $\begingroup$ @m.raynal, how so I BFS/DFS from it if I do not have the graph? I can only ask for some pair of elements whether they are connected. $\endgroup$ – Radio Controlled Jul 6 at 12:30
  • $\begingroup$ Because the belonging to a components is an equivalence relation, and this is among other transitive, maybe I could do something with a union-find data-structure somehow store, only one edge, so basically each component is a spanning tree, but I have to look closer what the union find data-structure actually is... $\endgroup$ – Radio Controlled Jul 6 at 12:34
  • $\begingroup$ btw this is a nice tutorial on the union find: youtube.com/watch?v=wU6udHRIkcc $\endgroup$ – Radio Controlled Jul 6 at 18:49
  • 1
    $\begingroup$ I suspect the core of this problem is to efficiently find the set of edges in the graph (i.e., the set of all subset relationships between all vertices). These might be relevant: cs.stackexchange.com/q/109399/755, cs.stackexchange.com/q/39976/755, cs.stackexchange.com/q/74833/755. $\endgroup$ – D.W. Jul 6 at 19:19
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Do you need the i != j? $\endgroup$ – Radio Controlled Jul 6 at 18:40
  • $\begingroup$ But this is a good start. I had an improved version for partial order production, that could probably be used here to save some more steps, but it was still too slow I think. This would have to be considerably faster than partial order production as the latter is a follow up step for each component. I am currently working on an algorithm based on union find datastructure, but I have yet to test it. Then I will post 'my' idea as well and we can compare. $\endgroup$ – Radio Controlled Jul 6 at 18:46
  • 1
    $\begingroup$ The relationship is not transitive. Consider $a=\{1,2\}$, $b=\{2\}$, $c=\{2,3\}$. Then $a \sim b$ and $b \sim c$ but it is not true that $a \sim c$. Consequently, this answer appears to be incorrect. $\endgroup$ – D.W. Jul 6 at 19:16
  • $\begingroup$ The subset relation is a partial order. It is not transitive. So c(x,x') is not transitive. But the relation defined by the connected components of course is transitive (and reflexive and symmetric). So what is "the relationship? I think in this case it is the component relation what is meant. And the algorithm should be fine, only that as far as I can see its only trick is to start comparing from i+1 onwards, and not compare if something is already in a component. Then it is the symmetric property that should ensure a later connection to the already labelled node is still found? Not sure... $\endgroup$ – Radio Controlled Jul 6 at 19:26
  • $\begingroup$ But I do not think you can do better than quadratic worst case because if there is just one connected pair hidden in all the possibly connected pairs you might just find it last without any indication where to find it. Meaning you have to compare everything to prove nothing is connected. $\endgroup$ – Radio Controlled Jul 6 at 19:39
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is it correct that the possible_supersets is still changing after where I put the comment? $\endgroup$ – Radio Controlled Jul 7 at 6:49
  • 1
    $\begingroup$ No, the algo should work fine. But note that the getting possible supersets is the expensive operation. And as I can see from your editing comment you noticed that the memory efficiency could be improved. Was your attempt at finding an algo that utilizes union find successful? $\endgroup$ – plshelp Jul 7 at 10:14
  • $\begingroup$ Still trying... but I am using your idea hashing the elements themselves. This I had not tried before. Keep you posted. $\endgroup$ – Radio Controlled Jul 7 at 10:18
  • $\begingroup$ I have used your idea and @D.W. 's suggestion and created a structure that takes the oracle away and instead gives all available specifications for a set. This runs much faster. I am not sure yet about the theoretical complexity but I think it is the only way to avoid quadratic worst case complexity - that is by modelling the structure behind the relation in question. Currently I only have this for finding minimal elements and still need to see if it can be used for connected components... $\endgroup$ – Radio Controlled Jul 8 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.