# Data structure for storing edges of a graph

I'm currently working on my masters thesis, and it's about clustering on graphs. I'm working with an idea using ants to solve the problem. I'm currently working on the implementation and am wondering exactly how well to represent the edges of the graph.

Each edge is augmented with certain information such as its pheromone value and the number of times an ant has visited that edge. I'll be working with undirected graphs, which can be end up being pretty huge (over a million vertices) and I was wondering what is the most efficient way for me to store the edges and look them up? I was thinking of sticking to a convention and store endpoints according to the one which has a lower vertex id for $v_1$ and the higher one for $v_2$ ($v_1$ and $v_2$ are the endpoints of the edge in the data structure). But I'm wondering how would I perform a look up in this case?

There is a mapping I came up with from the adjacency matrix to the edge array, but that works only if the underlying graph is a complete graph. So I came here for some suggestions as to how I should proceed because I need my lookup to be efficient while at the same time I don't want to blow up the storage space for the edges as the graphs will be huge.

• Are your graph sparse or dense? Because answer rely on that. – Bartosz Przybylski Jul 20 '13 at 19:19
• Oh I should have mentioned that, yeah they are mostly sparse graphs. Basically the graphs I'm going to be working with represent real world networks which are usually sparse. :) – muddy Jul 20 '13 at 19:29
• Sorted adjacency lists? – Raphael Jul 20 '13 at 20:52

• You keep insisting on using data structures that only make sense for dense graphs. For sparse graphs the approach is always to store, somehow, for each vertex all edges incident to it. There is no duplication - the data is only stored in one place; but there are two pointers to the data. Fast indexing could be implemented using search trees, hash tables and so on. These will allow you to implement $G[x][y]$ fast and hopefully without too much space overhead. – Yuval Filmus Jul 20 '13 at 22:56