# -*- coding: iso-8859-1 -*-
from __future__ import division # 1/2 == .5 (par defaut, 1/2 == 0)

##--------------------------------------#######
#                Graphes                  #
##--------------------------------------#######
#    WxGeometrie
#    Dynamic geometry, graph plotter, and more for french mathematic teachers.
#    Copyright (C) 2005-2007  Nicolas Pourcelot
#
#    This program is free software; you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation; either version 2 of the License, or
#    (at your option) any later version.
#
#    This program is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    You should have received a copy of the GNU General Public License
#    along with this program; if not, write to the Free Software
#    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

# version unicode

# from resolution import *


from pylib import *
import sympy


class Graphe(dict):
    def __init__(self, arg = ()):
        if isinstance(arg, basestring):
            arg = [self._couper(s) for s in arg.split(';')]
        dict.__init__(self, arg)


    @staticmethod
    def _couper(chaine):
        nom, sommets = chaine.split(':')
        nom = nom.strip()
        sommets = [sommet.strip() for sommet in sommets.split(',')]
        return nom, sommets


    @property
    def ordre(self):
        return len(self)

    @property
    def sommets(self):
        return sorted(self)

    @property
    def matrice(self):
        n = self.ordre
        sommets = self.sommets
        def f(i, j):
            return self[sommets[i]].count(sommets[j])
        return sympy.Matrix(n, n, f)

    def degre(self, sommet):
        return len(self[sommet])

    @property
    def degres(self):
        return dict((sommet, self.degre(sommet)) for sommet in self.sommets)

    @property
    def dictionnaire(self):
        return dict(self)

    def adjacents(self, sommet1, sommet2 = None):
        if sommet2 is None:
            adjacents = set(self[sommet1])
            adjacents.update(sommet for sommet in self if sommet1 in self[sommet])
        return sommet1 in self[sommet2] or sommet2 in self[sommet1]

    @property
    def connexe(self):
        def adjacent(sommet, nouveaux):
            return any(self.adjacents(nouveau, sommet) for nouveau in nouveaux)

        restants = set(self)
        nouveaux = [restants.pop()]
        while nouveaux:
            nouveaux = [sommet for sommet in restants if adjacent(sommet, nouveaux)]
            restants.difference_update(nouveaux)
        return not restants

    @property
    def symetrique(self):
        M = self.matrice
        return M.tranpose() == M

    def coloriage(self, *premiers_sommets):
        u"""Coloriage par l'algorithme de Welsh & Powell.

        Les sommets sont classés par degré, mais on peut forcer
        les choix des premiers sommets à parcourir.
        """
        coloriage = []
        non_colories = sorted(self, key = self.degre, reverse = True)
        if premiers_sommets:
            non_colories = list(premiers_sommets) \
                        + [s for s in non_colories if s not in premiers_sommets]
        self._classement_sommets_dernier_coloriage = non_colories[:]
        while non_colories:
            coloriage.append([])
            for sommet in non_colories:
                if not any(self.adjacents(sommet, s) for s in coloriage[-1]):
                    coloriage[-1].append(sommet)
            assert coloriage[-1]
            non_colories = [s for s in non_colories if s not in coloriage[-1]]
        return coloriage


    def latex_tableau_coloriage(self, *premiers_sommets):
        def couleurs():
            teintes = ('bleu', 'rouge', 'vert', 'jaune', 'orange', 'violet',
                        'marron', 'rose', 'turquoise', 'cyan', 'magenta', 'ocre',
                        'marine', 'indigo', 'pourpre')
            num = 0
            while True:
                yield (teintes[num] if num < len(teintes) else 'couleur %s' %num)
                num += 1

        dico = {}
        for sommets, couleur in zip(self.coloriage(*premiers_sommets), couleurs()):
            for sommet in sommets:
                dico[sommet] = couleur
        # Génération du code LaTeX
        ligne_sommets =  r'Sommets '
        ligne_degres =   r'Degr\'es'
        ligne_couleurs = r'Couleurs'
        for sommet in self._classement_sommets_dernier_coloriage:
            ligne_sommets += ' & $%s$ ' %sommet
            ligne_degres += ' & $%s$ ' %self.degre(sommet)
            ligne_couleurs += ' & %s ' %dico[sommet]
        code = r'\begin{tabular}{|l||*{%s}{c|}}' % len(dico)
        code += '\n\\hline\n'
        code += ligne_sommets + '\\\\\n\\hline\n'
        code += ligne_degres + '\\\\\n\\hline\n'
        code += ligne_couleurs + '\\\\\n\\hline\n'
        code += '\\end{tabular}\n'
        return code

