ben_dover's blog

Storing Adjacency List with Edge Weight
By ben_dover, history, 5 years ago, In English

For storing an adjacency list with edge weights, the (apparently) standard way is to store a vector of vector of pairs (vertex end, weight). I realized recently that it is possible to store the adjacency list as for an unweighted graph and store the edge weights separately (in a map or unordered map). noedne pointed out that storing the weight in the adjacency list is more organized. In theory by storing the edge weights separately we can reuse algorithms for unweighted graphs that take the unweighted adjacency list.

Which do you think is better?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

The map/unordered_map makes it a lot slower, probably not worth it.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok, what about unordered_map? It should have constant insert and lookup time (though amortized, and not always like when adding (vertex, weight) pair)

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Maps are pretty slow and it's not just about asymptotic $$$O(1)$$$ performance, constant factors matter too. Try timing basic operations on arrays/vectors vs. unordered_maps.

One thing that's pretty common (for example, in flow implementations) is to number your edges. Then your adjacency lists store edge ids and you can keep separate arrays for destination, capacity, and so on.

You could also make edge structs with named members and templatize your algorithms.

→ Reply