grafi

connessioni fra oggetti Java:

altro esempio

circuito elettronico:

altro esempio ancora

nazioni confinanti:

altri esempi

• strade e posti
• rete idrica
• assegnazioni di corsi ad aule
• …

cose connesse

astrazione

niente oggetti, circuiti elettronici, nazioni, ecc.
pallini con numeri o scritte
frecce

stesse connessioni
non dipende dalla provenienza
permette algoritmi generali

esempio

esempi

connessione indiretta

data una targa, si può sapere dove vive il proprietario della macchina?

dalla targa, si arriva alla città seguendo le frecce

un certo input può influire su una certa uscita?

da uno specifico punto di ingresso del circuito,
si arriva a uno specifico punto di uscita

si può andare da una nazione a un'altra senza nave?

dalla prima nazione, si arriva alla seconda seguendo le frecce?

…

stesso problema per tutti
seguire le frecce

planarità

si può realizzare un circuito senza ponticelli?

un ponticallo serve per incrociare due linee senza farle toccare
ma ha un costo

si possono disegnare le connessioni fra gli oggetti Java senza incroci?

gli incroci possono rendere confuso un diagramma

…

altri problemi

• quali sono le strade da mantenere per garantire le connessioni?
• quante macchine possono viaggiare insieme da un posto a un altro
• quali gruppi di persone si conoscono direttamente tutte fra loro?
• …

caratteristiche comuni

problemi su cose completamente diverse
stesso problema se visto su grafi:

• esiste un percorso di frecce da un punto a un altro?
• si può disegnare un grafo senza incrociare le frecce?
• c'è una parte di grafo in cui tutti sono connessi con tutti?
• …

problemi diversi ⇒ stesso problema su grafi
stesso algoritmo

definizione informale di grafo

pallini con frecce

come lo memorizzo in un programma?

memorizzazione

pallini

insieme di interi

frecce

dove parte e dove arriva ognuna
insieme di coppie di pallini

memorizzazione del grafo di esempio

pallini

insieme di interi

frecce

dove parte e dove arriva ognuna
insieme di coppie di interi

Pyton:

grafo = ({1,2,3,4}, { (1,2), (1,3), (2,3), (2,4) })

immagine e contenuto

memorizzati come…

grafi memorizzati

stesso grafo, visualizzazioni diverse

disegnare un grafo

stesso grafo, visualizzazioni diverse

disegnare un grafo, data la sua memorizzazione:

• difficile capire come disporre i nodi
• difficile capire come disegnare gli archi
  tutti dritti? con piegature?
• il disegno migliore può dipendere da dove viene il grafo
  oggetti Java o mappe
• vari modi per misurare la qualità del disegno
  incroci o piegature degli archi, posizione dei nodi

raffigurazione di un grafo (graph drawing)

programma per il disegno grafi

graphviz

grafo specificato come testo
lo visualizza in vari modi

graphviz: esempio

digraph G {
  1 -> 2;
  1 -> 3;
  2 -> 3;
  2 -> 4;
}

grafo.gv

perchè "di"graph?

digraph G {
  1 -> 2;
  1 -> 3;
  2 -> 3;
  2 -> 4;
}

DIgraph = DIrected graph
gli archi sono freccie, hanno una direzione

grafo non diretto =
gli archi sono segmenti

graph invece di digraph
segmenti 1--2, 1--3, ecc. invece di frecce

nondigrafo.gv

sottografi, cluster, stile di disegno

digraph G {
  1 -> 2;
  1 -> 3;
  2 -> 4;
  subgraph cluster_x {
    2 -> 3;
    style = filled;
    label = x;
    color = lightblue;
  }
  1 [shape=diamond, style=filled, color=red];
}

cluster.gv

• archi normali
• sottografi, cluster
• direttive su come disegnare

sottografo e cluster

digraph G {
  …

  subgraph cluster_x {
    2 -> 3;
    …
  }

  …
}

sottografo cluster_…
il nome deve iniziare con cluster

contiene i nodi fra le graffe
2 -> 3 quindi nodi 2 e 3

direttive di disegno

digraph G {
  …
  subgraph cluster_x {
    …
    style = filled;
    label = x;
    color = lightblue;
  }
  1 [shape=diamond, style=filled, color=red];
}

nodi riempiti, colorati, etichettati

anche per gli interi cluster

metodi di visualizzazione

layout engines

esercizio: memorizzare un grafo

memorizzarlo nella variabile grafo

stamparlo

memorizzare il grafo di esempio

grafo = ( (1,2,3,4), { (1,2), (1,3), (2,3), (2,4) } )
print(grafo)

esercizio: verificare se c'è una freccia

