Design of vertex/edge indexing

[lindahua]

In a lot of algorithms, we have to use vertex or edge as indices to retrieve corresponding attributes such as colors and weights.

In my original design, this is through the vertex_map and edge_map interface. This is how it works:

colors[vertex_index(v, g)]
weights[edge_index(v, g)]

The methods vertex_index and edge_index are used to map an vertex or edge into an integer index, which can then be used to get the attributes from an array (or an array-like object). The index can be directly stored within the vertex or in a map associated with the graph.

Some recent applications indicate that this approach might not be flexible enough, especially in a dynamic context where vertices/edges can be added or removed after a graph is constructed.

I think @deinst's property inspector might be a better way forward. For example, for Diijkstra's algorithm, instead of requiring the graph to implement the edge_map interface, we require the user of the algorithm to supply a weight map object that implements the following method:

get_edge_attribute(p, v, g)
# p: the property inspector object
# v: the vertex 
# g: the graph

This may probably make removal or temporary censoring of vertices or edges easier.

With this new interface, we no longer require vertices to be added such that their indexes are in consecutive ascending order. This also provides greater flexibility in some applications.

Any thoughts?

cc: @deinst, @kmsquire, @pozorvlak

[deinst]

This seems doable (I had started something along these lines in my last PR.) I'll play with it a bit. First, I want to get things working with graphs where the vertices and edges are unindexed (these are useful in the majority of cases where convenience and ease of use are of more importance than mindblowing speed)

[kmsquire]

I like this idea. It seems simpler than @deinst's PR (although that may change as it's implemented).

As in my comment there (#107 (comment)) it would seem that a few common inspectors could be provided through a simple interface.

[mlubin]

See #135 for recent related changes.

[sbromberger]

See also #143 for discussion on why keeping attributes/metadata inside graph structures might not be ideal.