Graph functional interface

[bolt12]

So I have been looking for Graph APIs and the networkx for python is very rich and powerful. It has a lot of things but I just want to start with the ones that are simpler/useful.

In the link I provided a lot of them are already implemented so I thought that would be nice to have the following:

• degree :: Graph a -> a -> Int - Returns the degree of a certain vertex
• degreehistogram :: Graph a -> [(a, Float)] - Returns de list of the frequency of each degree value.
• density :: Graph a -> Float - Returns the density of the graph
• reverse :: Graph a -> Graph a - Returns the graph with the edges reverted
• selfLoops :: Graph a -> Int - Returns the number of selfLoops in the graph

I want to discuss some of the types of these functions, if it makes sense to add these kind of functions and how to integrate this in alga. I also am thinking of doing isConnected :: Graph -> Bool and implement graph generation functions like Erdos Renyi/Barabasi-Albert.

should these functions be integrated in Graph API ?

[snowleopard]

Thanks! I think we could add some of these functions as methods or as functions to the ToGraph module.

degree :: Graph a -> a -> Int - Returns the degree of a certain vertex

This one is just one function call away: just run Set.size on preSet/postSet or neighbours.

degreehistogram :: Graph a -> [(a, Float)] - Returns de list of the frequency of each degree value.

This one feels too specialised to be included into the API. However, if there are many such graph statistics functions we could in principle put them into a separate module.

density :: Graph a -> Float - Returns the density of the graph

What is graph density? Again, this feels too specialised to me.

reverse :: Graph a -> Graph a - Returns the graph with the edges reverted

We already have this function, it's called transpose.

selfLoops :: Graph a -> Int - Returns the number of selfLoops in the graph

This sounds too specialised as well... Perhaps, it could at least be generalised to accept a predicate on edges, e.g. edgeCountIf :: (a -> a -> Bool) -> Graph a -> Int so that selfLoops = edgeCountIf (==) and edgeCount = edgeCountIf (\_ _ -> True).

isConnected :: Graph -> Bool

This one is definitely very common, and I'd love to have it in the API.

graph generation functions like Erdos Renyi/Barabasi-Albert.

Could you give examples? Are you talking about generating random graphs with desired statistical properties? If yes, I guess this could go into a separate statistics module (or even a separate package!).

[bolt12]

Okay, I was looking for functions that would make sense to extend the graph API and now that you replied I agree with them feeling too specialized. With this being said, I think it's more interesting for me to focus on the random graph generation and see where I can get.

I'll start by adding the isConnected function since it will be needed first.

[Synthetica9]

Speaking about Networkx: I think we should also implement the "Classic" graph generators.

[snowleopard]

@Synthetica9 We already have some of the listed combinators, but I agree that it would be nice to have some others from this list too.

As always, it is a matter of finding the right balance between the number of features in a library and the ease of navigating the library by a newcomer. To avoid overwhelming people, we might want to move some more sophisticated combinators in a separate module.

[bolt12]

@snowleopard Since there is already a PR on the implementation of isConnected and some of the ideas on the random graph generation require this function I think I'll put the idea on standby for now. I'll try and look at this PR 83