collection of suggestions from reddit and own ones

[matu3ba]

Reddit comments

1. testing.allocator for tests instead of page_allocator for finding leaks etc
2. zig fmt all files
3. let user pass the allocator type and dont use page_allocator always
4. https://ziglang.org/documentation/master/#Style-Guide for functions (ie camelCase unless returning type)

Personal comments

1. Why do you need the weight type? Weights can be attached via the "datagraph".
2. In graphdata and graph you use AddNode, but typically the user writes his own wrapper for the data manipulation and you only provide a way to "comptime derive the interface". For now as "simple start, lol" to show what the user might want this works.
3. RemoveNodeUndirected and RemoveNodeDirected. It may look nice, but this may break user experience ie when people want to have a broken graph to connect it themself for a special method etc. KISS and YAGNI until stuff is polished or move it to a concrete example instantiation of the graph.
4. Make comments over every method.
5. Document the choice for orderedRemove
6. Document the choice how the user should handle the case of between two vertices are only 0 or 1 edges (common graph restriction).

Sorry for the numerous points. Graph stuff is hard.

[sournav]

I agree with the reddit comments. I'm going through fixing some memory leaks I found using testing.allocator right now. I'll also look at the style guide soon. As far as the personal comments I agree with most of them, but have some clarifications.

1. I wanted the "graph" struct to be what algorithms use. There are several algorithms that make use of weights, such as shortest path algorithms, etc. The DataGraph struct allows any data type to be put on nodes and edges. If you had an edge with an edge data struct that is complex (say a struct of various integer and string values describing the edge), then how would an algorithm written for graphs know which struct value to use as weight? To avoid this problem I made weights mandatory. Of course an unweighted graph could just be represented as a weighted graph with edge weights all set to 1. As far as I'm aware there isn't a way to input default params in a zig function, so I explicitly require it. Any ideas?
2. I'm a little confused by what you mean when you say "the user writes his own wrapper for the data manipulation"? Do you mean they write their own AddNode function?
3. Hmm, maybe we could add a RemoveJustNode function that doesn't do any edge manipulation. I do not intend for the user to call these functions, the user should just call RemoveNode to remove a node. If a node no longer exists you would want the edges attached to it to go away.
4. Will do.
5. Will do. (edit: I discovered swapRemove, so I am now going to use that instead. Faster afaik. )
6. I'm a little confused here. The user can just add nodes to the graph without edges, or add as many edges between nodes if they want to. Is there something else you meant? Thanks for the detailed suggestions! This is all very useful, and I'll get to implementing this stuff soon.

[matu3ba]

how would an algorithm written for graphs know which struct value to use as weight?

There are 2 ways: 1. keep it separated from the graph. Then comptime closure can be used, but does not need to be.

2. If its inside the graph (ie edge or node representation), I dont know good ways to generalize and the user will likely copy-paste the code anyway. This could be called WeightedGraph in the abstract struct (as it is commonly phrased).

Do you mean they write their own AddNode function

Either this or they handle data separately. Your graphdata shows what an result could look like.

If a node no longer exists you would want the edges attached to it to go away.

Yes, though this is the responsibility of the user. Its common to use partially invalid graphs as iterators to generate the new graph structure. If you delete edges, the user must copy the structure.

The user can just add nodes to the graph without edges, or add as many edges between nodes if they want to. Is there something else you meant?

Yes. This may not be wanted, so it should be documented that its the users responsibility to check, if an edge n1 -> n2 already exists.

[sournav]

1. I think another possible way is to remove the edge to weight mapping from graph, and have the getWeight function return Then make a WeightedGraph struct that allows weights explicitly. There would then be a DataGraph, and WeightedDataGraph. That way all of the algorithms could still pretend that unweighted graphs have a weight of 1 for every edge, but the actual graph struct would be very simple.
2. Why not just rename RemoveNode, to RemoveNodeWithEdges, and add a RemoveNodeWithoutEdges function, or something similar.
3. Ahh got it. Yeah will do. Essentially graph supports a multigraph. I'll document this.

[matu3ba]

1. sounds good
2. also good idea.
3. good stuff.

https://git.skewed.de/count0/graph-tool was the link (so I can refer to it later).

Keep in mind to first make alot of tests of edge cases against memory leak stuff.

[matu3ba]

Hey @sournav, how are you doing? Did you manage to debug things so far etc?

[sournav]

Good, thanks for asking, you? My bad I got a little caught up with finals, I'll be working on this for the comming week. I should just have to finish adding comments in order to resolve this issue. Then I'll move to algos.

[matu3ba]

I am also busy with my thesis. No problem. First things first and good luck with the finals. Mitchell also became busy again (https://github.com/mitchellh/zig-graph).

[sournav]

Good luck with your thesis! Cool, another fellow zig grapher! Okay so I should be done with the general comments, and the rest of the issues we discussed as well. I will make a wiki with some of the specific design decisions, but overall I think we can close this issue if you don't have any additional comments. I'll be adding more features as I need to if it makes writing the graph algos easier.