C++ Dessin de graph en ASCII art

Tout est dans le titre.
Selon vous, qu'elle algorithme je pourrais utiliser pour dessiner un graph quelconque en ASCII Art ?
C'est assez compliqué en fait.

J'ai commencé quelque chose mais j'aimerais avoir vos avis sur un possible algorithme.
J'aimerais savoir comment placer les sommets et les arcs de la meilleure des manière possible. C'est une question ouverte.


Des idées ? Des pistes ?
On peut y réfléchir.

C'est quoi ta priorité?
La facilité d'édition manuelle?
Éviter les doublons lors de l'édition?

Car déjà, juste dessiner un graphe quelconque c'est un beau bordel...
Ce serait des arbres ça simplifierait tout.

Oui c'est une question ouverte

Les contraintes sont:
+ Nombre de sommetd < 15
+ Temps de calcul <= 1/5 s. ( Le temps de taper un un character)
+ Graph quelquonque sans arêtes multiples ni d'aretes réentrantes.
+ Les sommets sont des rectangles en ascci art
+ Les arêtes sont des lignes en ASCII art. Elle se déplace horizontalement, verticalement et tourne de 90 degré.

I'm faudrait faire des arêtes les plus droites possible. Peu de croisements. Et une surface de dessin la plus petite possible.

Pour l'instant je me contenterai de solutions très imparfaites.

J'ai eu le temps de faire mûrir l'idée.
Voilà ce que je pense faire:
1) Me restreindre aux graphe planaires, ce sont les graphes pouvant être dessinés dans le plan sans croisement de fils.
2) Faire une sorte de carte de visibilité comme sur cette image: https://www.semanticscholar.org/paper/A-Unified-Approach-a-Visibility-Representation-of-Tamassia-Tollis/582212a037a08a4c59da05ebf648729d70cd7268/figure/7.
3) Je vais dessiner le graph sur cette carte.

Pour générer une représentation planaire d'un graph, ce document est pas trop mal: http://cs.rkmvu.ac.in/~shreesh/media/planarity.pdf
Je risque de prendre un peu de temps à le développer moi même.
Je pense utiliser boost graph pour ça à la place: http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/planar_graphs.html
J'ai toujours eu un peu peur de Boost  et j'ai aussi peur de faire augmenter la taille du WebAssembly. On va voir.

Boost c'est génial pour les graphs (je l'ai utilisé 2x pour des gros algos), et en principe tout est en templates donc je pense que le compilo saura bien optimiser la taille.

J'ai un peu lutté, mais on peut dire que ça à fonctionné avec Boost!
J'ai encore un petit problème subtile, mais globalement, ça fonctionne:

C'est vachement cool