juliagraphs / graphsbase.jl Goto Github PK

#13 (comment)

It seems like it would be convenient to have a package that defines only the AbstractGraph interface without providing any implementations, similar to how Tables.jl and DataAPI.jl work. That way packages that implement new graph types only need to depend on the interface package.

On the other hand, does the new package extensions feature reduce the need for separate interface packages? I haven't played around with package extensions yet, so I don't know the answer to that question.

In addition to the interface, this package should probably contain basic implementations for the most common types of graphs.

Here's a possible list:

For each one, we will provide both the simple version (no multi-edges, possible self-loops) and the generic version.

How to handle them?

Related:

• JuliaGraphs/Graphs.jl#92
• JuliaGraphs/Graphs.jl#281

Is there any intention to support hypergraphs? The main deadlock to integrate hypergraphs in Graphs is the assumption that edges point to 2 vertices. Currently is weird to implement a "undirected" HyperEdge type: dst and src have no point there (even in an undirected graph dst and src look weird) because there will be more than 2 vertices.

My proposal is the following:

1. See simple edges as a special case of hyperedges whose cardinality is 2.
2. Stop using dst and src for undirected edges $\rightarrow$ Use vertices(edge) where possible instead.
3. For graph algorithms that need a non-hyper graph view, a hyperedge can be seen as the powerset of cardinality 2 of the connecting vertices (i.e. all vertices in an hyperedge are at distance 1).

If we relax this assumption, open edges could also be supported and implemented as cardinality 1 hyperedges.

It would be great to provide minimal / adversarial implementations of the new interface for our own testing purposes.

Related:

• JuliaGraphs/Graphs.jl#224
• https://github.com/cmcaine/EvilArrays.jl

What's the idea with this package ?
Will it mean that most of the fundamental code in Graphs.jl will be transferred here ? If yes, what remains for Graphs.jl and how is this decided ?

Opening this to keep track of issues related to multiple edges or layers

Related

• JuliaGraphs/Graphs.jl#165
• JuliaGraphs/Graphs.jl#39

On Discourse, the question arose of how to combine generic vertices with efficient storage.

@CameronBieganek suggested interfaces methods to translate between vertices and integers. This is similar to what many package developers have done for graphs with metadata.
@mtfishman says we should look at what array packages like DimensionalData.jl and AxisKeys.jl have done, by similarity between a graph and a matrix.

Do they still make sense?
Should weights be defined even for edges that don't exist?

Which ones?

Should it be in the vertex / edge object itself?
What is the right syntax to access it? Can it be linked with the edge weight?

Once users implement an AbstractGraph, they need an easy way to make sure that all of the methods are correctly defined. For instance a test suite that we provide.

And we need a way to make sure that said test suite is correct: https://discourse.julialang.org/t/metatesting-jl-who-tests-the-test-suites/99273

Related: JuliaGraphs/Graphs.jl#253

When we define the new API, there will be abstract types with some methods that must be implemented. In base Julia, I see two main ways of specifying this (as in, defining the function name, possibly with a generic docstring):

julia> function myfunc1 end
myfunc1 (generic function with 0 methods)

julia> myfunc2(args...) = error("Not implemented")
myfunc2 (generic function with 1 method)

julia> myfunc1(1)
ERROR: MethodError: no method matching myfunc1(::Int64)
Stacktrace:
 [1] top-level scope
   @ REPL[4]:1

julia> myfunc2(1)
ERROR: Not implemented
Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:35
 [2] myfunc2(args::Int64)
   @ Main ./REPL[2]:1
 [3] top-level scope
   @ REPL[5]:1

I believe a methodless function is better than a single method throwing an error by default. The end result is nearly the same in terms of user experience, but I find the first error clearer because it directly tells you what to implement. @simonschoelly what do you think?

Of course we could also consider more advanced options like Interfaces.jl or InterfaceSpecs.jl but maybe it's a bit overkill?

See also: JuliaGraphs/Graphs.jl#262

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...

In the API proposal JuliaGraphs/Graphs.jl#146, some traits are useful for dispatch, but I feel like some are only useful to throw exceptions if something is not permitted (like is_mutable). Do we really need traits for that?

I am just thinking out loud here..
Quite commonly I need to deal with subgraphs (i.e. induced_subgraph) or merged graphs (i.e. merge_vertices).
It's quite handy to have the bank ! variations (i.e. merge_vertices vs merge_vertices!), but they are not consistent across Graphs.jl. E.g. induced_subgraph doesn't have a corresponding bank version.

Sometimes I want to operate on a resulted converted graph, without losing the original but still influencing it.
It's like a combination of a bank ! and without.
This basically means having a view of the original graph.
The whole idea is very similar to the DataFrames.jl view https://dataframes.juliadata.org/stable/man/basics/#Views

That might be more relevant for Metagraphs, since graphs will carry data that can be shallow- or deep-copied.
A view, e.g., should implement shallow copying (if not by reference)

Also it might be useful for different indexing, which might enable us to get rid of the vmap property that some functions return.

I know it's a lot; I just wanted to share since now a lot of discussions are taking place for a Graphs.jl 2.0
I am still not 100% persuaded on this, but it looks to me like there could be some value.
What do you think and could you see different use cases ?

The edge types in Graphs.jl are directed but used for undirected graphs too, in sometimes incoherent ways. Should there be an undirected edge acting like a set? And if so, should the syntax change, eg. other_endpoint(e,u)?

I think it's worth considering having one Graph type that can optionally include weights and metadata for an undirected graph, rather than having separate WeightedGraph and MetaGraph types. The Graph constructor could have various optional type parameters, so you could create empty graphs like this:

# Create a graph with `Any` vertex type, Float64 edge weights,
# and no metadata.
Graph()

# Char graph with Float64 edge weights:
Graph{Char}()

# Char graph with Int weights:
Graph{Char, Int}()  

# Char graph with Float64 edge weights and
# vertex data of type MyVertexData:
Graph{Char, Float64, MyVertexData}()

# Char graph with Float64 edge weights,
# vertex data of type MyVertexData,
# and edge data of type MyEdgeData:
Graph{Char, Float64, MyVertexData, MyEdgeData}()

# Char graph with Float64 edge weights,
# no vertex data, and edge data of type MyEdgeData:
Graph{Char, Float64, Nothing, MyEdgeData}()

Nothing would be an option for the metadata type parameters, but not for the vertex type and weight type. (Default weight type would probably be Float64.)

Sometimes seems necessary?

Related:

• JuliaGraphs/Graphs.jl#282
• JuliaGraphs/Graphs.jl#297

Once this package gets off the ground, it would be nice to define a typical workflow involving the most common graph types. This would have benefits beyond mere testing:

• allow precompilation with PrecompileTools.jl
• allow runtime dispatch analysis with JET.jl (see this comment)

Splitting out GraphsBase.jl means deciding which functions

1. Have to be overridden by users (the "interface")
2. Rely on the interface while remaining reasonably basic (the "core")
3. Rely on the interface and core while adding more sophisticated functionality (the "algorithms")

The interface and core will go in GraphsBase.jl, the algorithms will remain in Graphs.jl.