Add directed-graph? and undirected-graph?

[a11ce]

Hi, I would like to be able to tell if a graph is directed or undirected. Would it be possible to add this to the interface and implement it by:

• storing a boolean in the graph struct, initialized based on which constructor is used
• having add-directed-edge! set it to true

I will add it but wanted to make sure that this implementation would be acceptable.

[stchang]

Yes this is a good idea.

We might need to think about a few corner cases though. Like what should happen if someone calls add-edge after add-directed-edge`?

[a11ce]

Currently, add-edge! behaves like add-edges-in-both-directions! when used on a directed graph, right?

I think ideally it would instead only add one edge (or error?), but that would be a breaking change. The best way to follow the current behavior would be to have add-edge! ignore the flag.

I'm honestly having trouble thinking of use cases which require a graph to be changed from undirected to directed or vice versa. (In my case, the user gives a graph to my library but I don't need to modify it.)

[stchang]

Actually, I forgot that the internal struct is not exported, only constructors that already distinguish directed/undirected (eg, mk-unweighted-graph/undirected and mk-unweighted-graph/directed) so this should be easy to add without breaking.

Maybe create two substructs (one for directed one for undirected) that have the existing struct as a super struct?

[a11ce]

If they are different substructs, what happens when you call add-directed-edge! on an undirected graph? Does it create and copy its data to a new directed graph?

Also, having 4 total substructs (weighted/unweighted, directed/undirected) might be messy.

[stchang]

what happens when you call add-directed-edge! on an undirected graph

I think the right thing to do is to to error. But that might make things even more complicated since I think we would have to split the methods to the two structs as well. I think that's the cleaner design though. 4 structs might be slightly more verbose but they represent 4 distinct variations so it makes sense. I agree it would be easier to add a directed? flag but I dont like flags in general.

What do you think?

[a11ce]

In that case, it might make sense to combine add-edge! and add-directed-edge! into just add-edge!.

[stchang]

oh that's a good point. That's would definitely be a breaking change though. Let me think about it some more

[a11ce]

Also to think about, 4 structs would mean directed-graph? and weighted-graph? (etc.) would need to be defined explicitly instead of as structure predicates.

Would you be okay with a flag if it was immutable (such that calling add-directed-edge! on an undirected graph errors instead of switching the flag (or add-directed-edge! is removed entirely as above))?