Make objects behave like graphs without plugging them into type hierarchy

[kalmarek]

I'm writing this at a request of @gdalle to pool random design ideas ;)

---

Aim

I'd be great if we could make other objects behave like graphs, cheaply without plugging into type hierarchy.
This idea is inspired by the design of Tables.jl which is exemplified by this discourse post.

TLDR: It's very easy to make things behave like row/column based Tables without plugging into any type system.

Usecase

I have my separate type-system where I implement graph-like structures, but focusing on other aspects (deterministic? complete/regular? etc.) It would be very convenient to define just a bunch of methods (like iterators ;)) to make my structures behave like graphs and work with graphs algorithms.

Example (?)

I have a dfsa (deterministic finite state automaton = directed, labeled graph); I'd like to find shortest loop in it. Run a backtrack search on it.

here is (it's just an example, not a proposal!) a rough way one could think in terms of code about this:

const GB = GraphsBase 
GB.isgraph(x::Any) = fale # the default
GB.Directness(::Type{...}) # GB.Directed()/GB.Undirected()/...
GB.Simplicity(::Type{...}) # GB.IsSimpleGraph()/GB.IsMultiGraph()/GB.IsHypergraph()/...
GB.Eagerness(::Type{...}) # GB.Eager()/GB.Lazy() # if vertices edges are given only locally
GB.vertex_type(::Type{...})
GB.edge_type(::Type{...})
.... # and (many?) more

and (based on those traits) a separate sets of interface functions

GB.vertices(graph) = GB.vertices(graph) # an iterator over vertices
GB.neighbours(graph, vertex) # required if GB.Undirected()
GB.out_neighbours(graph, vertex) # which is different from
GB.in_neighbours(graph, vertex) # these two are only required for GB.Directed()

GB.hasedge(graph, vertex, edge) # if graph is GB.Lazy(), otherwise
GB.hasedge(graph, edge)
... # and so on, these are just examples, not a fixed proposal

This way graph can stay un-typed and it'd be easy to "turn anything into a graph"™, including e.g. BitMatrix (hopefully without committing type piracy).

Cons:

• potentially hard/complex "dispatch" path (but JuMP is an example that even more complex designs are possible ;);
• explosion of different methods (signatures);
• no clear type structure that we all love...

[CameronBieganek]

I sympathize with the desire to define everything in terms of traits instead of abstract types. (What we really need is multiple inheritance, but that might never happen.) However, the Tables.jl approach has some downsides. There are types for which Tables.istable returns true even though there are instances of those types that are not tables. Here is an example with a vector of named tuples that is not a table, because the length of columns a and b are different:

julia> t = [(a = 1, b = 3), (a = 2, )]
2-element Vector{NamedTuple}:
 (a = 1, b = 3)
 (a = 2,)

julia> Tables.istable(t)
true

julia> rows = Tables.rows(t)
2-element Vector{NamedTuple}:
 (a = 1, b = 3)
 (a = 2,)

julia> for (i, row) in enumerate(rows)
           println("Row $i: b=", Tables.getcolumn(row, :b))
       end
Row 1: b=3
ERROR: type NamedTuple has no field b
Stacktrace:
 [1] getproperty
   @ .\Base.jl:37 [inlined]
 [2] getcolumn(x::NamedTuple{(:a,), Tuple{Int64}}, nm::Symbol)
   @ Tables C:\Users\U216145\.julia\packages\Tables\u1X7W\src\Tables.jl:102
 [3] top-level scope
   @ .\REPL[30]:2

The same problem exists for named tuples of vectors:

julia> t = (a=[1, 2], b=[3])
(a = [1, 2], b = [3])

julia> Tables.istable(t)
true

julia> rows = Tables.rows(t)
Tables.RowIterator{NamedTuple{(:a, :b), Tuple{Vector{Int64}, Vector{Int64}}}}((a = [1, 2], b = [3]), 2)

julia> for (i, row) in enumerate(rows)
           println("Row $i: b=", Tables.getcolumn(row, :b))
       end
Row 1: b=3
ERROR: BoundsError: attempt to access 1-element Vector{Int64} at index [2]
Stacktrace:
 [1] getindex
   @ .\essentials.jl:13 [inlined]
 [2] getcolumn(c::Tables.ColumnsRow{NamedTuple{(:a, :b), Tuple{Vector{Int64}, Vector{Int64}}}}, nm::Symbol)
   @ Tables C:\Users\U216145\.julia\packages\Tables\u1X7W\src\fallbacks.jl:26
 [3] top-level scope
   @ .\REPL[34]:2

It's not really proper to say that Vector{NamedTuple} and NamedTuple{(:a, :b), Tuple{Vector{Int64}, Vector{Int64}}} are table types, because only some instances of those types can be treated as tables. For a type to be a table type, then every instance of that type should be a proper table.

Perhaps that's not an argument against the trait approach. Maybe it's just an argument that Tables.jl should be more strict in its definition of the table interface. Although I suppose the benefit of the loose interface is that many objects might work as a table, though you never really know until you try to use the object as a table...

[kalmarek]

For a type to be a table type, then every instance of that type should be a proper table.

Well, this is not enforcable in julia, as the users can "lie" in one place to get away with some functionality in other; e.g. here you constructed an abstractly typed Vector (e.g. since it's a useful container for some purposes of yours). Maybe Tables should tell that every concretely typed Vector{<:NamedTuple} is a table. Or maybe not.

My argument for this is more like this: If library code throws some errors with my arguments I might be able to fix it by either modifying my arguments (e.g. here: by concretely typing them) or defining additional methods. If the code rejects my arguments on type level I will not be even able to see if it runs (or investigate what functionality fails), without much effort.

I don't see interfaces as assumptions in mathematical theorems ;)
I see them more as a rather specific guidance of what and how should I implement to get things working.

[CameronBieganek]

Philosophically, I wish we had abstract multiple inheritance so that we could label types that implement the interface with AbstractGraph. But we don't have multiple inheritance, so I agree that the AbstractGraph type should not be in the interface (or defined at all).

[nsajko]

Requiring user-defined types to subtype an interface-defined abstract type is a huge PITA. IMO any new interface should do away with AbstractGraph and the rest of the type hierarchy.

[cpfiffer]

Oh, interesting 🤔. What would you propose?

…

On Sun, Aug 11, 2024, at 4:49 AM, Neven Sajko wrote: Requiring user-defined types to subtype an interface-defined abstract type is a huge PITA. IMO any new interface should do away with `AbstractGraph` and the rest of the type hierarchy. — Reply to this email directly, view it on GitHub <#26 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AADHITRST3XA3DJ6YTLYGBTZQ5FTZAVCNFSM6AAAAABMKV5DC2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEOBSG4ZTCOBRGA>. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[kalmarek]

@cpfiffer What Tables.jl did, or what I tried to roughly sketch in my first post (though this I made the sketch purposely vague, not give any specific sticking points).

And contrary to the belief of Cameron expressed above, I don't think interface should be any sort of "mathematical guarantee": all types implementing those methods will be correctly interpreted as XXX. This is neither achievable (without constraining the interface too much), nor useful either from the developer or user perspective.

Just because some Vectors/Tuple will give you errors when treated table-like, it's not useful to exclude all of them. I see here that rather the data stored in Vector is erring, not the interface.