Static allocated adjacency matrix Graph in C

I want to put in a adjacency matrix the following graph:

The left figure is a node link represen开发者_如何学运维tation 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.

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]