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.

[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.

[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

[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.