Data structure for storing edges of a graph

Problem Detail: 

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.

Asked By : muddy

Answered By : Yuval Filmus

If your graph is sparse then you should store it using adjacency "lists", though you probably want something more efficient than a list (or perhaps you don't, depending on usage). It's simplest if you store each edge at both endpoints. This can be implemented in many ways, for example you can store all data in some big array, and store only pointers in the adjacency "lists".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13364