metodo arco(grafo, a, b) per vedere se c'è la freccia da a a b

metodo per vedere se c'è una freccia

# presenza di un arco fra due nodi
def arco(grafo, a, b):
	return (a,b) in grafo[1];

# prove 
print('1->2:', arco(grafo, 1, 2))
print('2->1:', arco(grafo, 2, 1))
print('1->4:', arco(grafo, 1, 4))

perchè "nodi" e "arco"?

nomi tecnici

nodo =

pallino

arco =

freccia

esercizio: trovare i successori

scrivere un metodo successori(grafo, nodo) che trova tutti i nodi che sono alla fine di un arco che parte dal nodo

metodo per trovare i successori

# successori di un nodo
def successori(grafo, nodo):
	return { b for (a,b) in grafo[1] if a == nodo }

# prova: successori di 1
print('successori di 1:', successori(grafo, 1))

da metodi a classe

i grafi servono a molte cose
in molti serve verificare se c'è un arco (freccia)
o trovare tutti i successori di un nodo (pallino)

fare una classe Grafo

classi in Python

la classe Grafo

class Grafo:
	# costruttore
	def __init__(self, nodi, archi):
		self.nodi = nodi
		self.archi = archi

dichiara una classe in Python
ogni oggetto contiene un insieme nodi e un insieme archi

altro da mettere nella classe?

class Grafo:
	# costruttore
	def __init__(self, nodi, archi):
		self.nodi = nodi
		self.archi = archi

aggiunte utili:

• conversione in stringa
• i due metodi di prima

la classe Grafo con le aggiunte

class Grafo:
	# costruttore
	def __init__(self, nodi, archi):
		self.nodi = nodi
		self.archi = archi

	# conversione in stringa
	def __str__(self):
		n = "nodi: " + ' ' + ' '.join({str(p) for p in self.nodi})
		a = "archi: " + ' '.join({"\n			 " + str(a[0]) + "->" + str(a[1]) for a in self.archi})
		return n + "\n"+ a

	# presenza di un arco
	def arco(self, partenza, arrivo):
		if partenza not in self.nodi:
			return False
		if arrivo not in self.nodi:
			return False
		return (partenza,arrivo) in self.archi

	# insieme dei successori di un nodo
	def setsuccessori(self, nodo):
		return {b for (a,b) in self.archi if a == nodo}

programma di prova

from tabella import Grafo

# grafo di esempio
grafo = Grafo({1,2,3,4}, { (1,2), (1,3), (2,3), (2,4) })
print(grafo)
print()

# presenza arco e successori
print('1->2:', grafo.arco(1, 2))
print('2->1:', grafo.arco(2, 1))
print('1->4:', grafo.arco(1, 4))
print()
print('successori di 1:', grafo.setsuccessori(1))

un altro grafo

esercizio: memorizzarlo in un oggetto

memorizzazione grafo

grafo = Grafo({ 1,2,3,4 },
              { (1,2), (2,1), (2,3), (3,2), (2,4), (4,2), (3,4), (4,3) })
print(grafo)

altro grafo ancora

grafo = Grafo({1,2,3,4,5,6},
              { (1,6),
	        (2,4),
		# 3
		# 4
		(5,3),
		(6,2), (6,3), (6,4), (6,5) })
print(grafo)

altri modi di memorizzare gli archi

# classe Grafo
class Grafo:
	# costruttore
	def __init__(self, nodi, archi):
		self.nodi = nodi
		self.archi = archi

	…

in seguito: archi memorizzati in altro modo
non con un insieme

insieme degli archi

# classe Grafo
class Grafo:
	# costruttore
	def __init__(self, nodi, archi):
		self.nodi = nodi
		self.archi = archi

	# insieme degli archi
	def insiemearchi(self):
		return self.archi

ovvio: l'insieme degli archi è self.archi
non ovvio: funziona anche con archi memorizzati in altro modo

altro modo di memorizzare gli archi

# classe Grafo
class Grafo:
	# costruttore
	def __init__(self, nodi, archi):
		self.nodi = nodi
		self.archi = archi

	# insieme degli archi
	def insiemearchi(self):
		…

si trova l'insieme degli archi
si ritorna al posto di self.archi

altro modo di memorizzare i nodi

# classe Grafo
class Grafo:
	# costruttore
	def __init__(self, nodi, archi):
		self.nodi = nodi
		self.archi = archi

	# insieme dei nodi
	def insiemenodi(self):
		return self.nodi

	# insieme degli archi
	def insiemearchi(self):
		…

stessa cosa per i nodi

metodo che ritorna l'insieme dei nodi
funziona anche se i nodi non sono memorizzati come un insieme