add tests and benchmarks for Data.Graph

[jwaldmann]

There are no Data.Graph tests or benchmarks at https://github.com/haskell/containers/tree/master/containers-tests ?

These would be helpful if we are going to make claims about performance (#648 ) or for the (unlikely) case that the code should get extended/refactored.

[jwaldmann]

I made this https://github.com/jwaldmann/data-graph-test computing SCCs of (pseudo) random sparse graphs (m = c * n where n = #nodes, m = #edges, for c in 1 .. 100, say). Observations:

• For fixed n, SCC cost does indeed seem linear in m.
• For fixed c, SCC cost seems more than linear in n.
• For just building the graph, linearity seems fine.

This also includes a comparison to https://github.com/yav/GraphSCC . Observations:

• GraphSCC.scc is better except when the graph is small and very sparse (c = 1).

stack bench --ba -q
...
scc/n=10^3/m=n*1/containers              time                 449.9 μs  
scc/n=10^3/m=n*1/GraphSCC                time                 612.6 μs  
scc/n=10^3/m=n*10/containers             time                 1.833 ms  
scc/n=10^3/m=n*10/GraphSCC               time                 1.529 ms  
scc/n=10^3/m=n*100/containers            time                 24.27 ms  
scc/n=10^3/m=n*100/GraphSCC              time                 12.08 ms  

scc/n=10^4/m=n*1/containers              time                 7.244 ms  
scc/n=10^4/m=n*1/GraphSCC                time                 11.13 ms  
scc/n=10^4/m=n*10/containers             time                 30.86 ms  
scc/n=10^4/m=n*10/GraphSCC               time                 26.90 ms  
scc/n=10^4/m=n*100/containers            time                 306.6 ms  
scc/n=10^4/m=n*100/GraphSCC              time                 179.5 ms  

scc/n=10^5/m=n*1/containers              time                 119.5 ms  
scc/n=10^5/m=n*1/GraphSCC                time                 130.7 ms  
scc/n=10^5/m=n*10/containers             time                 535.2 ms  
scc/n=10^5/m=n*10/GraphSCC               time                 334.0 ms  
scc/n=10^5/m=n*100/containers            time                 4.584 s   
scc/n=10^5/m=n*100/GraphSCC              time                 2.372 s 

scc/n=10^6/m=n*1/containers              time                 2.416 s   
scc/n=10^6/m=n*1/GraphSCC                time                 1.513 s   
scc/n=10^6/m=n*10/containers             time                 20.82 s   
scc/n=10^6/m=n*10/GraphSCC               time                 5.031 s   
scc/n=10^6/m=n*100/containers            time                 209.2 s   
scc/n=10^6/m=n*100/GraphSCC              time                 40.87 s   

buildG/n=10^1/m=n*1                      time                 2.726 μs  
buildG/n=10^1/m=n*10                     time                 21.42 μs  

buildG/n=10^2/m=n*1                      time                 22.32 μs  
buildG/n=10^2/m=n*10                     time                 234.2 μs  
buildG/n=10^2/m=n*100                    time                 3.275 ms  

buildG/n=10^3/m=n*1                      time                 248.9 μs  
buildG/n=10^3/m=n*10                     time                 3.418 ms  
buildG/n=10^3/m=n*100                    time                 52.77 ms  

buildG/n=10^4/m=n*1                      time                 4.085 ms  
buildG/n=10^4/m=n*10                     time                 56.83 ms  
buildG/n=10^4/m=n*100                    time                 594.5 ms  

buildG/n=10^5/m=n*1                      time                 89.76 ms  
buildG/n=10^5/m=n*10                     time                 895.2 ms  
buildG/n=10^5/m=n*100                    time                 10.62 s   

buildG/n=10^6/m=n*1                      time                 1.877 s   
buildG/n=10^6/m=n*10                     time                 25.09 s   
buildG/n=10^6/m=n*100                    time                 368.2 s   

[meooow25]

Closing since Data.Graph has tests and benchmarks now (#883)
If something is not covered but should be, let me know.