Vertices and Edges

Vertex Types

A vertex can be of any Julia type. For example, it can be an integer, a character, or a string.

This package provides two specific vertex types: KeyVertex and ExVertex. The definition of KeyVertex is:

immutable KeyVertex{K}
    index::Int
    key::K
end

Here, each vertex has a unique index and a key value of a user-chosen type (e.g. a string).

The definition of ExVertex is:

type ExVertex
    index::Int
    label::UTF8String
    attributes::Dict{UTF8String,Any}
end

The ExVertex type allows one to attach a label as well as other attributes to a vertex. The constructor of this type takes an index and a label string as arguments. The following code shows how one can create an instance of ExVertex and attach a price to it.

v = ExVertex(1, "vertex-a")
v.attributes["price"] = 100.0

The ExVertex type implements a vertex_index function, as

vertex_index(v)

returns the index of the vertex v.

SimpleGraph is a special case where the vertices are of type Int and store both their index and identity. In all other graphs, Int vertices are unordered indices.

Edge Types

This package provides two edge types: Edge and ExEdge. The former is a basic edge type that simply encapsulates the source and target vertices of an edge, while the latter allows one to specify attributes.

The definition of Edge is given by

immutable Edge{V}
    index::Int
    source::V
    target::V
end

typealias IEdge Edge{Int}

The definition of ExEdge is given by

type ExEdge{V}
    index::Int
    source::V
    target::V
    attributes::Dict{UTF8String,Any}
end

ExEdge has two constructors, one takes index, source, and target as arguments, while the other use all four fields.

One can either construct an edge directly using the constructors, or use the add_edge methods for graphs, which can automatically assign an index to a new edge.

Both edge types implement the following methods:

edge_index(e)

returns the index of the edge e.

source(e)

returns the source vertex of the edge e.

target(e)

returns the target vertex of the edge e.

A custom edge type E{V} which is constructible by E(index::Int, s::V, t::V) and implements the above methods is usable in the VectorIncidenceList parametric type. Construct such a list with inclist(V,E{V}), where E and V are your vertex and edge types. See test/inclist.jl for an example.

Edge Properties

Many algorithms use a property of an edge such as length, weight, flow, etc. as input. As the algorithms do not mandate any structure for the edge types, these edge properties can be passed through to the algorithm by an EdgePropertyInspector. An EdgePropertyInspector when passed to the edge_property method along with an edge and a graph, will return that property of an edge.

All edge property inspectors should be declared as a subtype of AbstractEdgePropertyInspector{T} where T is the type of the edge property. The edge propery inspector should respond to the following methods.

Three edge property inspectors are provided ConstantEdgePropertyInspector, VectorEdgePropertyInspector and AttributeEdgePropertyInspector.

ConstantEdgePropertyInspector(c) constructs an edge property inspector that returns the constant c for each edge.

VectorEdgePropertyInspector(v) constructs an edge property inspector that returns v[edge_index(e, g)]. It requires that g implement the edge_map interface.

AttributeEdgePropertyInspector(name) constructs an edge property inspector that returns the named attribute from an ExEdge. AttributeEdgePropertyInspector requires that the graph implements the edge_map interface.