Member Avatar for sudipta.mml

Hi All,

I am looking for an algorithm/program that separates all of the data chunk i,e how many chunks are there. Moreover, that program will also be giving information of the size of the chunks and which are the elements. I am explained my problem by this following example

suppose I have three chunk of data points and one isolated point. each chunk of data are related by some rule.

chunk1: 1,2,8,9,11,12; connectivity: 1-2, 2-12,2-11,8-9,8-11
chunk2: 4,7,10; connectivity: 4-7,7-10,4-10
chunk3: 5,6; connectivity 5-6
chunk4: 3

Therefore, the total no of data points in this system are 12 and the dimension of connectivity matrix will be 12X12. I have set 1 if the two elements are connected in this matrix and the rest of the elements are 0. Moreover, the diagonal elements of this matrix was st to 0 because connection within the same element is meaningless. Therefore, the matrix, h(i,j), looks like

0 1 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 1 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0

Now, my question is, how do I find the the number of chunks and which elements constitute those chunks for a given matrix.

I have thought by this way:
1. go along first row, if there is any 1 then find out that column (j) and set that element and its conjugate as 0 i,e h(i,j)=h(j,i)=0 as that matrix is always symmetric. the element i is the first element of the first cluster.
2. In the next step go to the jth row and repeat the same procedure.
3. when there is no 1 along the row then the first cluster has been sorted out. repeat the same thing for 2nd ..3rd ...nth cluster until the all elements of that matrix is 0
4) when all elements of that matrix is 0 then computation is finished. The rest of the elements will be isolated elements.

However, I am facing difficulty to implement this algorithm using fortran. This is because if a row contains more than one 1 (i,e a element is connected simultaniously with more than one element) then how do I go to those rows simulataniously.

Can anyone help me in this regard? any logic or any idea or any program will be helpful for me.

Thanks in advance
Sudipta

  • 2 Contributors
  • 1 Reply
  • 221 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by rubberman

Dani AI

Generated

As described, this is the standard connected-components problem on an undirected graph: the adjacency matrix marks edges between points, and the goal is to report how many connected groups (chunks) exist and which nodes belong to each. ’s request for context is reasonable; two robust, easy-to-implement strategies avoid the “simultaneous row-walking” difficulty.

One approach is graph traversal (BFS or DFS). Maintain a boolean visited array of size N. For i = 1..N, if visited[i] is false, start a queue (BFS) or stack (DFS) with i, mark it visited, and expand: for each neighbor j with adj[i][j] = 1 and not visited, mark visited and enqueue/push j. When the expansion finishes, the collected nodes form one component. With an adjacency matrix this is O(N^2); with an adjacency list it’s O(N + E).

A second approach is Disjoint-Set (Union-Find): scan the symmetric matrix once (only j>i to exploit symmetry), and for every adj[i][j] = 1 perform union(i, j). After all unions, group nodes by their find(root) value to produce components. Union-Find is concise, fast (near-linear) and avoids recursion or manual traversal bookkeeping.

Example pseudocode (conceptual):

visited[1..N] = false
for i = 1..N
  if not visited[i]
    start queue with i; visited[i]=true
    component = []
    while queue not empty
      v = dequeue()
      component.append(v)
      for j = 1..N
        if adj[v][j]==1 and not visited[j]
          visited[j]=true; enqueue(j)
    output component

Fortran notes and cautions: Fortran is 1-based by default; be careful if porting Python examples (0-based). Older Fortran requires the recursive attribute for recursive functions — iterative BFS/stack is simpler and safer. Represent the queue as an integer array (circular buffer) and mark nodes visited at enqueue time to avoid duplicates. If N is large and the matrix is sparse, convert to adjacency lists first or use Union-Find to avoid scanning many zeros. Finally, validate with a small test case, print component sizes and member lists, and verify indices and symmetry to avoid off-by-one errors.

Member Avatar for rubberman

Some context would be helpful, to know what your purpose is and what you mean by a "data chunk".

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.