Data structure for graphs and vectors in C

Question

I'd like to design an implementation for graphs in C.

I'm wondering what the most efficient approach in terms of both computational power and memory consumption would be.

I've looked at various open-source implementations available online, such as iGraph: https://github.com/igraph/igraph or this short lecture note about graphs (which, I suppose, is more of an educational example but sort of shows another approach): https://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)Graphs.html.

Now, iGraph uses vectors to model their graphs, where each vector is essentially an array of integers (or doubles for floating point numbers). I understand that such vectors can be useful (e.g. for 3-D analysis stuff) but to represent a graph, one only needs binary vectors, that is to say vectors where each element of a vector can only have two states are enough to represent a graph.

I also understand that, theoretically, there exist two methods to represent graphs:

1. using adjacency matrixes (a 2D-array) and
2. using adjacency lists (listing the successors for each vertex/node).

Although memory consumption for matrixes seems to be larger (except for fully cross-linked graphs where each of the n nodes is linked with n nodes), it also seems to be simpler to handle than adjacency lists (f.ex. it's easier to check for reachability of a certain vertex using simple binary matrix multiplication).

However, the approaches above seem to be more some kind of theoretical approach rather than a suggestion for an actual implementation. At least in C, it's hard to design a data structure which is dynamically resizable (i.e. not a static array) without using lists.

My initial though was to use some sort of 2D-array where each bit represents an element of the adjacency matrix. However, this array would have to be resizable (e.g. when adding a vertex). And that leads us to lists which throws away the advantage of low memory consumption of bit representations (because I'll need pointers of some sort).

I'm wondering if there are any dynamic approaches using bit representations for graphs/vectors?

I don't want to delete/recreate an entire array each time an element gets removed (that seems overkill and would waste a lot of resources).

I'm rather looking for a fancy way to store the information.

I also thought about using the first two leading bits of each char in an array to activate/deactivate a column/row, but that seems like a really bad idea because I'd have to reinvent the wheel for signed/unsigned numbers.

I've come to a point where I think there exists no way to design an efficient data structure for a bit representation of graphs/vectors (and that might be why I can't find any on the internet).

Answer 1

There are many kinds of graphs, you're apparently thinking of simple directed graphs without edge weights. Different implementations may have different associated memory/performance costs depending for example on the edge density etc., and of course there's no such thing as "most efficient in terms of both computational power and memory consumption", most algorithms imply some space/time tradeoff.

If you want to optimize for a certain use case (or class of use cases) the best approach is to first measure and compare existing solutions, analyze under which conditions they fall short of your performance goals, design alternative algorithms and measure whether they actually outperform the existing solutions. If you come up with something that's consistently better in some area you need to evaluate whether there's actual need for it.

But you need to keep in mind that in many cases, flexibility beats efficiency by a huge margin in general-purpose libraries. If you're not solving an ubiquitous problem such as media data compression, low level optimization should be done last, and only if it is clear that allocating some more hardware resources isn't an option.

Answer 2

Apparently, this question mixes up the problem of creating dynamically resizable arrays / vectors with the problem of how to store a graph. The first one can be solved the same way as dynamic vectors are implemented in other languages (for example, in C++): by implementing a vector as a data structure with a capacity apart from its size, and whenever the size is increase beyond the capacity, the capacity is doubled and the memory reallocated. You will surely find ready-made implementations in C by googling for them (like this one), and I am sure this approach can also be transferred to two-dimensional matrices.

Once you have a dynamic 2D array data structure available, you can use it for implementing graphs with adjacency matrixes in C, maybe in a "packed" (bitwise) representation, if you prefer this.