A partition-generating algorithm

Question

I come across this problem in designing a database, but it would seem to have basic application to networks:

Given a set $J=\{j_1,j_2,\dots,j_k\}$, and a function $\mathscr M$ that maps each element of $J$ onto some subset of $J$. I.e., $\mathscr{M}: j_i \rightarrow K_i$, where $K_i \subset J$.

The set $J$ can refer to vertices of a graph, and each $K_i$ to the set of vertices that share an edge with $j_i$. The graph thus formed will be partitioned into a certain number of disjoint subgraphs. I don't know the terminology from set theory.

What is an algorithm that I can use to determine which subgraph each $j_i$ (for a given $J$ and $\mathscr{M}$) belongs to?

After receiving the accepted answer, I prepared the following (in javascript) which takes as input an array of arrays representing $K_i$ (assumed to be coindexed with $J$) and returns a result array $R$ also coindexed with $J$) such that $R_i$ specifies the partition that $j_i$ belongs to.

function pointer (M){
        var g=0; var R =[];
        for(i in M){
                if (R[i]==undefined){
                        g++;
                        R[i]=g;
                }
                for (k in M[i]){
                        var e=M[i][k];
                        if( R[e]==undefined ){
                                R[e]=R[i];
                        }
                        else{
                                R[i]=R[e];
                        } 
                }
        }
        return R;
}

Answer 1

We don't need an algorithm. This is purely a problem of data structuring.

You may as well assume that $J=[n]:=\{1,2,\ldots,n\}$. Then the map $${\cal M}:\quad J\to{\cal P}(J),\qquad i\mapsto K_i\subset J$$ defines an $(n\times n)$-matrix $M=[m_{ik}]$ as follows: $$m_{ik}:=\left\{\eqalign{1\quad&(i\in K_k)\cr 0\quad&( i\notin K_k)\ .\cr}\right.$$ In this way the $k^{\rm th}$ column of $M$ tells you which numbers are in the set $K_k={\cal M}(k)$, and the $i^{\rm th}$ row of $M$ tells you in which sets $K_k$ the number $i$ is occurring.

If ${\cal M}$ is given as a list of the $K_k$ $(1\leq k\leq n)$, then you use these data to set up the matrix $M$ column for column. Now address the individual rows and obtain the "transpose" information you like to have.

Answer 2

Ignoring the graph analogy, I think you're essentially looking for $\mathscr{M}^{-1}[\mathscr{M}[j_i]]$, the pre-image (or inverse image) of the image of $j_i$.

One algorithm to find this would be to loop through each element in $J$ and check if they map to the same $K_i$ as your chosen element $j_i$.

If the $K_i$ are disjoint (which they will be if they are defined as the images of disjoint sets of $j_i$, that is, $j_i$ maps to only one $K_i$), then the set of pre-images should also be disjoint (after removing any duplicates).