Added vertex property inspectors.

[deinst]

Currently, a-star search is the only algorithm using any vertex properties (for the distance heuristic), so the a-star code was changed.

The a-star code used the vertex type to index into the colormap, so would only work with graphs with integer vertex type. I generalized and abstracted away the colormap type. This probably should be a separate commit.

It may seem that I abstracted the colormap too far, but allowing the colormaps to be hashtables when the vertex_map or edge_map is not available will allow us to use hash based graphs a la networkx. Then we will be able to add and delete vertices and edges, and the algorithms will only be a constant factor slower (assuming a good dict implementation).

The current implementation seems to be transparent after the compiler does its magic.

If this is OK, I'll make a hash based graph type (actually 2 because it makes sense to do directed and undirected graphs separately.

[deinst]

Thanks. I'm still learning the julia module system. (and the language in general)

[kmsquire]

No problem. You still need to import Base.setindex!.

[deinst]

Do I really need to import Base.setindex! ? As I understand things, setindex! is an operator, and so should be implicitly imported. I'll fix the other export screwups.

[kmsquire]

Nope, you're right!

[kmsquire]

How about allowing the property inspectors to be constructed with something like

const_inspector = vertex_inspector(g, 0)

color = zeros(num_vertices(g), Int)
color_inspector = vertex_inspector(g, color)

weight = Dict{ExVertex, Float64}()
weight_inspector = vertex_inspector(g, weight)

fn(v) = v.weight * 2.6
fn_inspector = vertex_inspector(g, fn)

You could still have direct construction via the type constructors, but it would be nice to have a uniform (and short) interface that did the right thing most of the time.

Good bad idea?

[pozorvlak]

I like @kmsquire's idea of concise inspector-construction functions.

[deinst]

I too think it is a good idea. It is a bit more complicated, as the inspectors are also carriers of type information, so the last example would have to be something like

fn(v) = v.weight * 2.6
fn_inspector = vertex_inspector{Float64}(g, fn)

because functions have no type. If I have time tonight, I'll try to get to it.

[kmsquire]

Function calls can't have types either, at least in {}. But the types can be passed as parameters easily enough.

fn(v) = v.weight * 2.6
fn_inspector = vertex_inspector(g, fn, Float64)

When constructing the type, is knowing the graph useful? In your current PR, the graph is not included in the inspector (or constructors), but it could give the expected vertex and edge type:

function vertex_inspector{V,E}(g::AbstractGraph{V,E}, fn::Function, rettype::Type)
    ...
end

[lindahua]

In my mind, we don't really have to introduce AbstractVectorPropertyInspector or similar abstract types. Conceptually, an inspector can be a number, an array or a more sophisticated object. The only requirement for an inspector a should be that the following works:

vertex_property(a, v, g)

We can however introduce a series of fallback functions, so that people can simply grab a constant value or an array and supply it as a property inspector, as

vertex_property{V}(a::AbstractArray, v::V, g::AbstractGraph{V}) = a[vertex_index(v, g)]
vertex_property{V}(a::Number, v::V, g::AbstractGraph{V}) = a

Of course, people can implement more complex logics if they want.

[deinst]

@lindahua We also need to implement vertex_property_requirement but your point is extremely valid. I probably tend to be too prejudiced towards requiring too much typechecking of parameters.

[kmsquire]

FWIW, I concur with @lindahua that the interface can be much less strict.

[pozorvlak]

The AbstractPropertyInspector types are rather too Java-ish for my taste.

[deinst]

Guilty as charged, I suppose. The mortgage company likes being paid:)

The one other hitch with using generic objects is that we need to add a function to get the type returned. This is not difficult, but I have not done enough testing to know if it interferes with the compiler magic. This should not be a large problem, as we can pass the type in to the low level function that does the work. (We do this implicitly for Dijkstra and Bellman-Ford). My original reason for using inspector objects instead of the more natural functions was that the inspectors ended up being considerably faster.

I'll try to get something done tonight.

[deinst]

Ok, this backs out some controversial changes and implements @lindahua's inspectors. I am of two minds about this, the interface is cleaner, but it can generate some cryptic error messages for simple errors.

[deinst]

This last set of changes removes the attribute and function inspectors, as they could not identify their type, and defaulting it to Float64 was just wrong. I have moved them into the appropriate tests. I also added a simple example of vertex_properties to the documentation.

[AlainLich]

Hi @deinst , I wonder how this interacts with the attributes mechanism found in

./src/dot.jl
./src/common.jl
./src/Graphs.jl
./src/random.jl

I have proposed PR #184 to ensure that attributes of vertices get shown in to_dot output (besides fixing the behaviour that made non connected vertices invisble in .dot output). Should the two mechanisms be kept (one for display, the other to provide data in algorithms) or merged?

CP: @timholy