Replacing Algebra.Graph by Maybe (Algebra.Graph.NonEmpty)

[snowleopard]

Replacing Algebra.Graph by Maybe (Algebra.Graph.NonEmpty)

[snowleopard]

@nobrakal Many thanks for the experiment!

I have been wondering recently: do we even need graphs that can be empty? Presumably, non-empty graphs cover 99% of use-cases and are generally safer not only in terms of internal representation, but for the users too.

The creation takes longer from a list of edges, or anything, because we pattern match to detect the empty graph.

I don't understand this: it's just a single comparison, right? It shouldn't even be measurable.

[nobrakal]

Yeah indeed ^^.

Perhaps, into a separate Travis instance

I totally agree, I will send a PR

[nobrakal]

I have been wondering recently: do we even need graphs that can be empty?

With the actual Empty constructor, I don't think so. But providing an encapsulated version using Maybe NonEmptyGraph:

• allow to have "regular" functions (edges take a list, and not an NonEmpty one)
• is coherent with functions from Algebra.Graph.NonEmpty (like induce1)
• Will provide all the handy functions dealing with empty graphs, so a user who must deals with them have not to rewrite them, even if they are really dumb (like `isEmpty (G g) = isNothing g).
• introduce the user to NonEmptyGraph, it may even worth a adding a mention saying that NonEmptyGraph is faster in all cases, and if they are dealing with nonEmptyOne

But I think we definitely need to focus more in NonEmpty :)

I don't understand this: it's just a single comparison, right? It shouldn't even be measurable.

I don't understand yet too... It is a huge drop for a single comparison !

[snowleopard]

I don't understand yet too... It is a huge drop for a single comparison !

Perhaps, it prevents some important optimisation? Could you investigate by looking at generated Core?

[nobrakal]

Perhaps, it prevents some important optimisation?

It was the case for edges. Habitually, there is a merge between a foldr and map (this is what we used to speedup overlays), and after some search, I found that it didn't happened here.

I fixed it by hand by writing:

edges :: [(a, a)] -> Graph a
edges [] = Empty
edges (x:xs) = G $ Just $ foldr (N.Overlay . uncurry N.edge) (uncurry N.edge x) xs

It dropped to ratio to 1.09, so it is good. I don't know if we can do better

[snowleopard]

@nobrakal Why not use edges1 in the second case? Then you don't need to reimplement it.

[nobrakal]

In fact I need to do the change in edges1 and use it from Algebra.Graph.edges.

edges1 (x :| xs) = foldr (Overlay . uncurry edge) (uncurry edge x) xs

The problem is that the combination of foldr1 and fmap (uncurry edge) does not behave very well ^^

[nobrakal]

The last benchs:

isEmpty: 0.63 (good) 
vertexList: 1.06 (OK)
VertexCount: 1.07 (OK) 
hasVertex: 5.13 (bad) 
edgeCount: 1.09 (OK) 
edgeList: 0.76 (good) 
hasEdge: 0.40 (good) 
hasSelfLoop: 1.17 (bad) 
addEdge: 1.08 (OK) 
addVertex: 1.07 (OK) 
removeVertex: 1.15 (bad) 
equality: 1.06 (OK)
removeEdge: 1.04 (OK) 
transpose: 1.01 (OK) 
creation: 0.97 (OK)

So everything is ok, note that the rough number for hasVertex is a false positive: it search for the vertex 0 which is at the end of the graph in the new representation, and at the begining for the actual one, so the times are not the same (since || looks first for the left side)

[snowleopard]

note that the rough number for hasVertex is a false positive

Hmm, this makes me think that the benchmarking suite is too fragile: it shouldn't measure performance by looking up only a single vertex. It should average time for several different vertices, otherwise some libraries/implementations will get an unfair advantage by chance.

[nobrakal]

Sorry, I wasn't clear. I actually test 4/5 vertices (for a graph with n vertices I test the search of vertex 0, n/3, 2*n/3, n+1).
But the difference is actually very huge for the first one (50 ns for the actual Alga but 3 micro seconds for the new one (3 micro seconds it the time taken by both for searching a vertex at the end of the graph )).

It might worth it to add some vertices, but I don't think it will really change the results ^^

[snowleopard]

@nobrakal Ah, I see, thanks for clarifying... Yes, that's what one gets for having O(n) complexity :) There is really a huge swing between best and worst cases.

[snowleopard]

Since we are now starting to look more carefully at non-empty graphs, I think it may be worth adding them into the regression suite... Perhaps, into a separate Travis instance, so we don't hit the time limit?

[snowleopard]

I just realised that NonEmpty.Graph (Maybe a) is isomorphic to Graph a:

• NonEmpty.Vertex (Just a) ~ Vertex a
• NonEmpty.Vertex Nothing ~ Empty

Not sure this observartion is useful, but I thought I better record it here.

I still think Maybe (NonEmpty.Graph a) is a better representation for possibly empty graphs.