Bienvenue sur IndexError.

Ici vous pouvez poser des questions sur Python et le Framework Django.

Mais aussi sur les technos front comme React, Angular, Typescript et Javascript en général.

Consultez la FAQ pour améliorer vos chances d'avoir des réponses à vos questions.

Optimisation d'un algorithme de coloriage bipartite

+3 votes

Je dispose d'un graphe bipartite (ici une maison) et l'objectif est de colorier chaque pièce de la maison avec seulement 2 couleurs (vert et bleu).
Par définition d'un graphe bipartite : une pièce verte n'a que des voisins bleus et inversement, à partir de la liste modélisant la maison, j'aimerais colorier chaque pièce et ressortir une liste donnant 2 si c'est vert et 1 si c'est bleu.

J'ai déjà fait un programme qui fonctionne correctement mais je ne sais pas comment l'optimiser ...

Ci-joint le dit programme :

La liste maison est une liste de liste où chaque pièce est définie par ses voisins ainsi [4,6,7] correspond à la pièce 3 et elle communique vers les pièces 4,6 et 7.

maison=[[7,9],[7],[7],[4,6,7],[3,5],[4,6],[3,5,13],[0,1,2,3,13,12,8],[7,11,9],[0,8,10],[9,11],[8,10,12],[7,11],[6,7]] 



def colorie(maison):
    m=len(maison)
    BLANC,BLEU,VERT=0,1,2
    couleur=[BLANC]*m
    couleur[0]=VERT
    for l in range(m):
        while couleur[l]==BLANC:
            for k in range(m):
                voisins=maison[k]
                for j in voisins:
                    while couleur[j]==BLANC and (couleur[k]==BLEU or couleur[k]==VERT):
                        if couleur[k]==BLEU: couleur[j]=VERT
                        elif couleur[k]==VERT: couleur[j]=BLEU
    return couleur

donc en colorie(maison) me ressort :

In [2]: colorie(maison)
Out[2]: [2, 2, 2, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 2]

demandé 17-Mar-2016 par Quentin
edité 17-Mar-2016 par max

1 Réponse

+7 votes

Il s'agit d'un problème de bi-coloration, qui peut être réglé avec un parcours de graphe.

La question porte ici sur «l'optimisation» du traitement.
La première proposition d'optimisation sera ici l'écriture d'un code plus idiomatique.
La seconde proposition portera sur l'efficience algorithmique même, et consistera en l'usage d'une bibliothèque dédiée à la manipulation des graphes.

Solution endémique ; optimisation de la forme

Voici une implémentation spécifique au problème, avec quelques cas typiques d'usage :

from collections import deque


def bicoloring(graph, color1='blue', color2='green'):
    """Return a list of colors where color at index i is the color of node of index i in given graph.

    Return None in case of a non bipartite graph.

    Input data should be an adjacency list,
    an indexable of iterable, where an iterable at the index i iters on i's successors.

    """
    nodes_color = {1: color1}  # the first node is colored with the first color

    nodes_fifo = deque([1])  # begin by the first node

    while len(nodes_fifo) > 0:
        node = nodes_fifo.popleft()
        succs = graph[node - 1]  # minus one because of indexing starting to 0
        color = nodes_color[node]
        expected_succ_color = color1 if color == color2 else color2

        for succ in succs:
            if succ not in nodes_color:
                nodes_color[succ] = expected_succ_color
                nodes_fifo.append(succ)
            elif nodes_color[succ] != expected_succ_color:
                # this graph is not bipartite
                return None
            else:  # succ already treated and correctly colored
                pass

    # return the list of colors
    return [nodes_color[node] for node in range(len(graph))]


# Test case
SIMPLE = [[2], [1]]
THREE = [[2, 3], [1], [1]]
CLIQUE = [[2, 3], [1, 3], [1, 2]]
MAISON = [[7,9],[7],[7],[4,6,7],[3,5],[4,6],[3,5,13],[0,1,2,3,13,12,8],[7,11,9],[0,8,10],[9,11],[8,10,12],[7,11],[6,7]]

# Output
print(bicoloring(SIMPLE))
print(bicoloring(THREE))
print(bicoloring(CLIQUE))
print(bicoloring(MAISON))

Méthode

