Discussion :

[kinji]

Bonjour a tous,

Mon soucis n'est pas reellement python mais plutot algo en fait..
Vu que je code en python ca m'a semble etre un bon forum !

En entree, j'ai une list qui contient des tuples de cette forme :

[ (A, B), (C, D), (D, E) , (B, C)]

Ce qui doit me rendre la suite ordonne suivante :

[ A, B, C, D, E]

Comme vous l'avez compris chaque tuple est constitue de ( apres, avant).
Donc pour le premier tuple (A, B), cela signifie que : B s'execute apres A

J'ai A qui sera toujours mon point de depart !
Il faut eviter que ca se morde la queue aussi et des tuples peuvent etre sans apres et donc : (None, C) par exemple.
Du coup, on placera C tout a la fin de la liste.

Je me casse la tete la dessus depuis ce matin et pas moyen de sortir quelque chose qui couvre tout les cas...
Si quelqu'un y arrive, il a toute ma gratitude et reconnaissance !!!

Merci d'avance a tous !

PS : les "objets" sont de simples string ici !

[tyrtamos]

Bonjour,

Pourrais-tu préciser un peu plus le but à atteindre?

Tyrtamos

[kinji]

En fait chaque chaine represente le nom d'un script et ils doivent etre executes dans un certain ordre.
Cet ordre est defini dans le fichier xml de chaque script. En fait chaque script dit apres lequel il doit se lancer.

Chaque script est un objet python, je peux donc facilement creer la liste des scripts et leur precedant mais pour l'ordonner la.... J'ai besoin d'un coup de pate.

Mais certains n'ont pas besoin d'etre dans un certain ordre, d'ou les none dans les tuples.

Ca t'eclaires plus ?

[tyrtamos]

Eh, non. Il faudrait ajouter un exemple avec le début et la fin.

Si le début est: [ (A, B), (C, D), (D, E) , (B, C)], la fin, c'est quoi?

S'il s'agit de ranger par ordre des 'avants', c'est facile. J'ai fait des choses comme ça pour ordonner un planning de gantt en fonction des calculs de pert.

Par ailleurs, tu dis qu'il y a des tuples sans 'après' en citant comme exemple (None, C): ce ne serait pas plutôt (C, None)?

Tyrtamos

[rambc]

Bonsoir tyrtamos.

S'il s'agit de ranger par ordre des 'avants', c'est facile. J'ai fait des choses comme ça pour ordonner un planning de gantt en fonction des calculs de pert.

Par flemme et manque de temps, je serais preneur de ta méthode pour ce problème.

[eyquem]

Bonsoir,

(A, B), cela signifie que : B s'exécute apres A

Ceci est compréhensible.

chaque tuple est constitue de ( apres, avant).

Mais ceci ne l’est pas.
EDIT: ou du moins cela apparaît contradictoire avec ce qui précède.
Tu aurais dù écrire par exemple: (c’est apres ceci, qu’il y a cela)



Enfin bref, il me semble avoir quand même compris:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
li = [ ('H','I'),('E','F'),(None,'Q'),('A','B'),('J','K') ,('C','D'),
       ('D','E'),('F','G'),('B','C') ,('G','H'),(None,'R'),('I','J') ]
 
deek = dict( (u,v) for u,v in li if u )
res = ['A']
[ res.append(deek[res[-1]]) for i in xrange(len(deek)) ]
res.extend( v for u,v in li if u==None )
print res

Il faut évidemment que li contienne potentiellement la succession que l’on veut en extraire.
Pour gérer le risque qu’il n’en soit pas ainsi, il faudra ajouter une gestion d’exception.





NB:
certains ne sont pas d’accord avec mon usage de la compréhension de liste, mais je ne vois toujours pas ce qu’il y a de mal là dedans.

[dividee]

eyquem, ton code ne fonctionne pas dans un cas comme celui-ci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

li = [ ('A','B'), ('A','C')]

A priori, rien dans l'énoncé ne me dit que ce cas n'est pas à envisager.

