Implement possibility of choosing git graph rendering algorithm

[marekyggdrasil]

Is your feature request related to a problem? Please describe.

I was analysing the problem mentioned in feature request #290 and I realised this is bigger change and demands more discussion and proper planning and design so I decided to open a proper feature proposal issue.

Briefly for those unfamiliar with #290, every time we branch a new column gets assigned to new branch even if there is available space. For projects with many short-lived branches layout grows really large pretty quickly. I prepared an example that demonstrates it pretty clearly:

Describe the solution you'd like

I came across the article commit graph drawing algorithms by @pvigier the developer of Gitamine who written a master thesis about this subject.

It appears like the process of rendering git graph consists of three steps

1. finding appropriate order of commits (x-coordinate of each commits)
2. finding appropriate column (compute y-coordinates)
3. optimise the layout

I propose to isolate those steps and implement separate functions for them so that user can select which algorithm would like to use

const options = {
  "sorting": "topological",
  "algorithm": "curved",
  "optimisation": "all-nodes-and-all-edges"
}

that gives full customisation regarding the output layout, for less advanced users who would want to replicate the behaviour of their favourite software we could prepare pre-defined layout, each consisting of sorting and column order algorithm and eventual optimisation, such as

const options = {
  "layout": "SourceTree"
}

would replicate the output as similar to SourceTree as we can reproduce

the disadvantage is, there would be a lot of code to take into account all those algorithms and possibly not enough contributors to implement all of those, so I also suggest and alternative solution

Describe alternatives you've considered

We could also adapt some code from Gitamine which is GPL-3.0 licenced, I briefly researched it and it looks like it is possible to include GPL-3.0 code in MIT licence project as stated here.

My alternative proposal is to still abstract out part of the code that assigns order to columns and keep the layout option proposed earlier as

const options = {
  "layout": "gitamine"
}

would use the Gitamine-based algorithm and

const options = {
  "layout": "regular"
}

would render everything exactly as it is now, also regular would be the default value so update would not break backwards compatibility and in the future we could consider using different layout as default if community demands it.

Additional context

I attach some figures from article by @pvigier, they demonstrate quite nicely the possible variety of layouts.

Also, I'd like to mention that I already forked and briefly researched the source and if there would be positive feedback on proposal I'll be happy to discuss techy details based on my notes and I can take care of the implementation.

I'd like to mention that the adapted algorithm by @pvigier I would commit separately and set him as the author of that commit.

GitCola	GitExtension
gitk	GitKraken
SmartGit	SourceTree

[nicoespeon]

Hey @marekyggdrasil 👋

I'm impressed by the quality of your research and very detailed issue.

I just created an issue to explain explicitly that I won't have time to deal with this, but I'm looking for volunteer to maintain the library: #328

Let me know if that's something you'd be interested in 😉
Thanks!

[pvigier]

Hi,

If you need my code to be under MIT license, I can change the license. And if you need more information concerning the algorithm, I can help.

Best,
Pierre

[marekyggdrasil]

Thanks guys!

@nicoespeon that is perfectly understandable, I think all I would need from you is basic code review and merging, I'll take care of implementation and make sure tests are passing etc. Regarding your need of help with maintenance, I could occasionally dedicate some time to help you out.

@pvigier so glad you joined the discussion! let me just play with your algo a bit and if I have questions I'll surely reach you, thanks for that!

Regarding the licence, unfortunately I'm not an expert so I can't comment on that, perhaps Nicolas (or anyone else following this discussion) could give some comments.

[nicoespeon]

@pvigier @marekyggdrasil regarding the license, we use the MIT license too. It's all good 👍

I'd like we credit Pierre's work in the README if we use his algorithm, so it's fair recognition 😉

[marekyggdrasil]

Glad the licence problem is resolved, and regarding the recognition I agree and I suggest the following:

1. Include his contribution in the README
2. Author the commit with the algorithm with his github e-mail so that it gets counted to his contributions
3. Name the rendering option gitamine after his project

[marekyggdrasil]

Some analysis.

The position of each commit depends on x, y coordinates (as gitgraphs are 2D). In case of @pvigier article they are labeled as x-coordinate and y-coordinate, in gitgraphjs we call them row and order (which makes sense as layout could be also vertical). For example in case of default layout:

gitgraph.js/packages/gitgraph-core/src/gitgraph.ts

