Graphs is too general to be useful

[mlubin]

There have been some grumbles before about this in the abstract sense, but here's a concrete technical example of how the overparameterization of the Graph object limits its usability:

With Julia 0.4:

julia> g = simple_graph(2)
Directed Graph (2 vertices, 0 edges)

julia> add_edge!(g,1,2)
edge [1]: 1 -- 2

julia> @code_warntype Pair(g,2)
Variables:
  first::Graphs.GenericGraph{Int64,Graphs.Edge{Int64},UnitRange{Int64},Array{Graphs.Edge{Int64},1},Array{Array{Graphs.Edge{Int64},1},1}}
  second::Int64

Body:
  begin 
      return ((top(apply_type))(Pair,A,B)::Type{_<:Pair{A,B}})(first::Graphs.GenericGraph{Int64,Graphs.Edge{Int64},UnitRange{Int64},Array{Graphs.Edge{Int64},1},Array{Array{Graphs.Edge{Int64},1},1}},second::Int64)::Pair{A,B}
  end::Pair{A,B}

Note that the return type of Pair can't be inferred. I'm guessing this is because of MAX_TYPE_DEPTH recently discussed here.

In general it seems like any type which is parameterized by a type of a graph suffers from this. This affects TargetIterator, SourceIterator, out_neighbors, in_neighbors, and maybe more.

@lindahua @sbromberger @JeffBezanson @IainNZ

[mlubin]

I bumped up MAX_TYPE_DEPTH in my local build and the timings on a particular graph coloring instance in ReverseDiffSparse went from

elapsed time: 18.321259555 seconds (4459 MB allocated, 3.41% gc time in 204 pauses with 1 full sweep)

to

elapsed time: 4.350620804 seconds (1383 MB allocated, 4.43% gc time in 63 pauses with 1 full sweep)

[JeffBezanson]

What did you set MAX_TYPE_DEPTH to? I'd definitely consider increasing the default.

[mlubin]

@JeffBezanson, I just changed it from 4 to 5.

[JeffBezanson]

That seems pretty reasonable.

[mlubin]

This issue also affects arrays of Graph objects, i.e.,

arr = SimpleGraph[]

cannot be type inferred.