0

I want to put in a adjacency matrix the following graph: enter image description here

The left figure is a node link representation of an 8 node network. The right one is an adjacency matrix representation of the same network. The number of grey cells is equal to the number of links in the graph.

So I want to make a static assigned adjacency matrix. What would be the best approach in C language?

I was thinking something like:

int Matrix[8][8];

and then assign a 1 if the node is connected to other node and 0 if it is not. Also I was thinking to keep a counter for the number of neighbours a node has, like A has 2, B has 3...

But all this I want to be static not dynamic.

1
  • int Matrix[8][8] is already static / automatic (depending on where you put it).
    – cnicutar
    May 29, 2011 at 17:22

1 Answer 1

3

In C99, use enum and 'designated initializers':

enum { A, B, C, D, E, F, G, H };

static const int Matrix[8][8] =
{
    [A] = { [B] = 1, [C] = 1 },
    [B] = { [A] = 1, [C] = 1, [D] = 1 },
    [C] = { [B] = 1, [F] = 1 },
    [D] = { [H] = 1 },
    [E] = { [D] = 1, [F] = 1, [G] = 1 },
    [F] = { [E] = 1, [G] = 1 },
    [G] = { [F] = 1, [H] = 1 },
    [H] = { [E] = 1, [G] = 1 },
};

This is a direct transcription of the table you provide; I've not verified the table against the graph. The elements without an explicit initializer are zeroed, of course. You could decide to align the close braces, though it isn't necessary; I quite possibly would.

If you don't have C99 support available, you are left with manually populating the 2D array:

static const int Matrix[8][8] =
{  /* A  B  C  D  E  F  G  H */
    { 0, 1, 1, 0, 0, 0, 0, 0 }, /* A */
    { 1, 0, 1, 1, 0, 0, 0, 0 }, /* B */
    { 0, 1, 0, 0, 0, 1, 0, 0 }, /* C */
    { 0, 0, 0, 0, 0, 0, 0, 1 }, /* D */
    { 0, 0, 0, 1, 0, 1, 1, 0 }, /* E */
    { 0, 0, 0, 0, 1, 0, 1, 0 }, /* F */
    { 0, 0, 0, 0, 0, 1, 0, 1 }, /* G */
    { 0, 0, 0, 0, 1, 0, 1, 0 }, /* H */
};

If you have the graphs presented in some text form, you could write a Perl, Python, or Awk script (to name but three suitable languages) to generate the output for you automatically.


Note: if you want to keep a counter of the number of neighbours that an element has (meaning, I assume, the number of neighbours that can be reached from this node, rather than the number of neighbours that can reach this node - or arrows out rather than arrows in), then you need a more complex structure than a simple 2D array. You'd probably use an array of structures:

enum { A, B, C, D, E, F, G, H };
enum { MAX_GRAPH_SIZE = 8 };

typedef struct Node
{
    unsigned char n_out;
    unsigned char nodes[MAX_GRAPH_SIZE];
} Node;

static const Node Matrix[MAX_GRAPH_SIZE] =
{
    [A] = { .n_out = 2, .nodes = { [B] = 1, [C] = 1          } },
    [B] = { .n_out = 3, .nodes = { [A] = 1, [C] = 1, [D] = 1 } },
    [C] = { .n_out = 2, .nodes = { [B] = 1, [F] = 1          } },
    [D] = { .n_out = 1, .nodes = { [H] = 1                   } },
    [E] = { .n_out = 3, .nodes = { [D] = 1, [F] = 1, [G] = 1 } },
    [F] = { .n_out = 2, .nodes = { [E] = 1, [G] = 1          } },
    [G] = { .n_out = 2, .nodes = { [F] = 1, [H] = 1          } },
    [H] = { .n_out = 2, .nodes = { [E] = 1, [G] = 1          } },
};

I'm not at all convinced that the savings compared with computing the number of arrows out of (or into) a node warrants the extra complexity. Notationally, when referencing elements of the array, you'd now have to write:

Matrix[i].nodes[j]

instead of the simpler:

Matrix[i][j]
2
  • 3
    unsigned char is probably going to be enough for this
    – IanNorton
    May 29, 2011 at 17:59
  • @IanNorton; I agree, except that the question explicitly said int Matrix[8][8];. May 29, 2011 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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