Lines 376 to 381 in a4a26a2

	return commit.setPosition({
	x: this.initCommitOffsetX + this.template.branch.spacing * order,
	y:
	this.initCommitOffsetY +
	this.template.commit.spacing * (maxRow - row),
	});

For each commit rows.getRowOf(commit.hash) and branchesOrder.get(commit.branchToDisplay) are called as follows.

gitgraph.js/packages/gitgraph-core/src/gitgraph.ts

Lines 369 to 372 in a4a26a2

	const row = rows.getRowOf(commit.hash);
	const maxRow = rows.getMaxRow();
	const order = branchesOrder.get(commit.branchToDisplay);

And objects that provide them (rows and branchesOrder) are passed in the parameters

gitgraph.js/packages/gitgraph-core/src/gitgraph.ts

Lines 364 to 368 in a4a26a2

	private withPosition(
	rows: GraphRows<TNode>,
	branchesOrder: BranchesOrder<TNode>,
	commit: Commit<TNode>,
	): Commit<TNode> {

I plan to replace it with a single object called layout returning both coordinates for each commit. This object will differ default rendering form Gitamine rendering.

The entire layout is computed when rows and branchesOrder objects are created, notably in computeRenderedCommits() function.

gitgraph.js/packages/gitgraph-core/src/gitgraph.ts

Lines 224 to 229 in a4a26a2

	const rows = createGraphRows(this.mode, this.commits);
	const branchesOrder = new BranchesOrder<TNode>(
	commitsWithBranches,
	this.template.colors,
	this.branchesOrderFunction,
	);

I will replace this with computing the layout object and this object will be either computed using currently available createGraphRows() and BranchesOrder functions (by default to ensure backwards compatibility) either using a new function / object called Gitamine, and that one will be adapted from Pierres algorithm.

( no need to comment on that, although comments are always welcome, I'm just used to use issues as notepad, it might be somehow useful for future contributors )

[TheMightyMic]

Hi,

is this still being worked on? Or is there already a way to create graphs the way as they are discribed in the issue?

Greetings

[nicoespeon]

@TheMightyMic the issue is still relevant, nothing as changed in this direction yet.

ping @marekyggdrasil > would you be able / motivated to move on this topic?

[joliebig]

Hi,

I'm also interested in such a feature, not a configurable graph-rendering algorithm as suggested by @marekyggdrasil , but at least a fix that addresses the one-column-can-have-only-one-branch problem.

Best regards
jl

[marekyggdrasil]

Sorry for being silent, guys @TheMightyMic, @nicoespeon and @joliebig, seeing growing interest in this issue is really motivating, let's get back to work and have it done.

The biggest challenge currently is including the algorithm designed by @pvigier into the library. The reason why it is challenging is both algorithms operate on graph but differ in data structures and representation. The easiest way to do it would be to rewrite the rendering from gitgraph-core but it would break the backwards compatibility.

The solution I'm proposing is to abstract out the rendering, so that algorithm designed by Pierre could be included in the library without removing the default one, this would not break the backwards compatibility and allow to add customised rendering heuristics in the future.

Since there is interest in having it done, I will undust my notes and think about it during next few days, anyone willing to contribute please don't hesitate to reach me.

[marekyggdrasil]

Currently

1. computing positions is (was already) separated from rendering
2. I added options to be able to chose rendering algorithm

Now I will try to translate Gitamine algo, this is the part that computes positions

https://github.com/pvigier/gitamine/blob/0f66a960b1e52a5e9faba2cb791e5dfddabb3a29/src/renderer/helpers/commit-graph.ts#L54-L162

and include it here, this is where it is supposed to be computed

https://github.com/marekyggdrasil/gitgraph.js/blob/41e8315eb6414aad85f85437d098affb934f0819/packages/gitgraph-core/src/graph-rows/gitamine.ts#L7-L13

[marekyggdrasil]

Sorry it was just the rows... But today I made an update, both rows and columns for each individual commit are computer by a single function now

https://github.com/marekyggdrasil/gitgraph.js/blob/97f49e74bb5e3601f5322d0d182622feebf97051/packages/gitgraph-core/src/layout-algorithms/gitamine.ts#L10-L17

This function can be implemented for different layout rending algorithms, I'll try to translate gitamine algo into that

[marekyggdrasil]

For those of you who are looking forward for this feature to be implemented and want to keep track of the progress, feel free to check marekyggdrasil#1