AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  Connexion  

Partagez
 

 C++ Dessin de graph en ASCII art

Aller en bas 
AuteurMessage
arthuro
Utilisateur confirmé: Rang ****
arthuro

Messages : 1448
Localisation : Paris
Projet Actuel : Diagon https://arthursonzogni.com/Diagon

C++ Dessin de graph en ASCII art Empty
MessageSujet: C++ Dessin de graph en ASCII art   C++ Dessin de graph en ASCII art EmptyMer 21 Fév 2018 - 21:49

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++ Dessin de graph en ASCII art PochetteC++ Dessin de graph en ASCII art Signature.php?gid=588
D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
onilink_
Modérateur
onilink_

Messages : 9108
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

C++ Dessin de graph en ASCII art Empty
MessageSujet: Re: C++ Dessin de graph en ASCII art   C++ Dessin de graph en ASCII art EmptyJeu 22 Fév 2018 - 17:38

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.

_________________
C++ Dessin de graph en ASCII art Runningpotato1C++ Dessin de graph en ASCII art TvF6GED C++ Dessin de graph en ASCII art MdetltS
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
arthuro

Messages : 1448
Localisation : Paris
Projet Actuel : Diagon https://arthursonzogni.com/Diagon

C++ Dessin de graph en ASCII art Empty
MessageSujet: Re: C++ Dessin de graph en ASCII art   C++ Dessin de graph en ASCII art EmptyVen 23 Fév 2018 - 18:29

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.

_________________
C++ Dessin de graph en ASCII art PochetteC++ Dessin de graph en ASCII art Signature.php?gid=588
D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
arthuro

Messages : 1448
Localisation : Paris
Projet Actuel : Diagon https://arthursonzogni.com/Diagon

C++ Dessin de graph en ASCII art Empty
MessageSujet: Re: C++ Dessin de graph en ASCII art   C++ Dessin de graph en ASCII art EmptyJeu 1 Mar 2018 - 22:12

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 Smile et j'ai aussi peur de faire augmenter la taille du WebAssembly. On va voir.

_________________
C++ Dessin de graph en ASCII art PochetteC++ Dessin de graph en ASCII art Signature.php?gid=588
D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
onilink_
Modérateur
onilink_

Messages : 9108
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

C++ Dessin de graph en ASCII art Empty
MessageSujet: Re: C++ Dessin de graph en ASCII art   C++ Dessin de graph en ASCII art EmptyVen 2 Mar 2018 - 9:54

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.

_________________
C++ Dessin de graph en ASCII art Runningpotato1C++ Dessin de graph en ASCII art TvF6GED C++ Dessin de graph en ASCII art MdetltS
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
arthuro

Messages : 1448
Localisation : Paris
Projet Actuel : Diagon https://arthursonzogni.com/Diagon

C++ Dessin de graph en ASCII art Empty
MessageSujet: Re: C++ Dessin de graph en ASCII art   C++ Dessin de graph en ASCII art EmptySam 10 Mar 2018 - 17:29

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++ Dessin de graph en ASCII art PochetteC++ Dessin de graph en ASCII art Signature.php?gid=588
D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
onilink_
Modérateur
onilink_

Messages : 9108
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

C++ Dessin de graph en ASCII art Empty
MessageSujet: Re: C++ Dessin de graph en ASCII art   C++ Dessin de graph en ASCII art EmptySam 10 Mar 2018 - 19:54

C'est vachement cool happy1

_________________
C++ Dessin de graph en ASCII art Runningpotato1C++ Dessin de graph en ASCII art TvF6GED C++ Dessin de graph en ASCII art MdetltS
Revenir en haut Aller en bas
Contenu sponsorisé




C++ Dessin de graph en ASCII art Empty
MessageSujet: Re: C++ Dessin de graph en ASCII art   C++ Dessin de graph en ASCII art Empty

Revenir en haut Aller en bas
 
C++ Dessin de graph en ASCII art
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Quelque Photo de mes bateaux
» Décès du dessinateur et caricaturiste Sid Ali Melouah
» eyeliner feutre ...
» The Meatrix
» Dessiner des émotions

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum Le CBNA :: Développement :: Programmation-
Sauter vers: