Scaffolding discussion

[sbromberger]

Ref #526

Option 1:

abstract AbstractGraph
abstract AbstractDiGraph

type Graph{V,E} <: AbstractGraph
type DiGraph{V,E} <: AbstractDiGraph

...

We will need index(V) in order to store adjacencies efficiently, and V should have an efficient reverse function. (This argues for a Dict-like structure.)

[juliohm]

One of the lessons I learned from the Julia type system is that shallow hierarchies are preferred over deep hierarchies both from the designer perspective as well as from the user perspective. It is very hard to contribute to code with deep hierarchies.

What other types do you see fitting in this proposal besides Graph and Digraph?

[sbromberger]

Well, what I was thinking is something like

typealias Int64Graph Graph{Int64, Pair{Int64, Int64}}
typealias Int64DiGraph DiGraph{Int64, Pair{Int64, Int64}}

to mimic what we have now for Graph.

This allows us to do, for example,

typealias DictGraph Graph{Pair{Int64, Dict{String, Any}}, Pair{Int64, Int64}

to specify a graph that has metadata for vertices, and

type WeightedEdge{V<:Integer, T<:Number}
  src::V
  dst::V
  weight::T
end

typealias WeightedGraph{V, ET} Graph{V, WeightedEdge{V, ET}}

etc.

[juliohm]

A question from someone that is still getting used to the Julia type system as it evolves... Why in the option you showed there are two abstract types instead of one? Maybe my question is more about what motivates the design with both AbstractGraph and AbstractDiGraph, couldn't we abstract a single base type like in the snippet below:

abstract AbstractGraph
type Graph <: AbstractGraph end
type DiGraph <: AbstractGraph end

[sbromberger]

Yes, of course - but I thought it might be interesting to explore having separate types. This solves a bunch of issues (#401, is_directed becomes simpler and "abstractable", etc). We don't have to do this; it's just a suggestion. :)

[juliohm]

I need to use the type system more before I can counter argue, but my impression is that we could have the separation you mentioned with a single abstract base and dispatch on the concrete types as usual.

I am looking forward to see how the changes will unfold 😊

[sbromberger]

Yes, you can, except it would be a bit harder to have unique edge types for Graphs and DiGraphs without having different types for the graph structures themselves. There's more than one way to do this, and I'm not particularly worried at this point about getting it perfect.

[sbromberger]

Thinking about this some more, I don't think we want to go away from the UnitRange Vertex indices. This means that

abstract AbstractGraph{VI<:Integer}
abstract AbstractDiGraph{VI<:Integer}

type Graph{VI ,VD,ED} <: AbstractGraph{VI}
  vind::UnitRange{VI}
  vertices::VD  # must be indexable via vind
  edges::ED
  fadjlist::Vector{Vector{VI}}
end

This looks complicated, and it is, but it would be easier if we could get rid of the VI parameter for the Graph concrete type by somehow inferring it from the supertype. Since there are no built-in traits, we might consider requiring them via SimpleTraits for vertices to uphold some notion of indexability.

Edited: we might not even need to parameterize AbstractGraph / AbstractDiGraph if we just say "Our package requires vertex indices as some integer type".

[jpfairbanks]

What about the following?

abstract AbstractGraph

type Graph{VI ,VD,ED} <: AbstractGraph{VI}
  vind::UnitRange{VI}
  vertices::VD  # must be indexable via vind
  edges::ED
  fadjlist::Vector{Vector{VI}}
end

vindtype(g::Graph{VI,VD,ED) = VI
vsettype(g::Graph{VI,VD,ED) = VD
edgetype(g::Graph{VI,VD,ED) = ED

Then you could get the types from any implementation, but don't need to specify it with parameterized types at the AbstractGraph level.

[juliohm]

We have to be careful with such constructs in Julia, at the moment they are not quite practical like C++ metaprogramming, I had issues trying to inspect the type at the time of usage and it seems a solution is still not implemented in the language:

https://discourse.julialang.org/t/recovering-parameter-type-from-parameter-list/1343/5?u=juliohm

[juliohm]

One thing that we can do without any impact on the code is to replace every occurrence of SimpleGraph by AbstractGraph, make it an abstract type as suggested, and see if the tests pass. I can implement the replacement with regular expressions and submit a PR if you want.

[jpfairbanks]

Yeah that would be good.

[sbromberger]

@jpfairbanks

What about the following?

That won't compile as you haven't parameterized AbstractGraph yet you're referencing AbstractGraph{VI}.

[sbromberger]

I've been playing around with this most of the day. Here's what I've found makes the most sense:

abstract AbstractGraph    # [1]

abstract AbstractSimpleGraph <: AbstractGraph   # [2]

type SimpleGraph{...} <: AbstractSimpleGraph
type SimpleDiGraph{...} <: AbstractSimpleGraph    # [3]

typealias Graph SimpleGraph
typealias DiGraph SimpleDiGraph              # [4]

Rationale / explanation

1. This is the most generic abstract type. Straightforward.
2. This is an abstract type that indicates a general set of abstractions. Think DictGraph, etc.
3. These break out the abstract type into concrete Graph and Digraph.
4. Just for now, so we don't break existing code.

[jpfairbanks]

Does AbstractSimpleGraph mean anything that represents a graph with no multiedges?
Otherwise why "Simple"?

[sbromberger]

Does AbstractSimpleGraph mean anything that represents a graph with no multiedges?

That, and (possibly?) with a sparse adjacency list, and no vertex or edge metadata.

[jpfairbanks]

We should write down the names we will use for these types of graphs. Maybe these terms?

• simple: no multiedges, no weights, or metadata
• multi: with multiedges (unsupported)
• weighted: weights <:Number
• meta: vertex or edge metadata

All graphs are accessed primarily through neighbors which provided an iterator over the set of neighbors of each vertex.

[sbromberger]

All graphs are accessed primarily through neighbors which provided an iterator over the set of neighbors of each vertex.

or edges, right?

[jpfairbanks]

Yeah I was going to add that and then remembered that you can always build edges out of vertices and neighbors. We should provide that implementation for AbstractGraph

[sbromberger]

Yeah I was going to add that and then remembered that you can always build edges out of vertices and neighbors

We're doing that with Edgeiter now, right? That is, we're using the adjacency lists to generate the iterator.

[sbromberger]

See #541 please.

[sbromberger]

I'm closing this out due to the advanced progress of #541.