Bonjour , je poste ici plus un problème de pensée que directement de code.
Je détiens un graphe dirigé (vertices + côtés) sous forme :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
 
struct edge
{
 const vertex[2] vertices; // le sens du côté est vertex[0] -> vertex[1]
}
 
struct vertex
{
 std::string name;
 bool explored // pour traverser le graphe avec l'algorithme DFS
 std::vector<const edge *> links; 
}
et un tableau de vertices et un autre de côtés. La disposition graphique que je cherche est une disposition où aucun côté ne doit passer sur un vertex pour en rejoindre un autre (e.g. le côté entre A et B ne doit pas être obligé de passer par C, tout en étant droit). L'intuition que j'ai est de regrouper les vertices en groupes d'éléments fortements connectés (groupe de vertices ou chaque vertice peut atteindre une autre, directement ou pas). Et de prendre ces groupes en tant que vertices d'un nouveau graphe, et ainsi de suite de manière récursive, pour pouvoir simplifier les relations. Bien que cela simplifie beaucoup le graphe, je ne sais pas comment disposer les vertices dans les groupes de vertices fortement connectées. Une position entre 0 et 1 est suffisante pour cet algorithme.Si cet algo prend en compte que le nombre de liens qu'a une vertice le rend proportionnellement plus "grand", cela sera apprécié, mais cela n'est pas obligatoire