AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  Connexion  

Partagez | 
 

 C++ Dessin de graph en ASCII art

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

Messages : 1366
Localisation : Grenoble / Méribel
Projet Actuel : CBNA

MessageSujet: C++ Dessin de graph en ASCII art   Mer 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.

_________________

D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

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

MessageSujet: Re: C++ Dessin de graph en ASCII art   Jeu 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.

_________________
                 
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
avatar

Messages : 1366
Localisation : Grenoble / Méribel
Projet Actuel : CBNA

MessageSujet: Re: C++ Dessin de graph en ASCII art   Ven 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.

_________________

D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
avatar

Messages : 1366
Localisation : Grenoble / Méribel
Projet Actuel : CBNA

MessageSujet: Re: C++ Dessin de graph en ASCII art   Jeu 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.

_________________

D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

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

MessageSujet: Re: C++ Dessin de graph en ASCII art   Ven 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.

_________________
                 
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
avatar

Messages : 1366
Localisation : Grenoble / Méribel
Projet Actuel : CBNA

MessageSujet: Re: C++ Dessin de graph en ASCII art   Sam 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:

_________________

D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

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

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

C'est vachement cool happy1

_________________
                 
Revenir en haut Aller en bas
Contenu sponsorisé




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

Revenir en haut Aller en bas
 
C++ Dessin de graph en ASCII art
Revenir en haut 
Page 1 sur 1

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