ben_dover's blog

By ben_dover, history, 5 weeks 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

»
5 weeks 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.

  • »
    »
    5 weeks 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)

»
5 weeks 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.

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

    Constant factors :P

    The edge numbering is good to keep in mind.

    For my (vertex, weight) pair I currently use a struct with named members since it is a little easier for me to think about than pair members first and second. For now I use long longs for values which should be good for most problems though in the future maybe templates will help.