[Devember2021] Terminal graph editor

Development Code
1

This is project is reanimated from my pet-projects graveyard(Happy Halloween!) I’ve been working on it and out for couple of years, but never muster time to deliver something substantial. My hope that Devember(c) will be enough motivation for at least MVP.

About

GMPT(Graph ManiPulation Tool) is terminal visual graph editor inspired by vim. It aims to provide powerful, extensible and convenient interface and libraries for constructing, drawing and editing graphs.
Motivation

Graphs are very accessable tool for visually represent data relations(given that the graph have been layouted nicely). If you are visually oriented mind you probably thinking in graphs. But at the moment it is difficult to use graphs to share information with other people and its not because scarcity of offer.

Indeed, there are plenty of graph editing software on the market. Some of them, like draw.io, are online applications, which first assumes presence of desktop environment on my system, second - (browsers are) ravenous for system resources and third - reduces interactability with linux command environment. Well,you can circumvent online requirements by using containers, but that is even more hustle.

My main disappointment is that almost all of them require you to use mouse, which, do not get me wrong, very welcoming for new users, but for experienced user it only hinders their performance. In addition, mouse interactions are not easily scriptable, so writing plugins becomes pain in the butt. And lastly, Vim showed us that Great User Interface doesn’t have to be Graphical User Interface.

Main Usecases

This project tries to cover two main usecases:

  • user draws graphs interactively(for example mind-maps)
  • creation and modification of graphs can be done and sensed by other program (for example displaying control-flow of script/program while you writing it and modifying source code in reaction to modification of control-flow graph.

!NB: creation of translatrors source<->graph is outside of the scope of this project!)

Main Requirements

From this usecases follows main requirements:

  • ascii/unicode render system
  • robust and extensible command system
  • user input interface(key-binding schema, completion hints)
  • serialization/deserialization of graphs and graph modifications

MVP

Minimum viable product covers only first main usecase and include:

  • rendering nodes and links
  • text command system
  • load and save graphs
  • graph navigation
  • single buffer with one window
4 Likes
2

UPDATE 1

  • Added naive rendering system
  • Simple text command interface
  • Primitive visual mode command interface
  • Link pathing avoid obstacles

asciicast

4 Likes
3

Super cool project, as a developer who uses vim myself I’ve looked into ways to create graphs without a gui. There are projects out there like flowchart.js that generate images from text and so at least let you commit the flow chart in with your code and get diffs, but it’s fairly difficult (annoying?) to actually write the flow charts and get what you want because you have to constantly generate and open the image. It also irks me to have to leave my terminal. So I would be super excited if this project works out

4

Yeah, I agree with @pfeiferj , thats super cool, still a bit of work needed on some of those console strings (where the status line gets printed in the wrong place), but really great 1st update, keep it up (special thanks for the animated example, also cool, and very helpful)

5

Long time no see

If you thought I was dead … I wish I was. The project (and I) survived
soul-crushing refactoring. I should have posted frequently, though

Here is summary of what have been done:

  1. Components now are (mostly) decoupled from each-other and message-queue is implemented and tied them all together. Although this pattern simplifies unittesting, but, oh god, debuging it was hell.

  2. Rendering now allows to draw complex nodes like in demo below with text alignment(but not padding yet), decorations etc. Fancy

  3. Internal representation of graph was implemented. With event propagation, enumeration and other goodness

  4. Representation made possible of saving/loading graphs. It is plain JSON but for MVP it will do.

  5. Piping commands in and JSON out is crude but effective way of communication between programs

asciicast

TODO:

Now things that I need/want to do or need think about/help with.

Links

Link construction uses “lightning” algorithm. Link originates from some point and cast rays at every direction, forming the front. Then (at each step) each ray for the front scored (by length, number of kinks, distance to target, penalties for crossing obstacles, etc) and the goodest boy is selected. Then goodest boy propagates and re-radiates new rays in every direction (except one that already been seen by the front). Finally event of front reaching target point triggers selection of ray sequence.

Without score function complexity of this algorithm is quadratic(of distance
between source and target). Score function directs flow of the front towards target effectively speeding up algorithm. You can archive even bigger boost if before each run of this algorithm you contract space(by factor of 2), run algorithm on that contracted space and seed breadcrumbs(negative obstacles) of result path onto initial space.

This is fairly straightforward when there is only one start and one target and can be implemented using dynamic programming - every ray can calculate it next score from previous value. Unfortunately in case of hyper-graph, where links can connect multiple nodes, we no longer have luxury neither of localized score(ray score can be good for one target, but terrible to another) nor of simple stop condition.

Simplest solution of this problem would be just to run existing algorithm
N(N-1) times - for every node hyperlink connects - hyperlink rank.
Unfortunately this will clutter canvas - every previous path will add obstacles for next to avoid resulting in a tangled mess.

I will play with cost function and modify algorithms’ stop condition and if it will not help, I’ll try to modify algorithm to form the front from every point.

Refactor command structure

Now command is single textx-parser rule that is not very flexible if I want to
add or modify some command. Also I want for controllers that react to particular commands to be responsible for registering said commands. IMO it would localize and better document behavior of controllers.

I also want from command interface to present contextual help. For example when typing command I want to press (or <ctrl+?> or ) I want small pop-up to appear that lists all at this point possible commands with brief explanation of what they do. I need to think about command tree structure.

This idea clashes with concept of message queue somewhat - why do I need queue if I already know who is responsible for handling the command; whose responsibility is that if multiple controllers handles same type of command. I need to think things through first after all.

Minimap

Utilizing Braille font it is possible to render scaled down version of canvas.
This is definitely a feature creep and wont be present in scope of MVP, but very nice feature to have eventually.

Source

I will unprivate code repository as soon as quality of the code improves to
be at least not immediately actionable for indecent exposure:)

6

@pfeiferj @paulwratt I’m very sorry for long silence in this thread.

I would be very happy If you describe your use-case of this type of software so I could try accommodate their requirements:

  • What task you have in mind when you think of graph editor(I need as much context as you can reasonably provide)
  • What type of graphics your task need(flow-chart, sub-graphs, link-decoration, etc)
  • How would planing to interact with with graph editor? Does this task involves interaction of multiple program?
  • What IDE you use