***************************
Design
***************************

This document looks at implementation of the same adjacency list data structure
that is used in Boost.Graph. It is a string over vertex storage, where
each vertex stores a string of neighbors. The vertices aren't necessarily
indexed in any way. An adjacency list knows which entry is a neighbor of
which other entry, but the string of vertices and string of neighbors
may be stored many different ways.

Vertex Descriptor
---------------------

The ``vertex_descriptor`` in Boost.Graph is an opaque handle to a vertex.
It is usually a pointer to the vertex, except in one special case.
For adjacency lists constructed with vector types for both the vertex list
and neighbor lists, the ``vertex_descriptor`` is an integer.

Instead of using a dictionary at vertices and edges to store properties,
it is possible to append those properties to the vertex type and neighbor
type. In the following example, note that the type of the VertexDescriptor
used in the Neighbor class is determined by the Vertex class. It's recursive.::

  immutable type Neighbor{VertexDescriptor,EdgeProperty}
    n::VertexDescriptor
    edge_property::EdgeProperty
  end

  immutable type Vertex{VertexProperty,EdgeProperty}
    # This is the recursive bit, where it makes pointers to itself.
    v::Deque{Neighbor{Vertex{VertexProperty,EdgeProperty},EdgeProperty}
    vertex_property::VertexProperty
  end

  type AdjacencyList{VertexProperty,EdgeProperty}
    vertices::Deque{Vertex{VertexProperty,EdgeProperty}}
    is_directed::Bool
  end

This setup would work fine for the Deque type, but Boost.Graph uses
C++ vector, list, or set types. An array type would use integers for
indexing.::

  immutable type Neighbor{VertexDescriptor,EdgeProperty}
    n::VertexDescriptor
    edge_property::EdgeProperty
  end

  immutable type Vertex{VertexProperty,EdgeProperty}
    # This is the recursive bit, where it makes pointers to itself.
    v::Vector{Neighbor{Int,EdgeProperty}
    vertex_property::VertexProperty
  end

  type AdjacencyList{VertexProperty,EdgeProperty}
    vertices::Vector{Vertex{VertexProperty,EdgeProperty}}
    is_directed::Bool
  end

Parameterizing Storage
------------------------

It is difficult in Julia to create a type which changes
storage class depending on a parameter type. For instance,
this is not allowed::

  type Foo{C,V}
    container::C{V}
  end

That it is not allowed is specified in an issue 3359,
https://github.com/JuliaLang/julia/issues/3359.
Although it is not allowed, this works (for now)::

  cconstruct(x::TypeVar, y)=x
  cconstruct(x::Union(DataType,TypeConstructor), y)=x{y}

  type Foo{C,V}
    container::cconstruct(C,V)
  end

  Foo{Vector,Int}(Array(Int, 0))

Julia does three passes through the type, two
where it calls ``cconstruct(x::TypeVar, y)`` and then
one where it passes in the given type. At that point,
the function can do calculations on the incoming types.

If the code can vary the container type parametrically,
then it helps to abstract across the container types
the exact interface this code requires. This will
look something like the Boost ``property_map`` interface.
There are two containers in this class, one for
vertices and one for neighbors of a vertex,
and they are used slightly differently.
The ``vertex_descriptor`` will always be some sort
of key, whether it is a reference to an object in
a Deque or an Int pointing into a Vector.
On the other hand, the ``edge_descriptor`` in Boost.Graph
isn't just a pair of vertices. It's
a pair of (vertex_descriptor, edge_pointer). In Julia,
that becomes (vertex_descriptor, edge instance), no
matter whether neighbor edges are stored in a Set, Deque,
or Vector.

To this end, there are a set of methods defined for
each type of container. Here are two.::

	container_key{V}(::Type{Vector{V}})=Int
	container_value{V}(::Type{Vector{V}})=V
	container_construct{V}(::Type{Vector{V}})=Array(V, 0)
	container_push{V}(c::Vector{V}, v::V)=begin push!(c, v); length(c) end
	container_add{V}(c::Vector{V}, args...)=begin v=V(args...); push!(c, v); v end
	container_add_key{V}(c::Vector{V}, args...)=begin push!(c, V(args...)); length(c) end
	container_get{V}(c::Vector{V}, k::Int)=c[k]
	container_set{V}(c::Vector{V}, k::Int, v::V)=begin c[k]=v; k end
	container_iter{V}(c::Vector{V})=1:length(c)
	container_value_iter{V}(c::Vector{V})=c

	container_key{V}(::Type{Deque{V}})=V
	container_value{V}(::Type{Deque{V}})=V
	container_construct{V}(::Type{Deque{V}})=Deque{V}()
	container_push{V}(c::Deque{V}, v::V)=begin push!(c, v); v end
	container_add{V}(c::Deque{V}, args...)=begin v=V(args...); push!(c, v); v end
	container_add_key{V}(c::Deque{V}, args...)=container_add(c, args...)
	container_get{V}(c::Deque{V}, k::V)=k
	container_set{V}(c::Deque{V}, k::V, v::V)=begin c[k]=v; v end
	container_iter{V}(c::Deque{V})=c
	container_value_iter{V}(c::Deque{V})=c

These abstract the container type, detecting the
type of the container that was created.

Lastly, Boost.Graph has a special integer ``vertex_descriptor``
when both containers are vectors, but the integer descriptor
is possible when only the vertex container is a vector. As well,
it is possible to use a Dict to store vertices (which would
also be possible in Boost if it weren't already so complicated),
so this container is included in the code, too.