Directed graphs?

[gdalle]

Hi, and congrats on the registration! I love the design so far.
Is there a way to implement directed graphs at the moment? From what I can tell, an edge or hyper-edge has no notion of where it comes from or where it goes to. Perhaps it would be feasible by switching to a "directed bipartite graph" between vertices and edges, with utilities like link_to!(g, e, v) and link_from!(g, u, e)?

[mofeing]

Thanks @gdalle! I was looking forward your opinion.

Is there a way to implement directed graphs at the moment?

From what I can tell, an edge or hyper-edge has no notion of where it comes from or where it goes to.

I'm not versed on graph theory literature, but AFAIK, directedness on hyper-edges is ill-defined. Should a hyperedge be a 2-set of source and destination vertices? Should we force to always have a single destination vertex? Should it be a path (so an ordering, weak or strong, of the vertices connected by the hyperedge)?

Experience has taught me that in this cases is better not to abstract (because we don't know how) and leave this to implementors. In this sense, directedness as of right now is an implementation detail. Actually, I think that SimpleNetwork could be converted into a directed SimpleDiNetwork by just changing these lines:

Networks.jl/src/Components/SimpleNetwork.jl

Lines 60 to 64 in bc553a3

	if !hasedge(g, e)
	push!(g.fadjlist[a], b)
	push!(g.fadjlist[b], a)
	g.ne += 1
	end

to

if !hasedge(g, e) 
     push!(g.fadjlist[a], b)
     g.ne += 1 
 end 

(Probably it could benefit from several more things, like a SimpleDiEdge type, but it should make the work)

Perhaps it would be feasible by switching to a "directed bipartite graph" between vertices and edges, with utilities like link_to!(g, e, v) and link_from!(g, u, e)?

Check out that for adjacent matrix-based implementations like the SimpleDiNetwork above, you don't need to use link! / unlink!, and that "linking" is implicitly handled by the addedge! / rmedge! methods. For a implementation based on incidence matrices, like also mentioned above, directedness can be ill-defined for hyperedges. I've been unsuccessful trying to completely abstract it for these cases, and I think it should be up to the implementors.

Before adding something like a link_to! / link_from!, which would only be used by directed hypergraphs whose edges can vary their degree dynamically, I would like to see some specific cases where it could be benefitial.

We could maybe add a Directedness trait, to indicate whether a graph type is Directed, Undirected, Hybrid or a custom trait by some user (e.g. to implement different directedness definitions for hyper-edges, but that's very hypothetical) if we find a case where dispatching on the trait is benefitial. link! could maybe be such a case but not sure how to fit it.