<jupyter_start><jupyter_text>Resolução de Problemas Computacionais com Grafos  Aula 1 1. Apresentação da disciplina  - Ideia da disciplina  - Linguagens: Python, Java1. Apresentação do Plano de Ensino1. Conceito de Grafo: ideia, exemplos    - Representação de grafos por matrizes de adjacências  Avaliação Formativa 1 Escrever uma função que receba como entrada uma matriz de adjacências e que retorne a quantidade de vértices e a quantidade de arestas.Entregar um arquivo `.py` ou `.ipynb`; no arquivo entregue, colocar o nome dos integrantes da dupla de alunos.`vertices_arestas(m: matriz): (num_vertices: Int, num_arestas: Int)`<jupyter_code># Exemplo de matriz de adjacências
m1 = [[1, 0, 0], [0, 1, 1], [0, 1, 0]]<jupyter_output><empty_output><jupyter_text>Aula 2  Resolução do exercío 1  <NAME><jupyter_code>m1 = [[0,0,1],[1,0,0],[0,0,0]]

def calcMatriz(m):
  vertices = 0
  arestas = 0
  for i in m:
    arestas +=1
    for j in i:
      vertices += 1 if j == 1 else 0
  # print('Arestas: {} | Vertices: {}'.format(arestas,vertices))
  return (vertices, arestas)
calcMatriz(m1)<jupyter_output><empty_output><jupyter_text><NAME><jupyter_code>def matriz_adjacencia(matriz):
    return [sum([sum(i) for i in matriz])], len(matriz)
matriz_adjacencia(m1)
def matriz_adjacencia1(matriz):
    return (len(matriz), sum([sum(i) for i in matriz]))
matriz_adjacencia1(m1)<jupyter_output><empty_output><jupyter_text><NAME><jupyter_code>def NArestas(matriz):
    vertice = 0
    for coluna in matriz:
        for linha in coluna:
            if linha == 1:
                vertice += 1
    aresta = vertice*(vertice - 1)/2
    return (vertice, aresta)
NArestas(m1)<jupyter_output><empty_output><jupyter_text>Amanda<jupyter_code>from functools import reduce 

m2 = [[0,1,0,0,0,0],[0,0,0,0,1,0],[0,0,0,1,0,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,0,0,1,0]] 

def arestas(m): 
    if len(m) == 1:
        return m[0]
    else:
        return m[0] + arestas(m[1:])

def vertices_arestas(m):
    return ([len(m) , reduce((lambda x, y: x + y), arestas(m)) ])
vertices_arestas(m2)<jupyter_output><empty_output><jupyter_text>Allan<jupyter_code>matriz1 = [[0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0]]
 
def calc_vertice(matriz):
    return len(matriz[0])
 
def calc_aresta(matriz):
    if matriz == []:
        return 0 
    return sum(matriz[0]) + calc_aresta(matriz[1:])
 
def vertices_arestas(matriz):
    return (calc_vertice(matriz), calc_aresta(matriz))
vertices_arestas(matriz1)<jupyter_output><empty_output><jupyter_text>Aula 3  Conceito de Grafo $G = \langle V, A \rangle $  Representação   - Diagrama  - Matrizes: adjacências  - Conjunto de pares ordenados  - Classes de objetos  Grafos representados por classes de objetos Grafos podem ser representados computacionalmente por objetos da classe `Grafo`:`Classe Grafo`  $\quad$ `vertices`: [Vertice]    $\quad$ `arestas`: [Aresta]<jupyter_code># Código inválido
class Aresta:
    v1
    v2
    def origem():
        return v1
class Aresta:
    def __init__(self, v1, v2, peso = 1):
        self.v1 = v1
        self.v2 = v2
        self.peso = peso
    def origem(self):
        return self.v1
    def mpeso(self):
        return self.peso

# class Vertice:

# class Grafo:

a1 = Aresta("XXX", "YYY", 17)
# Acesso inadequado: uso direto de atributos do objeto
a1.mpeso()
# Acesso adequado: uso de funções
a1.origem()<jupyter_output><empty_output><jupyter_text>Exercício 1. Representar o grafo direcionado da figura 5.26, [JG] p 232.  Aula 4  1. Correção do exercício da aula anterior  <NAME><jupyter_code>class Vertice:
    def __init__(self, label):
        self._label = label
        
    def label(self):
        return self._label
    
    def __str__(self):
        return self._label
    
class Aresta:
    
    def __init__(self, v1, v2, peso = 0):
        self._v1 = v1
        self._v2 = v2
        self._peso = peso
        
    def origem(self):
        return self._v1
    
    def destino(self):
        return self._v2
    
    def peso(self):
        return self._peso
        
    def __str__(self):
        return self._v1.label() +' -> '+ self._v2.label()
    
