git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[RFC/PATCH v2] graph API: Use horizontal lines for more compact graphs

From
Allan Caffee <allan.caffee@gmail.com>
Date
Apr 21, 2009, 12:47 UTC
Message-ID
<20090421124701.GA25982@linux.vnet>
In-Reply-To
<alpine.DEB.1.00.0904211010410.10279@pacific.mpi-cbg.de>

Use horizontal lines instead of long diagonal during graph collapsing and precommit for more compact and legible graphs.

Signed-off-by: Allan Caffee <allan.caffee@gmail.com>
---
 graph.c        |   63 ++++++++++++++++++++++++++++++++++++++++++-------------
 t/t4202-log.sh |    6 +---
 2 files changed, 50 insertions(+), 19 deletions(-)
On Tue, 21 Apr 2009, Johannes Schindelin wrote:
Show 24 quoted lines
> Hi,
> 
> On Mon, 20 Apr 2009, Allan Caffee wrote:
> 
> > On Mon, Apr 20, 2009 at 8:56 PM, Johannes Schindelin
> > <Johannes.Schindelin@gmx.de> wrote:
> >
> > > On Mon, 20 Apr 2009, Allan Caffee wrote:
> > >
> > >> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? for (j = (target * 2)+3; j < (i - 2); j += 2)
> > >
> > > This (target*2)+3 is a bit too magical for me to understand. ?But 
> > > maybe I am just too tired?
> > 
> > It is a little magical.  Here target is an index into
> > graph->new_columns so we double that to get the actual location of the
> > edge in the string for this line.
> 
> Ah.  So how about
> 				 /*
> 				  * The variable target is the index of the graph
> 				  * column, and therefore target*2+3 is the actual
> 				  * screen column of the first horizontal line.
> 				  */
Sounds good to me.  Everything else look good?

