CODEWITHSUNDEEP
cadjacency-matrixneighbours
mugglepot
mugglepot

Reputation: 27

C programming two-hop neighbors

I am not sure how to get my two-hop neighbors correctly. It's almost correct but on my output, I don't want to include the same vertex. For my output now if vertex 0 is 0, it says "vertex 0: 0..... I want to skip the vertex it is currently looking at.

Please help me, are my codes for two hop wrong?

this is my codes:

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#define M 20
#define N 20
int main()
 {
int i, j, x, a, b;
int G[20][20] = { { 0 } };
/*creaate random adjaceney matrix*/
printf("==================================================\n");
printf("Welcome to my Graph Processing tool!\n\n");

srand(time(NULL));
for (i = 0; i < M; i++) {
    for (j = 0; j < N; j++) {
        if (i == j) {
            G[i][j] = 0;
        }
        else {
            G[i][j] = rand() % 2;
            G[j][i] = G[i][j];
        }
    }
}
/*check whether the whole row equals to 0*/
for (j = 0; j < N; j++) {
    if (G[j] == 0) {
        x = rand() % 20 + 1;
        G[x][j] = G[j][x] = 1;
    }
    /*print the matrix G*/
    else
    {

        printf("The adjacency for graph G is\n");
        for (i = 0; i < M; i++) {
            for (j = 0; j < N; j++) {
                printf("%d ", G[i][j]);
            }
            printf("\n");
        }
    }
}

/*all one-hop neighbors*/
printf("\nList of one-hop neighbors:");
for (i = 0; i < M; i++) {
    printf("\nVertex %d: ", i);
    for (j = 0; j < N; j++) {
        if (G[i][j] == 1) {

            printf("%d ", j);
        }
    }
}
printf("\n===================================\n\n");


/*two-hop neighbors*/

    for (i = 0; i < M; i++) {
        printf("\nVertex %d: ", i);
        for (j = 0; j < N; j++) {
            if (G[i][j] == 0) {

                printf("%d ", j);
            }
        }
        }

}

printf("\n============================================\n");


system("pause");
return 0;
}

This is my output:

One hop Two hop

Upvotes: 0

Views: 1061

Answers (2)

gasteigerjo
gasteigerjo

Reputation: 107

The answer provided by @Jake only works for node 0. For only looking at different nodes you need to do

for (j = 0; j < N; j++) {
    if (i != j && G[i][j] == 0) {
        printf("%d ", j);
    }
}

Furthermore, you are assuming that all nodes without an edge are two-hop neighbors. This is not correct. One way to calculate the actual two-hop neighbors would be ((A + I)^2 > 0) - ((A + I) > 0), where I is the identity matrix.

Also, you can code this via a three-layer loop:

int node, neighbor, neighbor2;
for (node = 0; node < N; node++) {
    printf("\nVertex %d: ", node);
    for (neighbor = 0; neighbor < N; neighbor++) {
        if (G[node][neighbor] == 1) {
            for (neighbor2 = 0; neighbor2 < N; neighbor2++) {
                if (node != neighbor2 && G[neighbor][neighbor2] == 1) {
                    printf("%d ", neighbor2);
                }
            }
        }
    }
}

Note that per definition M=N, so I've just used N. Also, this might print some 2-hop neighbors twice. You might want to do some filtering before printing.

Upvotes: 1

Jake
Jake

Reputation: 78

Couple things to note here.

Be more descriptive with your variable naming, it would have made this a lot easier to read.

M-ROWS, N-COLS, G-Graph

When you loop through each row, you initialize j to 0. This includes the vertex that you are wanting to leave out.

for (j = 1; j < N; j++)

Upvotes: 0

Related Questions