class Grafo:
    
    def __init__(self):
        self._vertices = []
        self._arestas = []
        
    def __init__(self, vertices, arestas):
        self._vertices = vertices
        self._arestas = arestas
    
    def add_vertice(self, v):
        self._vertices.append(v)
        
    def add_aresta(self, a):
        self._arestas.append(a)
    
    def arestas(self):
        return self._arestas
    
    def vertices(self):
        return self._vertices
# Instanciando os vértices
vertices = [Vertice("1"), Vertice("2"), Vertice("3"), Vertice("4")]
v1 = vertices[0]
v2 = vertices[1]
v3 = vertices[2]
v4 = vertices[3]

# Instanciando as arestas com peso default
arestas = [Aresta(v1, v2),
           Aresta(v2, v2),
           Aresta(v2, v3),
           Aresta(v1, v3),
           Aresta(v3, v4),
           Aresta(v4, v3),
           Aresta(v1, v4)]

# Instanciando o grafo
grafo = Grafo(vertices, arestas)

# Imprimindo os vértices e arestas
print("-----------------Grafo--------------")
print("\nVertices")
for v in grafo.vertices():
    print(v) 

print("\nArestas")
for a in grafo.arestas():
    print(a)<jupyter_output>-----------------Grafo--------------

Vertices
1
2
3
4

Arestas
1 -> 2
2 -> 2
2 -> 3
1 -> 3
3 -> 4
4 -> 3
1 -> 4<jupyter_text><NAME><jupyter_code>class Vertice:
    def __init__(self, vert):
        self.vertice = vert
    
    def getVertice(self):
        return self.vertice

class Aresta:
    def __init__(self, vert_1, vert_2, peso=1):
        self.vert_1 = vert_1
        self.vert_2 = vert_2
        self.peso = peso
        
    def origem(self):
        return self.vert_1
    
    def extremidade(self):
        return self.vert_2
    
    def par(self):
        return (self.vert_1, self.vert_2)
    
    def peso(self):
        return self.peso
    
class Grafo:
    def __init__(self, arestas):
        self.arestas = arestas
        
    def arestas_grafo(self):
        return self.arestas
    
# Retorna as arestas na forma de tuplas dentro de uma lista   
vertices_arestas = lambda g: [i.par() for i in grafo_atividade.arestas_grafo()]

# Calcula vértices e arestas de um grafo
vertices_arestas_funcional = lambda g, lista: ([[[lista.append(i) for i in k if i not in lista] for k in g], len(lista)][-1], len(vertices_arestas(g)))
# ------------------------------- INSTANCIANDO
# Vértices
# Observação: usar a classe vértice para instanciar o grafo.
v_1 = "0"
v_2 = "1"
v_3 = "2"
v_4 = "3"

# Arestas
a_1 = Aresta(v_1, v_2)
a_2 = Aresta(v_2, v_2)
a_3 = Aresta(v_2, v_3)
a_4 = Aresta(v_1, v_3)
a_5 = Aresta(v_3, v_4)
a_6 = Aresta(v_4, v_3)
a_7 = Aresta(v_1, v_4)

# Lista contendo as arestas
arestas_grafo = [a_1, a_2, a_3, a_4, a_5, a_6, a_7]

# Grafo
grafo_atividade = Grafo(arestas_grafo)

# ------------------------------- FIM DA CRIAÇÂO DOS OBJETOS
# Chamando as arestas do grafo
print("GRAFO")
print(vertices_arestas(grafo_atividade))
print("\n")

print('VÉRTICES E ARESTAS')
# Chamando os vértices e arestas do grafo: Resultado = 4 arestas e 7 vértices
print(vertices_arestas_funcional(vertices_arestas(grafo_atividade), []))<jupyter_output>GRAFO
[('0', '1'), ('1', '1'), ('1', '2'), ('0', '2'), ('2', '3'), ('3', '2'), ('0', '3')]


VÉRTICES E ARESTAS
(4, 7)
{'fraction_non_alphanumeric': 0.14617044228694714, 'fraction_numerical': 0.03708198489751888, 'mean_word_length': 2.981213097155126, 'pattern_counts': {'":': 0, '<': 40, '<?xml version=': 0, '>': 48, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '94051', 'license': 'MIT', 'n_tokens_mistral': 3075, 'n_tokens_neox': 2983, 'n_words': 737, 'path': 'python/.ipynb_checkpoints/GrafosAulas2020(1)-checkpoint.ipynb', 'repo_name': 'allanvobraun/NotebooksGrafosPucpr', 'size': '7462'}