[DISCUSSION] Design of Network

[CarloLucibello]

I think that the easiest and most effective to implement a Network ( a graph also able to store edge and vertex properties), would require a little change in the direction of abstraction in LightGraphs.jl. Its a matter of few lines of code and have the following type structure:

abstract SimpleGraph

"""
Abstract graph type
Requirements: 
  - vertices are numbers in [1,N]
  - edges are pair of vertices
  - ... minimal api... (add/remove vertex/edge etc..)
"""
abstract Graph <: SimpleGraph

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

Then in Networks.jl we could have

"""
Abstract Network type
Requirements: 
  - Graph requirements + additional ones
"""
abstract Network <: Graph

type LightNetwork <: Network
    vertices::UnitRange{Int}
    edges::Set{Edge}
    fadjlist::Vector{Vector{Int}} # [src]: (dst, dst, dst)
    badjlist::Vector{Vector{Int}} # [dst]: (src, src, src)
    ... additional data.....
end

type DynamicNetwork <: Network
    vertices::UnitRange{Int}
    edges::Set{Edge}
    fadjlist::Vector{Vector{Int}} # [src]: (dst, dst, dst)
    badjlist::Vector{Vector{Int}} # [dst]: (src, src, src)
    ... additional data.....
end

And obtain for free all the functionality of LightGraph, without any metaprogramming trick. I wonder what @sbromberger and @jpfairbanks think about this...

[jpfairbanks]

This is a pretty standard way to do it in an OO system. We should also think about embedding the graph into the Network type. So a Network{G} is a thing that wraps a G to provide Metadata functionality while G provides graph functionality.

The metaprogramming necessary is just to make an array of methods you want to operate on the graph part of the network and make a loop that defines them all. I do it GraphMatrics to make all of the Laplacian and Adjacency types behave like matrices. It's not hard or confusing.

[CarloLucibello]

The is a relation sounds semantically more correct to me, and it allows for less maintenance burden, like adding a function to Networks every time a function is added to LG. On the other hand the has a elation provides more encapsulation, but in this case I fail to see the advantages of it, so I lean towards inheritance

[sbromberger]

One thing that I'd love to see in a package like this is the abstraction of the backend datastore. For example, I typically use redis to store my metadata. This allows me to separate the metadata from the actual graph objects but gives me fairly quick, efficient access to it.

[CarloLucibello]

can you show me an example of redis usage to store /edge/vertex properties?

[sbromberger]

Not one I can share publicly, but redis is a key-value store, so we have edges and vertices stored with various values in the datastore, and call out to get the values when we need them.

[jpfairbanks]

Are you using Redis.jl? It appears to have an api that is amenable to wrapping with getindex on the connections. You could define getindex and set index for Redis.connection right? The point being that using the dict interface and parameterizing over the actually storage type woukd make a lot of sense.

[sbromberger]

I'm using Redis.jl. It's a nice API and I've done some work on it.

[jpfairbanks]

@sbromberger could you share a simple version of your redis client? We should only need enough to understand the ideas not necessarily all the details of your application.

[sbromberger]

Probably not, though the idea is simple: Both vertices and edges are hashed using hash() to produce the redis key. For vertices, the data stored in redis is another integer. For edges, it's a single character (represented in redis by a string).

[jpfairbanks]

Hey @CarloLucibello I added conversion and promotion rules so that you can transparently use Networks as Graphs. I think this a general method for using embedding over inheritance.

We would need to add generic versions of every function that should work on networks. I think that could be done with some metaprogramming f(g::Graph,args)->f(g,args)=f(convert(Graph,g),args).

[CarloLucibello]

Definitely I would want to be able to use with a net every function exported by LightGraphs that doesn't modify the graph.

And I would also exclude functions returning a Graph for the time being.

Maybe we can imagine something on the line of

for f in names(LightGraphs)
    if isa(f, Function)
     .... f(g,args)=f(convert(Graph,g),args) ....
   end
end