9
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Are your graph sparse or dense? Because answer rely on that. $\endgroup$
    – Bartosz Przybylski
    Commented Jul 20, 2013 at 19:19
  • $\begingroup$ 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. :) $\endgroup$
    – muddy
    Commented Jul 20, 2013 at 19:29
  • $\begingroup$ Sorted adjacency lists? $\endgroup$
    – Raphael
    Commented Jul 20, 2013 at 20:52

1 Answer 1

Reset to default
5
$\begingroup$

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".

Improve this answer
$\endgroup$
3
  • $\begingroup$ So far I've been using an adjacency list approach where for each vertex I have an array of its neighbors (each vertex is an object). This way helps because each ant knows the neighbors of every vertex. But I need choose which edge to traverse next, based on pheromone information and some other data which I will calculate. I don't want to introduce duplication so I was wondering if there was a way to represent each edge individually but be able to index them efficiently at the same time, as I'll need a lot of look up for each edge in every iteration. $\endgroup$
    – muddy
    Commented Jul 20, 2013 at 22:31
  • $\begingroup$ As an example, here is the possible mapping to the indices of the edge array if the graph was complete. In this case we already know the size of edge array will be n(n-1), where n is the number of vertices. So to translate [x][y] adjacency matrix into the array index (idx) can be as follows: if x <= y then idx = n * x - x * (x + 1) / 2 + (y - x - 1) else idx = n * y - y * (y + 1) / 2 + (x - y - 1) So say edge (5,11) or (11,5) will both translate to the same array index. But since I am not working with complete graphs, I can't think of a mapping. $\endgroup$
    – muddy
    Commented Jul 20, 2013 at 22:43
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Jul 20, 2013 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.