RFC: Parameterized Graphs {T<:Integer} about lightgraphs.jl

[jpfairbanks]

What is the source of 2^128 nodes? you don't actually have more than 2^64 nodes right? Another solution to this problem I have seen before is to map names (arbitrarily large strings) to int64 and then use the int64 to index the graph. A Dict{T, Int} is appropriate for this. Then you can have graphs indexed by strings as well as by int128 or int32.

[sbromberger]

IPv6 addresses are 128 bits long. It would be convenient to be able to do graph analysis of v6 network traffic without having a translation dict.

Also, for IPv4, I only need 32 bits. It might be more performant to be able to create a graph with smaller-sized ints.

[jpfairbanks]

type Graph
    vertices::UnitRange{Int}
    edges::Set{Edge}
    fadjlist::Vector{Vector{Int}} # [src]: (dst, dst, dst)
    badjlist::Vector{Vector{Int}} # [dst]: (src, src, src)
end

fadjlist and badjlist need to be sparse representations indexed by T if you want to do that. It is a good idea because then when one goes to distribute these graphs across memory spaces that is easier. The biggest graph processing systems use such techniques. Translation from the big space to a small space will be happening somewhere, either before the data gets into the graph or inside the graph.

[sbromberger]

mmm. Yup. I forgot about fadjlist and badjlist appending. The problem is that performance is really bad with sparse matrices (and Dicts) right now, so this will likely have to wait until the situation improves a bit.

Closing out due to inviability but can continue discussion for future implementation if you'd like. Thanks for the input!