Manipulation de graphs

Le
Maïeul
Bonjour,

je cherche à manipuler des graphs (au sens mathematiques, avec nœud et
relations).

Sur http://wiki.python.org/moin/PythonGraphApi il y a bcp de chose, et
j'hésite. Y-t-il des gens qui ont utiliés l'un ou l'autre pour me
conseiller.

J'ai besoin de :
- orienter les relations (A->B n'est pas B->A), mais en pouvant les
conservé non orientés.
- qualifier les relations (par exemple en terme de degré)
- exporter en TikZ

Avez vous une idée ?
merci


--
Maïeul Rouquette
http://geekographie.maieul.net/-LaTeX-
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Alain Ketterlin
Le #25335302
Maïeul
je cherche à manipuler des graphs (au sens mathematiques, avec nÅ “ud et
relations).



On dit aussi sommets et arcs/arêtes (les arcs ont des flêches, do nc sont
orientés).

Sur http://wiki.python.org/moin/PythonGraphApi il y a bcp de chose, et
j'hésite. Y-t-il des gens qui ont utiliés l'un ou l'autre pour me
conseiller.



Jamais essayé.

J'ai besoin de :
- orienter les relations (A->B n'est pas B->A), mais en pouvant les
conserver non orientés.



Il faut faire attention aux mélanges. La plupart des algorithmes
traitent l'un ou l'autre, mais pas les deux. Cela dit, on peut souvent
représenter une arête {a,b} (non orientée) par deux arcs (a, b) et (b,a).

- qualifier les relations (par exemple en terme de degré)



Pas compris. Tu veux des relations non-binaires (donc des hypergraphes)
ou bien tu veux des "labels" sur les arcs ?

- exporter en TikZ



(Au passage il me semblait que dot/graphivz est maintenant capable
d'exporter en TikZ -- après rapide vérification cela ne semble pa s être
le cas mais il y a toujours dot2tex. Je mentionne cela parce que si le
but est dessiner des graphes, graphviz est quasiment imbattable).

Avez vous une idée ?



J'ai fait cela plusieurs fois, mais la structure précise dépend d e ce
que tu vas faire avec. Voici quelques variantes :

- une simple liste de couples (sachant que les sommets sont identifiés
par les N premiers entiers) [ (sommet,sommet) ]

- un dictionnaire { sommet : [sommet] }

- un dictionnaire { (sommet,sommet) : label }

- une classe de sommets contenant une liste de successeurs
Sommet([sommet]), et/ou de prédecesseurs (des dict si il y a des
labels)

- ...

Théoriquement, il y a des contraintes de complexité (par exemple avec
{ sommet : [sommet] } chaque accès aux successeurs coûte quelque chose).
Dans la pratique il faut vraiment avoir des gros graphes (ou faire de
gros traitements) pour que ce soit sensible.

-- Alain.
Maïeul
Le #25335382
Le 12.04.13 17:02, Alain Ketterlin a écrit :
Maïeul
je cherche à manipuler des graphs (au sens mathematiques, avec nœud et
relations).



On dit aussi sommets et arcs/arêtes (les arcs ont des flêches, donc sont
orientés).


Merci pour ces réponses et les précisions. Comme dit, je ne suis pas un
scientifique de sciences dure, mais un littéraire ayant quelques notions
de math ... d'où les approximations

Sur http://wiki.python.org/moin/PythonGraphApi il y a bcp de chose, et
j'hésite. Y-t-il des gens qui ont utiliés l'un ou l'autre pour me
conseiller.



Jamais essayé.

J'ai besoin de :
- orienter les relations (A->B n'est pas B->A), mais en pouvant les
conserver non orientés.



Il faut faire attention aux mélanges. La plupart des algorithmes
traitent l'un ou l'autre, mais pas les deux. Cela dit, on peut souvent
représenter une arête {a,b} (non orientée) par deux arcs (a,b) et (b,a).



En fait je travaillerais d'abord avec des arêtes non orientés, puis je
les orienterais.
- qualifier les relations (par exemple en terme de degré)



Pas compris. Tu veux des relations non-binaires (donc des hypergraphes)
ou bien tu veux des "labels" sur les arcs ?



Des labels. Je souhaiterais par exemple dire que des relations soit
"primaire" et d'autres "secondaires".
- exporter en TikZ



(Au passage il me semblait que dot/graphivz est maintenant capable
d'exporter en TikZ -- après rapide vérification cela ne semble pas être
le cas mais il y a toujours dot2tex. Je mentionne cela parce que si le
but est dessiner des graphes, graphviz est quasiment imbattable).



effectivement graphivz est un outils très puissant. Le but est de
dessiner le graph à la fin et de l'intégrer dans ma thèse, qui est écrit
en LaTeX. D'ou Tikz.
Avez vous une idée ?



J'ai fait cela plusieurs fois, mais la structure précise dépend de ce
que tu vas faire avec. Voici quelques variantes :

- une simple liste de couples (sachant que les sommets sont identifiés
par les N premiers entiers) [ (sommet,sommet) ]

- un dictionnaire { sommet : [sommet] }

- un dictionnaire { (sommet,sommet) : label }

- une classe de sommets contenant une liste de successeurs
Sommet([sommet]), et/ou de prédecesseurs (des dict si il y a des
labels)

- ...

Théoriquement, il y a des contraintes de complexité (par exemple avec
{ sommet : [sommet] } chaque accès aux successeurs coûte quelque chose).
Dans la pratique il faut vraiment avoir des gros graphes (ou faire de
gros traitements) pour que ce soit sensible.

-- Alain.



a priori j'aurais moins d'une centaine de sommet.

Le seul type de traitement que j'aurais à faire c'est de modifier des
relations et de verifier que untel est ancetre/descendant d'untel, en
suivant les chemins qualifié de "primaire".


--
Maïeul Rouquette
http://geekographie.maieul.net/-LaTeX-
Alain Ketterlin
Le #25336152
Maïeul
[...] approximations



Aucun problème.

[...]
En fait je travaillerais d'abord avec des arêtes non orientés, puis je
les orienterais.



Je te conseille de faire une structure spécifique, avec deux ensembles,
un d'arcs et un d'arêtes. Ensuite tu peux écrire tes traitements.

Cela dit, as-tu vraiment besoin de python ? (Pour autre chose que la
génération de TikZ, j'entends.)

[...]
Des labels. Je souhaiterais par exemple dire que des relations soit
"primaire" et d'autres "secondaires".



OK.

[...]
effectivement graphivz est un outils très puissant. Le but est de
dessiner le graph à la fin et de l'intégrer dans ma thèse, qui est
écrit en LaTeX. D'ou Tikz.



La difficulté de ce genre d'exercice, c'est le placement des sommets. Si
tu as une structure très régulière, alors cela vaut peut-à ªtre le coup de
placer "à la main". Sinon, graphviz est vraiment très bien.

Je me souviens même avoir un jour utilisé un script awk pour tran sformer
le format "plain" de graphviz en PSTricks. Ca marchait bien, et c'est
aussi simple que possible.

[...]
a priori j'aurais moins d'une centaine de sommet.



Alors, mon conseil est d'utiliser la structure qui te semble la plus
simple.

-- Alain.
Maïeul
Le #25336142
Le 12.04.13 18:22, Alain Ketterlin a écrit :
Maïeul
[...] approximations



Aucun problème.

[...]
En fait je travaillerais d'abord avec des arêtes non orientés, puis je
les orienterais.



Je te conseille de faire une structure spécifique, avec deux ensembles,
un d'arcs et un d'arêtes. Ensuite tu peux écrire tes traitements.



du coup j'aurais un objet "aretes" qui pointerait vers les deux sommets ?

Cela dit, as-tu vraiment besoin de python ? (Pour autre chose que la
génération de TikZ, j'entends.)



oui, pour déterminer ces arêtes ;-) à partir d'un ensemble de textes et
de manuscrits.
[...]
Des labels. Je souhaiterais par exemple dire que des relations soit
"primaire" et d'autres "secondaires".



OK.

[...]
effectivement graphivz est un outils très puissant. Le but est de
dessiner le graph à la fin et de l'intégrer dans ma thèse, qui est
écrit en LaTeX. D'ou Tikz.



La difficulté de ce genre d'exercice, c'est le placement des sommets. Si
tu as une structure très régulière, alors cela vaut peut-être le coup de
placer "à la main". Sinon, graphviz est vraiment très bien.



si tout va bien (c'est à dire si mes manuscrits ne sont pas chiants),
j'aurais une structure de type "arbre généalogique".
Je me souviens même avoir un jour utilisé un script awk pour transformer
le format "plain" de graphviz en PSTricks. Ca marchait bien, et c'est
aussi simple que possible.

[...]
a priori j'aurais moins d'une centaine de sommet.



Alors, mon conseil est d'utiliser la structure qui te semble la plus
simple.

-- Alain.





--
Maïeul Rouquette
http://geekographie.maieul.net/-LaTeX-
Damien Wyart
Le #25337012
Bonsoir,

* Maïeul
je cherche à manipuler des graphs (au sens mathematiques, avec n½ud et
relations).

Sur http://wiki.python.org/moin/PythonGraphApi il y a bcp de chose, et
j'hésite. Y-t-il des gens qui ont utiliés l'un ou l'autre pour me
conseiller.

J'ai besoin de :
- orienter les relations (A->B n'est pas B->A), mais en pouvant les
conservé non orientés.
- qualifier les relations (par exemple en terme de degré)
- exporter en TikZ



Alain a déjà donné quelques éléments, je vais essayer de compléter
puisque j'ai quelques connaissances en théorie des graphes, en Python et
en (La)TeX et outils connexes (dont TikZ). Je vais tenter de ne pas trop
m'étendre, et on pourra approfondir des points précis par la suite si
besoin...

Déjà pour donner du contexte à la page wiki citée, les graphes sont un
des « serpents de mer » du monde Python concernant l'unification et
l'intégration d'une base commune à la bibliothèque standard. L'une des
discussions les plus anciennes (ayant un peu d'ampleur) à ce sujet date
de 2004 (elle est citée sur la page) et la plus récente date de fin
2012, mais il n'y a pas eu d'avancée concrète.
http://thread.gmane.org/gmane.comp.python.ideas/18140
http://thread.gmane.org/gmane.comp.python.ideas/18147
http://thread.gmane.org/gmane.comp.python.ideas/18240

La prolifération de bibliothèques concernant les graphes s'est un peu
tassée (beaucoup d'entre elles ne sont plus maintenues, y compris
graphine qui rencontrait un certain succès et se voulait assez souple,
facile et uniquement compatible avec Python 3.)

Le paysage est maintenant plus lisible, il y a 4 bibliothèques
maintenues et assez complètes, avec parfois des particularités (par
exemple une orientation vers les performances) :

- networkx http://networkx.github.io/
- igraph http://igraph.sourceforge.net/
- graph-tool http://projects.skewed.de/graph-tool/
- python-graph http://code.google.com/p/python-graph/

En très résumé et à mon avis :

- networkx est la plus utilisée, est très complète, mature, donc
à privilégier à mon avis.
- igraph est encore relativement jeune (non cité sur le wiki), oritenté
performances et avec des fonctionnalités liées à la (encore jeune)
science des réseaux (http://en.wikipedia.org/wiki/Network_Science)
- graph-tool est orientée performance donc graphes volumineux
- python-graph me semble en perte de vitesse (maintenance faible), assez
orienté algorithme mais sans réel point fort différenciant par rapport
aux autres

Donc, toujours à mon avis, tu as deux principales pistes :

- utiliser networkx (qui est bien documenté)
- puisque tes besoins semblent assez modestes, comme suggéré par Alain,
programmer juste ce dont tu as besoin directement en Python, avec des
structures de données « basiques », si networkx te semble trop
complexe, que tu souhaites maîtriser ce que tu fais ou le faire à ta
façon.

Enfin, l'aspect sortie (La)TeX :

Si tu utilises networkx, le plus simple est d'exporter en format dot
(la fonctionnalité existe, et je crois qu'elle existe dans les
4 bibliothèques que j'ai citées), puis d'utiliser dot2tex
(http://code.google.com/p/dot2tex/). Il y a eu quelques discussions pour
exporter directement de networkx vers Tikz mais ça n'a rien donné :
https://groups.google.com/forum/?fromgroups=#!topic/networkx-discuss/p3TZQn1D8Dw

Si tu programmes la partie graphes, soit tu exportes aussi en dot puis
dot2tex, soit tu exportes directement en Tikz (en codant le « style »
plus ou moins en dur), soit tu te bases sur les bibliothèques d'Alain
Matthes : http://altermundus.com/pages/tkz/index.html

A chaque fois que tu as dot2tex dans la chaîne de traitement, tu peux
aussi passer par Graphviz, qui a un format de sortie (d'après la doc, je
n'ai pas eu l'occasion de tester) permettant l'inclusion dans pdfLaTeX
après utilisation de ps2pdf (epstopdf semble ne pas fonctionner,
http://www.graphviz.org/pdf/dotguide.pdf) :
http://www.graphviz.org/doc/info/output.html#d:ps2
Sinon, l'inclusion en png ne doit pas poser de problème ; est-ce
envisageable pour toi ?

Pour terminer (finalement j'ai quand même été un peu long ;-), j'ai
aussi vu qu'il y avait eu un travail de thèse
http://www.tcs.uni-luebeck.de/downloads/papers/2011/2011-configurable-graph-drawing-algorithms-jannis-pohlmann.pdf
dans le domaine du rendu de graphes, inspiré de graphviz, qui semble
avoir été inclus dans Tikz. Les articles de blog écrits par l'auteur
sont intéressants mais je ne pense pas que cela t'aurait été utile vu
les besoins que tu as décrits (à part la syntaxe mais je ne sais la
comparer à celle des bibliothèques d'Alain, que je ne connais pas en
détail) :
http://gezeiten.org/post/2011/07/An-introduction-to-drawing-graphs-with-TikZ/PGF,-Part-1
http://gezeiten.org/post/2011/07/An-introduction-to-drawing-graphs-with-TikZ/PGF%2C-Part-2
http://gezeiten.org/post/2011/10/An-introduction-to-drawing-graphs-with-TikZ/PGF%2C-Part-3

La doc de Tikz (2.10) n'en parle pas, et l'inclusion semble dater de fin
2011, mais depuis cela semble avoir disparu ("temporary algorithms") :
http://pgf.cvs.sourceforge.net/viewvc/pgf/pgf/generic/pgf/graphdrawing/algorithms/layered/pgfgd-algorithm-Pohlmann-layered.lua?hideattic=0&view=log
http://pgf.cvs.sourceforge.net/viewvc/pgf/pgf/generic/pgf/graphdrawing/algorithms/layered/pgfgd-algorithm-GansnerKNV-layered.lua?hideattic=0&view=log

Apparemment la partie "graph drawing" a été remaniée mais je n'en sais
pas plus... C'est un peu bizarre que pgf reste sur CVS, c'est horrible
à utiliser pour fouiller dans l'historique !

Tantau semble avoir publié sur le sujet récemment :
http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2012-gd-presentation.pdf
(l'article correspondant est en accès payant)

Il y a donc maintenant une syntaxe pour les graphes dans Tikz mais je ne
sais pas depuis quand, ni non plus comment elle se compare à ce que j'ai
cité plus haut.


J'espère que ces éléments te seront utiles et t'aideront dans tes
réflexions ; je me rends compte que je n'ai pas beaucoup parlé Python et
on est peut-être hors-sujet ; dans ce cas, on fera peut-être le suivi
sur fctt... Désolé pour la longueur, en tous cas :)

--
DW
Damien Wyart
Le #25337002
Bonsoir,

* Maïeul
je cherche à manipuler des graphs (au sens mathematiques, avec n½ud et
relations).

Sur http://wiki.python.org/moin/PythonGraphApi il y a bcp de chose, et
j'hésite. Y-t-il des gens qui ont utiliés l'un ou l'autre pour me
conseiller.

J'ai besoin de :
- orienter les relations (A->B n'est pas B->A), mais en pouvant les
conservé non orientés.
- qualifier les relations (par exemple en terme de degré)
- exporter en TikZ



Alain a déjà donné quelques éléments, je vais essayer de compléter
puisque j'ai quelques connaissances en théorie des graphes, en Python et
en (La)TeX et outils connexes (dont TikZ). Je vais tenter de ne pas trop
m'étendre, et on pourra approfondir des points précis par la suite si
besoin...

Déjà pour donner du contexte à la page wiki citée, les graphes sont un
des « serpents de mer » du monde Python concernant l'unification et
l'intégration d'une base commune à la bibliothèque standard. L'une des
discussions les plus anciennes (ayant un peu d'ampleur) à ce sujet date
de 2004 (elle est citée sur la page) et la plus récente date de fin
2012, mais il n'y a pas eu d'avancée concrète.
http://thread.gmane.org/gmane.comp.python.ideas/18140
http://thread.gmane.org/gmane.comp.python.ideas/18147
http://thread.gmane.org/gmane.comp.python.ideas/18240

La prolifération de bibliothèques concernant les graphes s'est un peu
tassée (beaucoup d'entre elles ne sont plus maintenues, y compris
graphine qui rencontrait un certain succès et se voulait assez souple,
facile et uniquement compatible avec Python 3.)

Le paysage est maintenant plus lisible, il y a 4 bibliothèques
maintenues et assez complètes, avec parfois des particularités (par
exemple une orientation vers les performances) :

- networkx http://networkx.github.io/
- igraph http://igraph.sourceforge.net/
- graph-tool http://projects.skewed.de/graph-tool/
- python-graph http://code.google.com/p/python-graph/

En très résumé et à mon avis :

- networkx est la plus utilisée, est très complète, mature, donc
à privilégier à mon avis.
- igraph est encore relativement jeune (non cité sur le wiki), oritenté
performances et avec des fonctionnalités liées à la (encore jeune)
science des réseaux (http://en.wikipedia.org/wiki/Network_Science)
- graph-tool est orientée performance donc graphes volumineux
- python-graph me semble en perte de vitesse (maintenance faible), assez
orienté algorithme mais sans réel point fort différenciant par rapport
aux autres

Donc, toujours à mon avis, tu as deux principales pistes :

- utiliser networkx (qui est bien documenté)
- puisque tes besoins semblent assez modestes, comme suggéré par Alain,
programmer juste ce dont tu as besoin directement en Python, avec des
structures de données « basiques », si networkx te semble trop
complexe, que tu souhaites maîtriser ce que tu fais ou le faire à ta
façon.

Enfin, l'aspect sortie (La)TeX :

Si tu utilises networkx, le plus simple est d'exporter en format dot
(la fonctionnalité existe, et je crois qu'elle existe dans les
4 bibliothèques que j'ai citées), puis d'utiliser dot2tex
(http://code.google.com/p/dot2tex/). Il y a eu quelques discussions pour
exporter directement de networkx vers Tikz mais ça n'a rien donné :
https://groups.google.com/forum/?fromgroups=#!topic/networkx-discuss/p3TZQn1D8Dw

Si tu programmes la partie graphes, soit tu exportes aussi en dot puis
dot2tex, soit tu exportes directement en Tikz (en codant le « style »
plus ou moins en dur), soit tu te bases sur les bibliothèques d'Alain
Matthes : http://altermundus.com/pages/tkz/index.html

A chaque fois que tu as dot2tex dans la chaîne de traitement, tu peux
aussi passer par Graphviz, qui a un format de sortie (d'après la doc, je
n'ai pas eu l'occasion de tester) permettant l'inclusion dans pdfLaTeX
après utilisation de ps2pdf (epstopdf semble ne pas fonctionner,
http://www.graphviz.org/pdf/dotguide.pdf) :
http://www.graphviz.org/doc/info/output.html#d:ps2
Sinon, l'inclusion en png ne doit pas poser de problème ; est-ce
envisageable pour toi ?

Pour terminer (finalement j'ai quand même été un peu long ;-), j'ai
aussi vu qu'il y avait eu un travail de thèse
http://www.tcs.uni-luebeck.de/downloads/papers/2011/2011-configurable-graph-drawing-algorithms-jannis-pohlmann.pdf
dans le domaine du rendu de graphes, inspiré de graphviz, qui semble
avoir été inclus dans Tikz. Les articles de blog écrits par l'auteur
sont intéressants mais je ne pense pas que cela t'aurait été utile vu
les besoins que tu as décrits (à part la syntaxe mais je ne sais la
comparer à celle des bibliothèques d'Alain, que je ne connais pas en
détail) :
http://gezeiten.org/post/2011/07/An-introduction-to-drawing-graphs-with-TikZ/PGF,-Part-1
http://gezeiten.org/post/2011/07/An-introduction-to-drawing-graphs-with-TikZ/PGF%2C-Part-2
http://gezeiten.org/post/2011/10/An-introduction-to-drawing-graphs-with-TikZ/PGF%2C-Part-3

La doc de Tikz (2.10) n'en parle pas, et l'inclusion semble dater de fin
2011, mais depuis cela semble avoir disparu ("temporary algorithms") :
http://pgf.cvs.sourceforge.net/viewvc/pgf/pgf/generic/pgf/graphdrawing/algorithms/layered/pgfgd-algorithm-Pohlmann-layered.lua?hideattic=0&view=log
http://pgf.cvs.sourceforge.net/viewvc/pgf/pgf/generic/pgf/graphdrawing/algorithms/layered/pgfgd-algorithm-GansnerKNV-layered.lua?hideattic=0&view=log

Apparemment la partie "graph drawing" a été remaniée mais je n'en sais
pas plus... C'est un peu bizarre que pgf reste sur CVS, c'est horrible
à utiliser pour fouiller dans l'historique !

Tantau semble avoir publié sur le sujet récemment :
http://www.tcs.uni-luebeck.de/downloads/mitarbeiter/tantau/2012-gd-presentation.pdf
(l'article correspondant est en accès payant)

Il y a donc maintenant une syntaxe pour les graphes dans Tikz mais je ne
sais pas depuis quand, ni non plus comment elle se compare à ce que j'ai
cité plus haut.


J'espère que ces éléments te seront utiles et t'aideront dans tes
réflexions ; je me rends compte que je n'ai pas beaucoup parlé Python et
on est peut-être hors-sujet ; dans ce cas, on fera peut-être le suivi
sur fctt (je ne mets pas de followup-to pour le moment)... Désolé pour
la longueur, en tous cas :)

--
DW
Maïeul
Le #25337152
Le 12.04.13 23:36, Damien Wyart a écrit :
Bonsoir,

* Maïeul
je cherche à manipuler des graphs (au sens mathematiques, avec n½ud et
relations).



Sur http://wiki.python.org/moin/PythonGraphApi il y a bcp de chose, et
j'hésite. Y-t-il des gens qui ont utiliés l'un ou l'autre pour me
conseiller.



J'ai besoin de :
- orienter les relations (A->B n'est pas B->A), mais en pouvant les
conservé non orientés.
- qualifier les relations (par exemple en terme de degré)
- exporter en TikZ



Alain a déjà donné quelques éléments, je vais essayer de compléter
puisque j'ai quelques connaissances en théorie des graphes, en Python et
en (La)TeX et outils connexes (dont TikZ). Je vais tenter de ne pas trop
m'étendre, et on pourra approfondir des points précis par la suite si
besoin...





merci pour tout ces elements qui vont assurément nourrir ma réflexion.



--
Maïeul Rouquette
http://geekographie.maieul.net/-LaTeX-
Publicité
Poster une réponse
Anonyme