De façon générale, on peut considérer la liste en entrée comme décrivant un graphe (sans cycle, espérons-le, sinon il n'y a pas de solution).
Le problème revient alors à effectuer un tri topologique de ce graphe. Deux algorithmes sont donnés dans la page référencée.

[kango]

bonsoir,

de ce que je comprends pour le moment je peux pondre ceci. la classe Action implémente une sorte de graphe.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
class Action(object):
    names = dict()
    def __new__(self, name):
        if name in Action.names:
            return Action.names[name]
        else:
            obj = object.__new__(self)
            obj.predecessor = None
            obj.follower = None
            Action.names[name] = obj
            return obj
    def __init__(self, name):
        self.name = name
    def is_first(self):
        return self.predecessor is None
    def is_last(self):
        return self.follower is None
    @classmethod
    def first(cls):
        res = [obj for obj in Action.names.values() if obj.is_first()]
        if len(res) != 1:
            raise ValueError('There should be only one first...')
        else:
            return res[0]
    def __str__(self):
        msg = "Action(name='%s'" % self.name
        if self.predecessor:
            msg += ", predecessor='%s'" % self.predecessor.name
        if self.follower:
            msg += ", follower='%s'" % self.follower.name
        msg += ")"
        return msg
    def flow(self):
        f = self.follower
        if f is not None:
            yield f
            for _f in f.flow():
                yield _f
 
data = [("E",None), ("C", "D"), ("A", "B"), ("B", "C"), ("D", "E")]
 
for first, second in data:
    a = Action(first)
    if second is not None:
        b = Action(second)
        a.follower = b
        b.predecessor = a
 
first = Action.first()
print first
 
for action in first.flow():
    print action

ce code retourne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Action(name='A', follower='B')
Action(name='B', predecessor='A', follower='C')
Action(name='C', predecessor='B', follower='D')
Action(name='D', predecessor='C', follower='E')
Action(name='E', predecessor='D')

l'idée c'est de créer des actions à partir de la liste que tu donnes en exemple, de trouver le point de départ (Action.first()) et d'itérer sur les actions à partir de ce point initial (first.flow()). La méthode flow est une méthode dite génératrice.

je suis parti du principe qu'il n'y a qu'un seul point de départ (mais on peut généraliser en itérant sur les différents points de départ si la méthode first() renvoie une séquence). je pars aussi du principe qu'une action n'a qu'un seul successeur (au maximum) (dans ce cas pour généraliser il faut définir l'attribut follower comme une séquence et modifier légèrement la fonction génératrice flow. c'est un peu moche mais c'est un point de départ.

edit: pas vu les 2 messages du dessus avant de poster. mais comme le dit dividee, je suis aussi parti sur un graphe non cyclique.

[eyquem]

eyquem, ton code ne fonctionne pas dans un cas comme celui-ci:
li = [ ('A','B'), ('A','C')]

En effet. Mais je l’ai écrit en pensant que ce cas ne peut pas, en tous cas ne doit pas, arriver.

En écrivant

Il faut évidemment que li contienne potentiellement la succession que l’on veut en extraire.

je voulais dire que tous les éléments de li différents de (None, qch) doivent être ordonnables dans une succession sans rupture de continuité.

Tu fais remarquer, dividee, qu’il ne doit pas non plus y avoir plusieurs tuples avec leurs premiers éléments identiques. C'est du moins l'idée logique à laquelle ta remarque me fait penser à partir de l’énoncé un peu brouillon.

A priori, rien dans l'énoncé ne me dit que ce cas n'est pas à envisager.

Je pense que si:

En fait chaque chaine represente le nom d'un script et ils doivent etre executes dans un certain ordre.
Cet ordre est defini dans le fichier xml de chaque script. En fait chaque script dit apres lequel il doit se lancer.

Chaque script est un objet python, je peux donc facilement creer la liste des scripts et leur precedant

« creer la liste des scripts et leur precedant » , comme il dit , doit consister à lire les fichiers xml des scripts et à extraire de chacun l’information (apres,avant) comme il dit. Je ne conçois pas qu’un mème fichier puisse donner deux tuples ('A','B') et ('A','C'),
ni que deux scripts puissent avoir le même nom ’A’.





Le code suivant est plus lisible que mon précédent.
J’y ai ajouté une vérification de la conformité de la liste de départ pour l’objectif recherché.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
li = [ ('H','I'),('E','F'),(None,'Q'),('A','B'),('J','K') ,('C','D'),
       ('D','E'),('F','G'),('B','C') ,('G','H'),(None,'R'),('I','J') ]
 
deek = dict( (u,v) for u,v in li if u )
plus = [ v for u,v in li if u==None ]
if len(deek)+len(plus)==len(li):
    x,res = 'A',['A']
    for i in xrange(len(deek)):
        x = deek[x]
        res.append(x)
    res.extend(plus)
    print res
else:
    print 'Donnees dans li incorrectes'

[eyquem]

Bravo, kango. J’avoue mon admiration devant la capacité d’écrire aussi rapidement un code aussi complexe.

Mais pourquoi faudrait-il compliquer une solution à un problème qui ne doit pas avoir la complexité traitable par ton code capable de déterminer un graphe ?

Pour moi, kinji veut trouver la succession simple dans laquelle doivent être exécutés plusieurs scripts. C’est tout.



Incidemment, j’ai une autre interrogation récurrente: pourquoi vouloir si souvent écrire des solutions dans le cadre d’une programmation par objets ??

[dividee]

Je ne conçois pas qu’un mème fichier puisse donner deux tuples ('A','B') et ('A','C'), ni que deux scripts puissent avoir le même nom ’A’.

Tel que je l'ai compris, si on a ('A','B') et ('A','C'), cela signifie que les scripts 'B' et 'C' dépendent tous les deux de l'exécution précédente de 'A'.
Suivant les mots du PO:

Donc pour le premier tuple (A, B), cela signifie que : B s'execute apres A

(en oubliant la terminologie (après, avant) qui induit en erreur).

[kinji]

Merci a tous pour vos solutions, je n'ai pas pu les tester encore (je viens juste de rentrer chez moi) mais je n'y manquerai pas.

Pour repondre a certaine question, en effet le cas ( A, B), ( A, C) peut arriver.

Cela signifie alors que la sortie doit etre A, B, C ou encore A, C, B. Il n'y a pas d'ordre entre B et C, ils doivent se situer apres B.

Cela dit on a parle d'eviter les cycles... je me permets de rajouter a ma question initiale : comment je peux les detecter car c'est aussi un soucis que j'ai rencontre et je ne sais que detecter des soucis de 1er niveau, par exemple si j'ai (B, C), je cherche dans ma list le tuple (C, B) et je m'arrete alors avec une erreur.
Mais cela n'est pas complet, n'est ce pas ?

Merci par avance de toutes votre aide, c'est vraiment tres gentil a vous, cela va m'inspirer

[kinji]

Je pense que si:

« creer la liste des scripts et leur precedant » , comme il dit , doit consister à lire les fichiers xml des scripts et à extraire de chacun l’information (apres,avant) comme il dit. Je ne conçois pas qu’un mème fichier puisse donner deux tuples ('A','B') et ('A','C'),
ni que deux scripts puissent avoir le même nom ’A’.

Bien que tu ai raison sur presque toutes la ligne, deux scripts peuvent avoir le meme precedant. Que ce soit A ou un autre car apres tout, si une personne ajoute un script, elle n'est pas oblige d'avoir connaissance de l'ordre des scripts actuellement en place

[tyrtamos]

Bonjour rambc,

...je serais preneur de ta méthode pour ce problème...

Pour le calcul d'un planning PERT ou d'un MPM (je préfère ce dernier), il est intéressant de commencer par ordonner les tâches en 'niveaux'.

Sur le principe, on a une liste de tâches, chaque tâche (une instance de classe en Python) étant caractérisée au minimum par son nom, sa durée et une ou plusieurs tâches précédente(s).

On ajoute un niveau (nb entier) à chaque tâche.

On boucle sur les niveaux (while True) et à l'intérieur, sur la liste des tâches (for...). Le while est nécessaire, parce qu'on ne sait pas d'avance combien il y aura de niveaux (entre 1 et le nombre total de tâches).

- le niveau 1 est bien entendu composé des tâches qui n'ont aucun précédent.

- le niveau 2 est composé des tâches qui n'ont comme précédents que les tâches de niveau 1

- etc... Chaque niveau i est composé des tâches qui n'ont comme précédents que les tâches de niveaux i-1 à 1.

- Le dernier niveau trouvé est logiquement composé par les tâches qui ne sont citées comme précédent par aucune autre tâche.

La boucle while se termine quand toutes les tâches ont leur niveau. Il faut ajouter une sécurité pour détecter les bouclages infinis: le nombre de niveaux ne peut pas dépasser le nombre total de tâches. Si on est dans un calcul MPM, il faut savoir tenir compte aussi des contraintes particulières, comme les précédents avec délais négatifs (imposition de délais minimum entre 2 tâches), problème que l'on résout en PERT par des tâches fictives (ex: "temps de séchage peinture").

On réordonne ensuite la liste des tâches selon les niveaux. En Python, on pourrait même regrouper les tâches de même niveau en sous-liste. Cela donne en tout cas une liste qui rend plus faciles:
- le calcul des dates et des marges (un coup dans un sens et un coup dans l'autre...)
- la représentation par graphe ou par gantt
- l'extension ou la compression du planning par modification des moyens si on gère les charges.

Ok?

Tyrtamos

[kango]

Bravo, kango. J’avoue mon admiration devant la capacité d’écrire aussi rapidement un code aussi complexe.

bonjour,

je ne pense pas qu'il soit aussi complexe que ça. c'est une implémentation très légère d'un graphe.

Mais pourquoi faudrait-il compliquer une solution à un problème qui ne doit pas avoir la complexité traitable par ton code capable de déterminer un graphe ? Pour moi, kinji veut trouver la succession simple dans laquelle doivent être exécutés plusieurs scripts. C’est tout.

par ce que visiblement, à la lumière des dernières informations le code doit pouvoir trouver des anomalies avant de devoir "orienter" les actions à exécuter.

Incidemment, j’ai une autre interrogation récurrente: pourquoi vouloir si souvent écrire des solutions dans le cadre d’une programmation par objets ??

bonne question . on n'a pas attendu l'avènement de la POO pour coder des algos complexes. la POO, le structuré, ce sont des outils. L'idée c'est de choisir celui qui semble le plus adapté à un moment donné. Tout traiter par une approche objet, c'est se priver des richesses algorithmiques proposées par les conteneurs standards de Python ou de l'approche fonctionnelle (voir l'autre file avec l'utilisation de sum). Systématiquement renier la POO est une erreur du même niveau selon moi.

l'approche objet sur un cas comme celui-ci sacrifie la concision (et la performance ?) au profil de l'évolutivité, de la souplesse et probablement de la clarté. Ensuite la question de la réutilisabilité est clairement en faveur de la POO. Dans le cas de cette file, ce qui existe en théorie des graphes me semble particulièrement adapté.

[kango]

Merci a tous pour vos solutions, je n'ai pas pu les tester encore (je viens juste de rentrer chez moi) mais je n'y manquerai pas.

Pour repondre a certaine question, en effet le cas ( A, B), ( A, C) peut arriver.

Cela signifie alors que la sortie doit etre A, B, C ou encore A, C, B. Il n'y a pas d'ordre entre B et C, ils doivent se situer apres B.

Cela dit on a parle d'eviter les cycles... je me permets de rajouter a ma question initiale : comment je peux les detecter car c'est aussi un soucis que j'ai rencontre et je ne sais que detecter des soucis de 1er niveau, par exemple si j'ai (B, C), je cherche dans ma list le tuple (C, B) et je m'arrete alors avec une erreur.
Mais cela n'est pas complet, n'est ce pas ?

Merci par avance de toutes votre aide, c'est vraiment tres gentil a vous, cela va m'inspirer

compte tenu de la difficulté croissante de ce que tu demandes, je t'encourage à aller voir du côté de networkx, c'est une librairie qui permet de traiter les graphes (cycliques ou non, orientiés ou non). l'idée serait alors:

- de "charger" l'information dont tu disposes en utilisant des graphes (directed graphs).
- d'utiliser les algos fournis par networkx pour identifier les cycles.

[dividee]

Voici une implémentation; une seule solution (arbitraire) est retournée s'il y en a plusieurs. Ce n'est pas spécialement optimisé; mais à moins qu'il n'y ait des dizaines de milliers de scripts à ordonner cela devrait convenir.

Le premier exemple est une situation déjà assez complexe (les arêtes vont de gauche à droite):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
  B -- D
 /      \
A        E -- H
 \      /
  C ---/
 
F -- G

Le second exemple ajoute une dépendance de A sur E pour tester la détection de cycle.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from itertools import chain
flatten = chain.from_iterable    # dedicated to eyquem ;)
 
class DGraph(object):
    def __init__(self):
        self.next = dict()
        self.prev = dict()
 
    def add_vertex(self, v):
        if v not in self.next:
            self.next[v] = []
            self.prev[v] = []
 
    def add_edge(self, (v1,v2)):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.next[v1].append(v2)
        self.prev[v2].append(v1)
 
    def postorder(self, v, result=None):
        "post-order DFS traversal from vertex v (no cycle detection)"
        if result is None:
            result = []
        for n in self.next[v]:
            if n not in result:
                self.postorder(n, result)
        result.append(v)
        return result
 
    def roots(self):
        "returns all vertices without predecessors"
        return (vtx for vtx, pred in self.prev.iteritems() if not pred)
 
    def topological_sort(self):
        return flatten(reversed(self.postorder(r)) for r in self.roots())
 
    def vertices(self):
        return self.next.iterkeys()
 
 
def dependency_sort(data):
    # build the graph
    G = DGraph()
    for e in data:
        if e[0] is None:
            G.add_vertex(e[1])
        else:
            G.add_edge(e)
 
    # sort the vertices
    l = list(G.topological_sort())
    # check for cycles:
    # if the graph has cycles, all vertices won't be in the result
    v = set(G.vertices())
    rest = v - set(l)
    if rest:
        print "Cycle detected. The following vertices leads to a cycle:", list(rest)
    else:
        print l
 
data = [(None, 'F'),('C','E'),('B','D'),('A','B'),('E','H'),('A','C'),('D','E'),('F','G')]
dependency_sort(data)
data = [(None, 'F'),('C','E'),('B','D'),('A','B'),('E','H'),('A','C'),('D','E'),('F','G'),('E','A')]
dependency_sort(data)

[kinji]

merci a tous pour toutes vos reponses et pistes, cela m'a bien aide a trouver la solution final a mon soucis .

Au final, j'ai fait un mix de vos solutions pour arriver a un parcours de ma structure et un ajout/recherche des dependances tout en supprimant les elements trouves dans ma liste.

Encore une fois, merci a tous !

[eyquem]

@ dividee


Ah oui oui, tu as tout à fait raison, dividee.

C’est pourtant clair:

kinji:
En fait chaque script dit apres lequel il doit se lancer.

Un fichier dit après quoi il s’exécute et non pas celui qui doit le suivre.
’B" peut très bien dire qu’il s’exécute après ’A’
et ’C’ dire qu’il s’exécute après ’A’.
Ça m’apprendra à m’auto-persuader:

eyquem, ton code ne fonctionne pas dans un cas comme celui-ci:
li = [ ('A','B'), ('A','C')]

En effet. Mais je l’ai écrit en pensant que ce cas ne peut pas, en tous cas ne doit pas, arriver.

Ben voyons, c’est plus simple ainsi: décider de ce qui peut et doit arriver en passant outre l’énoncé.

Je ne conçois pas qu’un même fichier puisse donner deux tuples ('A','B') et ('A','C'),

Ben si, mais pour ça, faut pas avoir une opinion toute faite.

eyquem: -5




@ kango

je ne pense pas qu'il soit aussi complexe que ça. c'est une implémentation très légère d'un graphe.

Pas ultra-complexe, non. Tout de même, il faut prendre le temps de le lire pour le comprendre... et je ne l’ai pas fait...


Maintenant que dividee m’a ouvert les yeux et que j’ai saisi le réel niveau de complexité du problème à traiter,
et compte tenu que

Dans le cas de cette file, ce qui existe en théorie des graphes me semble particulièrement adapté.

il m’est désormais compréhensible de faire appel à un programme un tantinet plus sophistiqué que le mien.


Qaunt à ton propos équilibré concernant la PO, je le trouve convaincant et dit comme ça je suis d’accord.







@ kinji

Je trouverais intéressant de voir quelle sorte de solution mixée tu as écrite.

[kinji]

Hop et voila la solution qui a resolu mon soucis :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
#!/usr/bin/python
 
class script(object):
    def __init__(self, name):
        self.name = name
        self.childs = []
        self.subtests = 0
 
    def addChild(self, mod):
        self.childs.append(mod)
 
    def buildChildren(self, element_list):
        left_list = []
        while (len(element_list) != 0):
            #Pop all the elements
            mod, depend = element_list.pop()
            if (depend == self.name):
                #Found a matching element
                self.addChild(plugin(mod))
                self.subtests +=1
            else:
                left_list.append((mod, depend))
 
        for child in self.childs:
            self.subtests += child.buildChildren(left_list)
 
        #Put the element that didn't match back into the list 
        element_list.extend(left_list)
        return self.subtests
 
    def display(self, time=0):
        print "\t"*time + "[%s sub_tests=%d]" % (self.name, self.subtests)
        for child in self.childs:
            child.display(time+1)
 
    def launch_tests(self):
        print "[%s] is executing its scripts" % self.name
        for child in self.childs:
            child.launch_tests()
def main():
    list  = [ ("A", None), ("B", "A"), ("C", "B"), ("D", None), ("E", "C") , ("G", "F"), ("F", "H"), ("H", "G")]
    Script_list = script(None)
    #first find all the elements that do not depend on another script
    Script_list.buildChildren(list)
 
    if len(list) != 0:
        print "some script couldn't be scheduled because of strange dependency"
        print list
 
    Script_list.display()
 
    Script_list.launch_tests()
 
if "__main__" == __name__:
    main()

Encore merci a tous pour votre aide et mise sur piste