En lisant un peu la page que tu cites sur les itérateurs on trouve :
An external iterator may be thought of as a type of pointer that has two primary operations: referencing one particular element in the object collection (called element access), and modifying itself so it points to the next element (called element traversal).
Ici, vu la structure, ce qu'il faut c'est « tout simplement », pouvoir ré-ordonner les nœuds dans la construction qui est faite. C'est d'ailleurs l'une des premières choses qui sont abordées dans l'article. Un algorithme naïf permet de le faire facilement. On veut le noeud v en haut du graphe (pour avoir accès à son sommet, et ses arêtes) :
Si le graphe est vide, on plante
Si le nœud visible est v alors c'est fini
Sinon, on a un sous graphe et un nœud w. On met le nœud v en haut du sous-graphe avec un appel récursif. Ensuite, on construit le graphe Graphe (v, arv, Graphe (w, arw, sous-sous-graphe)) en faisant attention à ce que les arv et arw respectent les contraintes de la structure (ie: ce sont les arêtes entre le nœud et le sous graphe, qui ne peuvent pas faire référence à des nœuds qui sont définis plus haut).
C'est inductif, mais ça n'est pas linéaire.
Je pense que pour un type algébrique, une définition récursive donne toujours un moyen de parcours linéaire (sur une structure finie). En tout cas le cas du graphe tel que proposé marche bien :
Si c'est un graphe vide c'est fini
Si c'est un graphe non vide alors c'est un tuple (sommet, aretes_du_sommet, sous-graphe). Il suffit donc d'afficher le sommet, puis de continuer sur le sous graphe (qui n'a plus ce sommet).
La bonne propriété c'est que chaque nœud et chaque arête est vue une seule et unique fois.
Tu construit le graphe comme on construit un arbre.
En fait, c'est l'objectif du papier cité : avoir toute l'expressivité des graphes, avec la simplicité du traitement des arbres, sans trop perdre en performances.
[^] # Re: Map-Reduce
Posté par Aluminium95 . En réponse au journal Données vs Code. Évalué à 2.
En lisant un peu la page que tu cites sur les itérateurs on trouve :
Ici, vu la structure, ce qu'il faut c'est « tout simplement », pouvoir ré-ordonner les nœuds dans la construction qui est faite. C'est d'ailleurs l'une des premières choses qui sont abordées dans l'article. Un algorithme naïf permet de le faire facilement. On veut le noeud
ven haut du graphe (pour avoir accès à son sommet, et ses arêtes) :valors c'est finiw. On met le nœudven haut du sous-graphe avec un appel récursif. Ensuite, on construit le grapheGraphe (v, arv, Graphe (w, arw, sous-sous-graphe))en faisant attention à ce que lesarvetarwrespectent les contraintes de la structure (ie: ce sont les arêtes entre le nœud et le sous graphe, qui ne peuvent pas faire référence à des nœuds qui sont définis plus haut).Je pense que pour un type algébrique, une définition récursive donne toujours un moyen de parcours linéaire (sur une structure finie). En tout cas le cas du graphe tel que proposé marche bien :
(sommet, aretes_du_sommet, sous-graphe). Il suffit donc d'afficher le sommet, puis de continuer sur le sous graphe (qui n'a plus ce sommet).La bonne propriété c'est que chaque nœud et chaque arête est vue une seule et unique fois.
En fait, c'est l'objectif du papier cité : avoir toute l'expressivité des graphes, avec la simplicité du traitement des arbres, sans trop perdre en performances.