langage déclaratif pour les graphes - Page 1

Ce truc là m'est resté dans la tête:
http://linuxfr.org/~Montaigne/25405.html

et aussi mon prof de combinatoire qui avait dit un jour: "si on pouvait programmer en disant 'je veux tous les noeuds de degré 3', je programmerais plus souvent". Autrement dit, il voulait un langage déclaratif.
Avec LINQ, Microsoft a inseré du déclaratif dans son langage impératif C#, une fois la requete executé, on utilise l'objet comme une collection classique. En gros, pour ceux qui connaissent pas, on peut faire (en gros hein c'est pas un truc exact là):

var les_noeuds_qui_minteressent = from noeud in db.noeuds
                                                  where Count(noeud.neighbours) == 3
                                                  select new noeud;

// et après

foreach (b in les_noeuds_qui_minteressent){
    traitement(b);
}

et comme le montre le lien, ca commence à bouger du coté du libre aussi.


D'où l'idée: faire un langage déclaratif pour traiter les graphes. Ca pourrait servir à pas mal d'étudiants en graphe, mais aussi à des professionels qui se retapent les mêmes algos de parcours à chaque coup.
Est-ce que ça existe déjà? J'ai suivi les liens du premier post, j'ai rien vu de précis pour les graphes. Sinon,
Je vois deux possibilités:

1)* Voir ça comme une surcouche de SQL. On peut très bien stocker le graphe sous forme de tables, et traduire la requete écrit en langage déclaratif des graphes en SQL en adaptant. (Là j'ai pris un exemple simple, mais il faudrait pouvoir gérer des cas plus compliqués du genre: "trouver les noeuds qui forment un stable et qui sont du même coté par rapport aux coupes que l'arete 5 intercepte" par exemple )


2)* plus élégant mais plus chiant: Refaire un interpreteur OQL. En partant éventuellement des outils libres qui existent, puisque ce n'est pas bon de réinventer la roue en la rendant carré

onur (./1) :
et aussi mon prof de combinatoire qui avait dit un jour: "si on pouvait programmer en disant 'je veux tous les noeuds de degré 3', je programmerais plus souvent".

http://www.aei.mpg.de/~peekas/tree/ <-- achement bien pour les graphes (bcp de types d'iterateurs)

Bah Prolog permet de jongler plutôt bien avec les graphes (les prédicats peuvent être utilisés pour déclarer des graphes).

Et qu'est-ce que ça gagne par rapport à:

foreach (Node *b, db.noeuds) {
  if (b->neighbors()==3) {
    ...
  }
}

qu'on peut avoir avec du C++ + Qt avec juste une classe pour les graphes (qui doit sûrement déjà exister quelque part d'ailleurs)?

Si c'est le fait que la liste est préfiltrée avant le foreach, ben, on peut avoir ça aussi:

template <typename T> QList<T> filterList (const QList<T> &list, bool (*filterFunc)(const T &item))
{
  QList<T> result;
  foreach (const T &item, list) {
    if (filterFunc(item)) result.append(item);
  }
  return result;
}

Ou alors on peut faire un itérateur qui filtre au moment où il est parcouru aussi, mais je n'ai pas envie de le coder maintenant.

Bref, je ne vois pas qu'est-ce qui n'est pas déjà faisable en C++ dans tout ça.

c'est vraiment imbitable le c++ pour moi

boaf, faut juste que t'en fasses pas mal une fois et apres ca roule hein... c'est sur que c'est plus selectif que le Java :P

Bah, les templates sont à vomir, mais l'idée est que tu n'as pas à écrire cette fonction template, juste l'utiliser.

5> oui, sans doute.

lY a rien qui est infaisable en C++. Mais l'idée c'est d'avoir un langage déclaratif... Select * from machin where trucchose= hello; n'est surement pas bien différent d'un while ou foreach...

Edit: Add: On veut que l'interpreteur sache comment le faire et non pas le programmeur qui n'a à dire que ce qu'il veut avoir.

Bah fait du Prolog ^^

wow ok... y a déjà eu des travaux dessus on dirait:

http://citeseer.ist.psu.edu/cache/papers/cs/7526/http:zSzzSzerciyes.ces.cwru.eduzSzshengzSzicde_ext.pdf/sheng99graph.pdf
mais ca reste purement mathématique j'ai l'impression.