Avui a classe han presentat l’algorisme Havel-Hakimi per a validar i dibuixar grafs. Després han posat una sèrie d’exercicis i com que no em venia de gust fer-los he buscat una implentació de l’algorisme per internet, i al no trobar-la la he fet jo, a més, et mostra els passos intermitjos per a poder copiar-ho a la pràctica. Aqui la teniu. A veure si aquest cap de setmana puc acabar-ho perquè en calculi les alternatives i ho dibuixi.

def comprova(nodes):
    if sum(nodes) % 2 != 0:
      print 'la suma se graus no es parell'
      return 0
    if max(nodes) > len(nodes)-1:
      print 'hi ha un node de grau mes gran que el total de nodes'
      return 0
    if min(nodes) < 0:
      print 'hi ha un node de grau negatiu'
      return 0
    if max(nodes) == 0:
      print 'es un graf correcte'
      return 0
    return 1

# mostra de Butà un hidrocarbó amb fórmula C4H10
nodes = [4,4,4,4,1,1,1,1,1,1,1,1,1,1]
# mostra d'una definició de graf incorrecte
# nodes = [6,5,5,5,5,2,1,1]

while (comprova(nodes)):
  print nodes
  nodes2 = list(nodes)
  nodes.sort()
  nodes.reverse()
  if nodes!=nodes2: print str(nodes) + " ordenat"
  node = nodes.pop(0)
  for i in range(node):
    nodes[i]=nodes[i]-1
print nodes

Aquesta entrada es va publicar el 2010 02 19 a les 17:06 i està arxivada a Codi. Pots seguir-ne les respostes a través del RSS 2.0. Els comentaris i els pings no estan permesos actualment.