Actually now that I look at it, it might be a good idea to put an assert statement in that for loop like `assert(graph->new_mapping[j] < 0)' to make sure we don't clobber any existing lines. But that seems like overkill since we're already assured to be the first collapsing edge at that point, which would imply that all previous odd indeces are empty. WDYT?

diff --git a/graph.c b/graph.c
index d4571cf..86577b4 100644
--- a/graph.c
+++ b/graph.c
@@ -47,20 +47,6 @@ static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
  * - Limit the number of columns, similar to the way gitk does.
  *   If we reach more than a specified number of columns, omit
  *   sections of some columns.
- *
- * - The output during the GRAPH_PRE_COMMIT and GRAPH_COLLAPSING states
- *   could be made more compact by printing horizontal lines, instead of
- *   long diagonal lines.  For example, during collapsing, something like
- *   this:          instead of this:
- *   | | | | |      | | | | |
- *   | |_|_|/       | | | |/
- *   |/| | |        | | |/|
- *   | | | |        | |/| |
- *                  |/| | |
- *                  | | | |
- *
- *   If there are several parallel diagonal lines, they will need to be
- *   replaced with horizontal lines on subsequent rows.
  */
 
 struct column {
@@ -982,6 +968,9 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 {
 	int i;
 	int *tmp_mapping;
+	short used_horizontal = 0;
+	int horizontal_edge = -1;
+	int horizontal_edge_target = -1;
 
 	/*
 	 * Clear out the new_mapping array
@@ -1019,6 +1008,23 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			 * Move to the left by one
 			 */
 			graph->new_mapping[i - 1] = target;
+			/*
+			 * If there isn't already an edge moving horizontally
+			 * select this one.
+			 */
+			if (horizontal_edge == -1) {
+				int j;
+				horizontal_edge = i;
+				horizontal_edge_target = target;
+				/*
+				 * The variable target is the index of the graph
+				 * column, and therefore target*2+3 is the
+				 * actual screen column of the first horizontal
+				 * line.
+				 */
+				for (j = (target * 2)+3; j < (i - 2); j += 2)
+					graph->new_mapping[j] = target;
+			}
 		} else if (graph->new_mapping[i - 1] == target) {
 			/*
 			 * There is a branch line to our left
@@ -1039,10 +1045,21 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			 *
 			 * The space just to the left of this
 			 * branch should always be empty.
+			 *
+			 * The branch to the left of that space
+			 * should be our eventual target.
 			 */
 			assert(graph->new_mapping[i - 1] > target);
 			assert(graph->new_mapping[i - 2] < 0);
+			assert(graph->new_mapping[i - 3] == target);
 			graph->new_mapping[i - 2] = target;
+			/*
+			 * Mark this branch as the horizontal edge to
+			 * prevent any other edges from moving
+			 * horizontally.
+			 */
+			if (horizontal_edge == -1)
+				horizontal_edge = i;
 		}
 	}
 
@@ -1061,8 +1078,24 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			strbuf_addch(sb, ' ');
 		else if (target * 2 == i)
 			strbuf_write_column(sb, &graph->new_columns[target], '|');
-		else
+		else if (target == horizontal_edge_target &&
+			 i != horizontal_edge - 1) {
+				/*
+				 * Set the mappings for all but the
+				 * first segment to -1 so that they
+				 * won't continue into the next line.
+				 */
+				if (i != (target * 2)+3)
+					graph->new_mapping[i] = -1;
+				used_horizontal = 1;
+			strbuf_write_column(sb, &graph->new_columns[target], '_');
+		}
+		else {
+			if (used_horizontal && i < horizontal_edge)
+				graph->new_mapping[i] = -1;
 			strbuf_write_column(sb, &graph->new_columns[target], '/');
+
+		}
 	}
 
 	graph_pad_horizontally(graph, sb, graph->mapping_size);
diff --git a/t/t4202-log.sh b/t/t4202-log.sh
index b986190..a3b0cb8 100755
--- a/t/t4202-log.sh
+++ b/t/t4202-log.sh
@@ -298,14 +298,12 @@ cat > expect <<\EOF
 * | | |   Merge branch 'side'
 |\ \ \ \
 | * | | | side-2
-| | | |/
-| | |/|
+| | |_|/
 | |/| |
 | * | | side-1
 * | | | Second
 * | | | sixth
-| | |/
-| |/|
+| |_|/
 |/| |
 * | | fifth
 * | | fourth

-- 
1.5.6.3
Previous: Johannes SchindelinNext: Johannes Schindelin
Message 5 of 17 in “graph API: Use horizontal lines for more compact graphs”
  1. graph API: Use horizontal lines for more compact graphsAllan Caffee, Apr 21, 2009
  2. Johannes SchindelinApr 21, 2009
  3. Allan CaffeeApr 21, 2009
  4. Johannes SchindelinApr 21, 2009
  5. graph API: Use horizontal lines for more compact graphsAllan Caffee, Apr 21, 2009
  6. Johannes SchindelinApr 21, 2009
  7. Bug in colored "log --graph" implementationTeemu Likonen, Apr 21, 2009
  8. graph API: fix extra space during pre_commit_line stateAllan Caffee, Apr 21, 2009
  9. Teemu LikonenApr 22, 2009
  10. Allan CaffeeApr 22, 2009
  11. 2/3 graph API: fix extra space during pre_commit_line stateAllan Caffee, Apr 22, 2009
  12. 1/3 t4202-log: extend test coverage of graphingAllan Caffee, Apr 22, 2009
  13. 2/3 graph API: fix extra space during pre_commit_line stateAllan Caffee, Apr 22, 2009
  14. 3/3 graph API: fix a bug in the rendering of octopus mergesAllan Caffee, Apr 22, 2009
  15. Allan CaffeeApr 22, 2009
  16. graph API: Use horizontal lines for more compact graphsAllan Caffee, Apr 27, 2009
  17. Junio C HamanoApr 27, 2009

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.