Le code ci-dessus utilise un parcours BFS (on regarde tous les voisins d'un nœuds un par un, puis on regarde les voisins des voisins, etc).

L'idée est d'associer à chaque voisin (succ) du nœud considéré (node) la couleur (expectedsucccolor) qui n'est pas celle du nœud.
Dés lors qu'un nœud devant être coloré en bleu se trouve être voisin d'un nœud lui aussi coloré en bleu, la clause elif est évaluée comme vrai, et le programme retourne None immédiatement.

L'usage d'un deque, et plus particulièrement la méthode popleft, définit le comportement du parcours. En utilisant la méthode pop, (l'usage d'un deque plutôt qu'une liste est alors inutile) le parcours se ferait alors en profondeur, Ce qui ne changera pas grand chose au résultat final.
Dans le cadre d'une bicoloration, le parcours en largeur est néanmoins plus logique (du moins conceptuellement ; je soupçonne un gain potentiel de performance dans le cas de graphe non bipartite, quelqu'un a une idée ?).

Discussion

Cette fonction n'est pas robuste aux graphes dont la définition est incomplète, par exemple [[2], []]. Cela reviens à dire qu'elle considère le graphe comme orienté.

L'usage de constantes littérale comme nom de couleur est inutile : dans le cadre d'une bicoloration, un booléen suffirait.

Solution standard ; optimisation du fond

Avec une bibliothèque telle que networkx (ma référence personnelle concernant les graphes en python), il est possible de travailler sur les graphes bipartites à l'aide de nombreuses fonctions dédiées.

Voici un code montrant comment (1) construire un graphe networkx depuis la liste d'adjacence encodant les données de la question initiale, et (2) générer une coloration du graphe.

import networkx as nx
from networkx.algorithms import bipartite


def networkxised(adjacent_list):
    """Return an nx.Graph instance describing given adjacent list"""

    # Create the networkx graph
    g = nx.Graph()
    for node, succs in enumerate(adjacent_list, start=1):
        for succ in succs:
            g.add_edge(node, succ)
    return g


# Test case
MAISON = [[7,9],[7],[7],[4,6,7],[3,5],[4,6],[3,5,13],[0,1,2,3,13,12,8],[7,11,9],[0,8,10],[9,11],[8,10,12],[7,11],[6,7]]


g = networkxised(MAISON)
colors = bipartite.color(g)  # dictionnary node: color

print('GRAPH:', g)
print('Is Bipartite:', bipartite.is_bipartite(g))
print('Sets of nodes:', bipartite.sets(g))
print('Bicoloring:', colors)

# print the list of colors
print([colors[node] for node in range(len(graph))])

Le code critique (la bi-coloration) est réalisée par un module de référence, à l'aide d'une API simple et efficace.
L'intérêt de cette approche est double : le code gagne en abstraction, et la partie algorithmique est largement optimisée.

Conclusion

Dans une vaste majorité de cas, des librairies existent et font déjà une grosse partie des traitements souhaités. (c'est particulièrement vrai pour Python et d'autres langages à la communauté dynamique)
Ici, networkx est tout à fait indiquée pour le job.

Enfin, lorsque le code doit être écrit «à la main», alors il devient important de le rendre lisible et standard.
Je ne sais pas si la solution proposée est parfaitement pythonique (certainement que non), mais elle utilise un algorithme (DFS) et des structures de données (dictionnaire, deque) standards, et respecte les conventions principale d'écriture de code Python défini par la PEP8.

répondu 17-Mar-2016 par lucas (2,332 points)
edité 19-Mar-2016 par lucas

Petite simplification du premier code (qui retourne cette fois un dict) :

def bicoloring(graph, colors=('blue', 'green')):
    nodes_color = {0: 0}  # first node is colored with the first color
    nodes_lifo = [0]      # begin by the first node

    while nodes_lifo:
        node = nodes_lifo.pop()
        expected_color = 1 - nodes_color[node]
        for succ in graph[node]:
            if succ not in nodes_color:
                nodes_color[succ] = expected_color
                nodes_fifo.append(succ)
            elif nodes_color[succ] != expected_color:
                # this graph is not bipartite
                return None

    return {node: colors[i] for node, i in nodes_color.items()}

Concernant l'usage de networkx, c'est vrai que c'est une lib de référence pour tout ce qui touche aux graphes, et je l'apprécie beaucoup personnellement, mais il est parfois plus pratique de ne pas avoir trop de dépendances dans un projet, surtout pour des choses aussi simples.

En ce qui concerne la performance, je crois qu'on peut difficilement faire plus performant. D'ailleurs, ça correspond à peu de choses près à ce que fait networkx (la différence principale est qu'ils traitent aussi les graphes orientés et les graphes non-connexes).

cool de filer une réponse aussi complète, gg !

@boblinux: merci !

@yoch: retourner un dictionnaire n'est pas ce qui est demandé dans l'OP, mais c'est effectivement ainsi que je ferais personnellement. (encore que cela dépende de l'usage des données en aval)

Merci beaucoup pour vos réponses :)
Si je comprend bien pour effectuer ce coloriage de façon optimum on doit passer par des bibliothèques comme networkx ?
Je vais vérifier si dans notre projet on peut importer d'autres bibliothèques que celles déjà présentes dans Python car l'étude des graphs ne fait pas partie de notre programme, c'est pour cela que j'utilise des listes de listes pour modéliser un graph (ce qui est moins pratique je vous l'accorde).

ISN ? Tu ne devrais pas être limité par cela. Apprendre la programmation passe aussi (et surtout) par l'usage de librairies de référence.

Et, même en utilisant des listes d'adjacences (listes de listes), tu utilise des graphes. La seule différence avec un dictionnaire, c'est la manière de les encoder ; mais c'est ultimement la même chose, et la même théorie qui est derrière : la théorie des graphes.

Pense à accepter la réponse si elle te conviens.

...