Search code examples
c++boostboost-graph

What is the runtime complexity of `boost::edge()` on an adjacency_list with vecS?

I have an undirected adjacency_list graph defined as this:

typedef boost::adjacency_list<
               boost::vecS,
               boost::vecS, boost::undirectedS,
               boost::no_property,
               boost::property<
                 boost::edge_weight_t, int, EdgeInfo> 
            > weighted_graph;

For my algorithms class, my program was too slow and only passed one of four test sets in terms of speed. I then did one small change that made my program pass all the time limit tests: I stopped using weightmap[boost::edge(u, v, G).first].

Instead I looped over all edges once, and stored each edge weight twice in a 2D Vector, so that I could look it up with weightvec[u][v] instead.

I was not able to find any documentation on the runtime complexity of boost::edge(). I expected it to be constant, but it seems like that's not true. What is the complexity in terms of number of edges and vertices in the graph?

I considered if it might be due to the access to the weight property map instead, but if I still use the weightmap and store the edge descriptors, I still see that speedup.

Solution

  • edge(v,u) searches for an edge. Why would you do this? If Since² you know the edges exist anyways, you should probably either:

    • be using an adjacency matrix instead
    • or already have a hold of the edge descriptor of the edge you knew existed (instead of searching for it)

    Q. I was not able to find any documentation on the runtime complexity of boost::edge().

    I guess it's sort of implied by the concept of an adjacency list (see below). Also, it would be tricky to formulate due to the many generic type parameters that influence this.

    Q. I expected it to be constant, but it seems like that's not true.

    So, let's see. An adjacency list is ... a list of adjacencies. For a graph, it it would be a list of vertices, with for each vertex a list of "adjacencies" - that is, "edges¹", represented by their target vertex (the source is already implied by the datastructure).

    Finding an edge in graph g by (v,u) vertex endpoints requires:

    • a search for (v) on the primary list
    • search for (u) on the local set of adjacencies

    Since you chose vecS/vecS both could be linear searches.

    Luckily, because vecS for the vertices is random-access AND the element index is by definition the vertex_index it will be O(1). (where n is num_vertices(g)) and the second O(m) (where m is the average out-degree of vertices).

    Q. I considered if it might be due to the access to the weight property map instead, but if I still use the weightmap and store the edge descriptors, I still see that speedup.

    Yeah, the property maps aren't doing the searching:

    CONCLUSION

    There's some time to be gained, probably, by e.g. using other container selectors. However, from intuition I'm gussing you were really looking for adjacency matrix or even implicit graphs (more).

    ¹ In this case. In directed situations you would say outgoing edges. Boost also has a "birectionalS" representation where each list entry holds a reundant list of incoming edges, to optimize for some kinds of algorithms

    ² This can be deduced from the fact that you unconditionally use .first without checking the search result. Doing that on a non-existent edge is probably UB