30:T6fb,class MatrizAdjacencia { constructor(vertices) { // Construtor recebe o array de vértices do grafo this._vertices = vertices; this._matriz = [[]]; this.redimensiona_matriz(); } get qtdVertices () { // Número de vértices return this._vertices.length; } redimensiona_matriz() { // Assegura que matriz tem mesmo tamanho que o array de vértices let m = this._matriz.length; let n = this._vertices.length; if (m==n) return; // Acrescenta novas colunas for (let i = 0; i < m; i++) { for (let j = m; j < n; j++) { this._matriz[i][j] = 0; } } // Acrescenta novas linhas for (let i = m; i < n; i++) { this._matriz[i] = []; for (let j = 0; j < n; j++) { this._matriz[i][j] = 0; } } } adicionarArestaDir (indiceVerticeInicial,indiceVerticeFinal,valorCelula = 1) { // Acrescenta aresta de grafo direcionado this.redimensiona_matriz(); this._matriz[indiceVerticeInicial][indiceVerticeFinal] = valorCelula; this._vertices [indiceVerticeFinal].incrementaGrau(); } adicionarAresta (indiceVerticeInicial,indiceVerticeFinal,valorCelula = 1) { // Acrescenta aresta de grafo não direcionado this.adicionarArestaDir (indiceVerticeInicial,indiceVerticeFinal,valorCelula); this.adicionarArestaDir (indiceVerticeFinal,indiceVerticeInicial,valorCelula); } peso (i,j) { // Retorna o peso da aresta de i para j. Zero se não estão conectados return this._matriz[i][j]; } * indicesVerticesAdjacentes (indiceVertice) { // Gera todos os índices de vértices adjacentes a indiceVertice this.redimensiona_matriz(); for (let i = 0; i < this.qtdVertices; i++) { if (this._matriz[indiceVertice][i] > 0) yield i; } } } 31:T741,class Grafo { constructor () { this._vertices = []; this._matrizAdjacencia = new MatrizAdjacencia(this._vertices); this._mapaRotulos = new Map(); } adicionarVertice (rotulo) { if (this._mapaRotulos.has(rotulo)) throw "Vertice com rotulo "+rotulo+" já existe"; let indice = this._vertices.length; this._vertices.push(new Vertice(rotulo)); this._mapaRotulos.set(rotulo,indice); } indiceVertice (rotulo) { if (!this._mapaRotulos.has(rotulo)) throw "Grafo não tem vértice com rótulo "+rotulo; return this._mapaRotulos.get(rotulo); } conectarVertices (rotuloVerticeInicial, rotuloVerticeFinal) { let i = this.indiceVertice(rotuloVerticeInicial); let j = this.indiceVertice(rotuloVerticeFinal); this._matrizAdjacencia.adicionarAresta (i,j); } imprimir () { for (let i = 0; i < this._vertices.length; i++) { let v = this._vertices[i]; v.imprimir(); for (let j of this._matrizAdjacencia.indicesVerticesAdjacentes(i)) { let u = this._vertices[j]; imprime("conectado a "); u.imprimir(); } } } *vertices () { for (let v of this._vertices) yield v.rotulo; } *verticesAdjacentes (rotulo) { for (let j of this._matrizAdjacencia.indicesVerticesAdjacentes(this.indiceVertice(rotulo))) { yield this._vertices [j].rotulo } } graphViz () { // Gera especificação graphViz para este grafo let d = 'graph {'; for (let i = 0; i < this._vertices.length; i++) { let v = this._vertices[i]; let count = 0; for (let j of this._matrizAdjacencia.indicesVerticesAdjacentes(i)) { if (i < j) { let u = this._vertices[j]; d += v.rotulo+" -- "+ u.rotulo + ";"; count++; } } if (count == 0) d += v.rotulo + ";"; } return d + "}"; } }32:T4ba,grafo = { let grafo = new Grafo(); imprime ("Segunda aplicação\n"); grafo.adicionarVertice("RJ"); grafo.adicionarVertice("SP"); grafo.adicionarVertice("BH"); grafo.adicionarVertice("PT"); grafo.adicionarVertice("OS"); grafo.adicionarVertice("SV"); grafo.adicionarVertice("CR"); grafo.adicionarVertice("PA"); grafo.conectarVertices("RJ","SP"); grafo.conectarVertices("RJ","BH"); grafo.conectarVertices("RJ","PT"); grafo.conectarVertices("RJ","PA"); //grafo.conectarVertices("SP","RJ"); grafo.conectarVertices("SP","BH"); grafo.conectarVertices("SP","OS"); grafo.conectarVertices("SP","SV"); grafo.conectarVertices("SP","CR"); grafo.conectarVertices("SP","PA"); //grafo.conectarVertices("BH","RJ"); //grafo.conectarVertices("BH","SP"); //grafo.conectarVertices("PT","RJ"); //grafo.conectarVertices("OS","SP"); //grafo.conectarVertices("SV","SP"); grafo.conectarVertices("SV","PA"); //grafo.conectarVertices("CR","SP"); grafo.conectarVertices("CR","PA"); //grafo.conectarVertices("PA","RJ"); //grafo.conectarVertices("PA","SP"); //grafo.conectarVertices("PA","SV"); //grafo.conectarVertices("PA","CR"); grafo.imprimir(); return grafo }33:[] 2e:{"title":"Grafos - Capítulo 3","cells":[{"id":0,"value":"md`# Grafos - Capítulo 3\n\nEste caderno de notas contém código adaptado do livro sobre grafos de João Paulo Maida. Procurei adaptar\nas classes e construções do livro para a linguagem JavaScript de forma a facilitar a expressão dos algoritmos \ne estruturas de dados.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"md`## Capítulo 3`","pinned":false,"hidden":false,"mode":"ojs"},{"id":64,"value":"md`Esta é a classe **MatrizAdjacencia**`","pinned":false,"hidden":false,"mode":"ojs"},{"id":67,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":4,"value":"md`Esta é a classe **Vertice**`","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"class Vertice { \n constructor (rotulo) {\n this._rotulo = rotulo;\n this._grau = 0;\n if (rotulo == undefined) throw \"rótulo indefinido\";\n if (rotulo.trim() == \"\") throw \"rótulo em branco\";\n }\n get grau () {\n return this._grau;\n }\n get rotulo () {\n return this._rotulo;\n }\n incrementaGrau () {\n this._grau++;\n }\n imprimir() {\n imprime (\"Vertice \"+this.rotulo+\" com grau \"+this.grau+\"\\n\")\n }\n}\n ","pinned":true,"hidden":false,"mode":"ojs"},{"id":16,"value":"md`Esta é a classe **Grafo**`","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":23,"value":"md`Segunda **Aplicação**`","pinned":false,"hidden":false,"mode":"ojs"},{"id":25,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":31,"value":"resultado = {\n let r = html`

`;\n r.append(html`

Resultado

`);\n let textarea = html``;\n r.append(textarea);\n let clear = html``;\n r.append(clear);\n clear.onclick = function() { textarea.value = \"\" }\n return r;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":40,"value":"imprime = function () {\n let textarea = resultado.getElementsByTagName(\"textarea\")[0];\n for (let arg of arguments) textarea.value += arg;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":98,"value":"md`### Desenho do grafo`","pinned":false,"hidden":false,"mode":"ojs"},{"id":110,"value":"dot`${grafo.graphViz()}`","pinned":true,"hidden":false,"mode":"ojs"},{"id":104,"value":"md`Importação da biblioteca **graphViz**` ","pinned":false,"hidden":false,"mode":"ojs"},{"id":102,"value":"dot = require(\"@observablehq/graphviz@0.2\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}