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:
- using adjacency matrixes (a 2D-array) and
- 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).