A√ļn no tienes acceso a esta clase

Crea una cuenta y contin√ļa viendo este curso

Construyendo un grafo

24/25
Recursos

Aportes 22

Preguntas 2

Ordenar por:

¬ŅQuieres ver m√°s aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesi√≥n.

Hace ya un buen tiempo hice un curso de estructuras de datos en Python, y en unos de los ejercicios nos daban un grafo, en el cual nos pedían crear tres funciones las cuales retornaran un edge list, un adjacency list y un adjacency matrix. Me tomé el tiempo de pasar el código de Python a JS, aquí lo dejo

class Node{
    constructor(value){
        this.value = value
        this.edges = []
    }
}
        
class Edge{
    constructor(nodeFrom, nodeTo){
        this.nodeFrom = nodeFrom
        this.nodeTo = nodeTo
    }
}

class Graph{
    constructor(nodes = [], edges = []){
        this.nodes = nodes
        this.edges = edges
    }
    insertNode(value){
        this.nodes.push(new Node(value))
    }
    insertEdge(fromValue, toValue){
        let fromFound = null
        let toFound = null

        this.nodes.forEach(node=>{
            if(fromValue === node.value){
                fromFound = node
            }
            if(toValue === node.value){
                toFound = node
            }
        })

        if(!fromFound){
            fromFound = new Node(fromValue)
            this.nodes.push(fromFound)
        }
        if(!toFound){
            toFound = new Node(toValue)
            this.nodes.push(toFound)
        }
        const newEdge = new Edge(fromFound, toFound)
        fromFound.edges.push(newEdge)
        toFound.edges.push(newEdge)
        this.edges.push(newEdge)
    }
    getEdgeList(){
        const edgeList = []
        for(let edge of this.edges){
            edgeList.push([edge.nodeFrom.value, edge.nodeTo.value])
        }
        return edgeList
    }
    getAdjacencyList(){
        const maxIndex = this.edges.length
        // Create a list with maxIndex +1 elements, all null
        const adjacencyList = Array.from(new Array(maxIndex+1), x => null)

        for(let edge of this.edges){
            if(adjacencyList[edge.nodeFrom.value]){
                adjacencyList[edge.nodeFrom.value].push(edge.nodeTo.value)
            }
            else{
                adjacencyList[edge.nodeFrom.value] = [edge.nodeTo.value]
            }
        }
        return adjacencyList
    }
    getAdjacencyMatrix(){
        const len = this.nodes.length + 1
        //Create a matrix of dimensions len x len, filled with zeros 
        const adjacencyMatrix = Array.from(new Array(len), x => new Array(len).fill(0))
        for(let edge of this.edges){
            adjacencyMatrix[edge.nodeFrom.value][edge.nodeTo.value] = 1
        }
        return adjacencyMatrix
    }
}
const graph = new Graph()
graph.insertEdge(1,2)
graph.insertEdge(1,3)
graph.insertEdge(1,4)
graph.insertEdge(3,4)

// Should be [[1, 2], [1, 3], [1, 4], [3, 4]]
console.log(graph.getEdgeList())
// Should be [ null, [ 2, 3, 4 ], null, [ 4 ], null ]
console.log(graph.getAdjacencyList())
// Should be [[0,0,0,0,0],[0,0,1,1,1],[0,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0]]
console.log(graph.getAdjacencyMatrix())

El grafo de tipo adjancentList lo que haces es, como vimos, generar una lista de a quiénes conoce tal nodo.
.
Lo genial de este grafo es que si t√ļ necesitas saber qu√© otros nodos est√°n conectados a alg√ļn nodo espec√≠fico simplemente tienes que obtener el √≠ndice que contiene a dicho nodo y eso te devolver√° a los nodos con los cuales este se conecta ūüĎÄ

lo entendí, pero no supe para que me sirve eso, toca seguir investigando los grafos, buen curso cositas avanzadas para mí, pero no sabría donde poner en practica

Dejó el código con las líneas para insertar datos:

class Grafo {
    constructor() {
        this.nodos = 0;
        this.Adylist = {};
    }

    // Add Vértice/Nodo
    addVertice(valor){
        this.Adylist[valor] = [];
        this.nodos++;
    }

    // Add Conexión/Edge
    addConex(nodo1, nodo2){
        // Conexión entre gragos
        this.Adylist[nodo1].push(nodo2);
        this.Adylist[nodo2].push(nodo1);
    }
}

const Graph = new Grafo();

// Vértices
Graph.addVertice(1);
Graph.addVertice(3);
Graph.addVertice(4);
Graph.addVertice(5);
Graph.addVertice(6);
Graph.addVertice(8);

// Conexiones
Graph.addConex(8,4)
Graph.addConex(4,1)
Graph.addConex(1,3)
Graph.addConex(1,6)
Graph.addConex(3,6)
Graph.addConex(3,5)
Graph.addConex(5,4)

/**
    // RESULTADO:
    1: (3) [4, 3, 6]
    3: (3) [1, 6, 5]
    4: (3) [8, 1, 5]
    5: (2) [3, 4]
    6: (2) [1, 3]
    8: [4] 
 */

Para hacerlo dirigido imagino que es no hacer push en ambos sino solo en el camino ( 1 -> 2 solo hacer push a nodo1 )

Me encanto el tema, quisiera aprender a utilizarlos digamos en backend, por ejemplo si creo una mini red social cómo conectar a los usuarios que se agreguen (No Dirigido) y así. Me parece muy interesante de aplicar. Excelente curso 10/10

Increíble la manera que tiene De Granda de explicar todo de una manera super entendible ^^

Vaya fumada como generó el grafo, de locos!!!

Hice una clase de utilidad para crear un diccionario que cuando una propiedad se acceda y esta no exista, entonces cree autom√°ticamente la entrada con un array.

class DefaultArrayDict {
  constructor() {
    return new Proxy(
      {},
      {
        get: (target, name) => {
          if (!(name in target)) {
            target[name] = [];
          }

          return target[name];
        },
      }
    );
  }
}

class Graph {
  constructor() {
    this.nodes = 0;
    this.adjacentList = new DefaultArrayDict();
  }

  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2);
    this.adjacentList[node2].push(node1);
  }
}

const myGraph = new Graph();

De esta forma me ahorro la función llamada addVertex.

Código del ejercicio
Incluye los vértices y bordes.
.

class Graph {
  constructor() {
    this.nodes = 0;
    this.adjacentList = {};
  }

  /** Adicionar un Vertice */
  addVertex(node) {
    this.adjacentList[node] = [];
    this.nodes++;
  }

  /** Adicionar un Borde */
  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2);
    this.adjacentList[node2].push(node1);
  }
}

const myGraph = new Graph();
// Vertices
myGraph.addVertex('1');
myGraph.addVertex('3');
myGraph.addVertex('4');
myGraph.addVertex('5');
myGraph.addVertex('6');
myGraph.addVertex('8');
// Bordes
myGraph.addEdge('1', '6');
myGraph.addEdge('1', '4');
myGraph.addEdge('1', '3');
myGraph.addEdge('3', '5');
myGraph.addEdge('3', '6');
myGraph.addEdge('4', '5');
myGraph.addEdge('4', '8');

Código para la construcción de un Grafo no direccionado utilizando una Matriz adyacente.

class Graph {
  constructor() {
    this.nodes = 0;
    this.adjacentMatrix = {};
  }
  addVertex(node) {
    if (this.adjacentMatrix[node]) {
      return new Error("Existing vertex"); 
    }
    this.adjacentMatrix[node] = [];
    const adjacentMatrixLength = Object.keys(this.adjacentMatrix).length;
    for (let key in this.adjacentMatrix){
      for (let i = 0; i < adjacentMatrixLength; i++) {
        if (this.adjacentMatrix[key].length !== adjacentMatrixLength) {
          this.adjacentMatrix[key].push("0");
        }
      }
    }
    this.nodes++;
    return this;
  }
  addEdge(node1, node2) {
    if (!this.adjacentMatrix[node1] || !this.adjacentMatrix[node2]) {
      return new Error("One of the vertices entered doesn't exist");
    }
    const adjacentMatrixKeys = Object.keys(this.adjacentMatrix);
    for (let i = 0; i < this.nodes; i++) {
      if (adjacentMatrixKeys[i] == node1) {
        this.adjacentMatrix[node2][i] = "1";
      }
      if (adjacentMatrixKeys[i] == node2) {
        this.adjacentMatrix[node1][i] = "1";
      }
    }
    return this;
  }
}

const myGraph = new Graph();
ūü§© Excelente clase, hace que se vea f√°cil y entendible.

para hacer un dirijo podria ser igual al que tenemos de esta clase pero cambiando la clase del edge por algo asi

make_conection(from, to){
    this.adjacentList[from].push(to)
  }

Les comparto mi implementación del código de la clase usando JSDocs:

/*
 * A graph can be represent in many ways, let suppose we have the following graph:
 * 2 - 0
 * | \
 * |  \
 * 1 - 3
 * 
 * we can represent it as:
 * 1. Edge list:
 *    const graph = [
 *      [0, 2],
 *      [1, 2],
 *      [1, 3],
 *      [2, 3]
 *    ]
 * 
 * 2. Adjacent list
 *    - with arrays:
 *       const graph = [[2], [2, 3], [0, 1, 3], [1, 2]]
 *   - with an object:
 *       const graph = {
 *         0: [2],
 *         1: [2, 3],
 *         2: [0, 1, 3],
 *         3: [1, 2]
 *       }
 * 
 * 3. Adjacent matrix:
 *   - with arrays:
 *       const graph = [
 *         [0, 0, 1, 0],
 *         [0, 0, 1, 1],
 *         [1, 1, 0, 1],
 *         [0, 1, 1, 0],
 *       ]
 *   - with an object:
 *       const graph = {
 *         0: [0, 0, 1, 0],
 *         1: [0, 0, 1, 1],
 *         2: [1, 1, 0, 1],
 *         3: [0, 1, 1, 0],
 *       }
 */

class Graph {
  constructor() {
    /**
     * @type {Number} number of nodes from the graph
     * @public
     */
    this.nodes = 0
    /**
     * @type {Object<number, [number]>} an object which every key is a node and each value is an array of nodes to which this node is connected
     * @public
     */
    this.adjacentList = {}
  }

  /**
   * @param {Number} value node of the Graph
   */
  addVertex(value) {
    this.adjacentList[value] = []
    this.nodes++
  }

  /**
   * @param {Number} node1 
   * @param {Number} node2 
   */
  addEdges(node1, node2) {
    this.adjacentList[node1].push(node2)
    this.adjacentList[node2].push(node1)
  }
}

Parecía el mas difícil de hacer y resultó ser el mas sencillo jaja

A√Īad√≠ la comprobaci√≥n de si existen los nodos antes de a√Īadir la conexi√≥n entre ambos y en caso de que uno de ellos no exista se a√Īade autom√°ticamente.

addLink( node1, node2 ) {

    if( !(node1 in this.adjList) ) 
        this.addVertex( node1 )
    if( !(node2 in this.adjList) )
        this.addVertex( node2 )

    this.adjList[node1].push(node2)
    this.adjList[node2].push(node1)
    
    return this

}

Mi nueva version de grafos ipo AdjacentList con algunas mejoras para evitar redundancia de validaciones:
p.s. permite agragar edges individuales o multiples si se envía un array XD:

class AdjacentList {
  constructor() {
    this.graph = {}
    this.length = 0
  }
  addVertex(value) {
    if (!this.graph[value]) {
      this.graph[value] = []
      this.length++
    }
    return this
  }
  addEdge(vertex, edges) {
    if (this.graph[vertex]) {
      if (!Array.isArray(edges)) {
        edges = [edges]
      }
      edges.forEach(edge => {
        if (this.graph[edge]) {
          const existEdge = this.graph[vertex]
            .find(ele => ele == edge)
          if (existEdge == undefined) {
            this.graph[vertex].push(edge)
            this.graph[edge].push(vertex)
          }
        }
      })
    }
    return this
  }
}

const myGraph = new AdjacentList()
myGraph.addVertex(1)
myGraph.addVertex(3)
myGraph.addVertex(4)
myGraph.addVertex(5)
myGraph.addVertex(6)
myGraph.addVertex(8)
myGraph.addEdge(8,4)
myGraph.addEdge(4, [1,5,8])
myGraph.addEdge(1, [4,3,6])
myGraph.addEdge(6, [1,3])
myGraph.addEdge(5, [4,3])

Es increible eel derrame cerebral que me da cada que acabo una clase

Listo! ya terminé tanto el de la clase, como uno grafo dirigido ponderado que hice por mi cuenta c:

.
.


// const graph = {
//   1: [4, 3, 6],
//   3: [5, 1, 6],
//   4: [8, 1, 5],
//   5: [4, 3],
//   6: [1, 3],
//   8: [4]
// }

//----------------------------------------------------------------->>>
//GRAFO DE LA CLASE - NO DIRIGIDOS - NO PONDERADO

class graph {
  constructor() {
    this.nodes = 0;
    this.adjacentList = {};
  }
  addVertex(node) {
    this.adjacentList[node] = []
    this.nodes++
  }
  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2);
    this.adjacentList[node2].push(node1); 
  }

}

const newGraph = new graph();

newGraph.addVertex(1);
newGraph.addVertex(3);
newGraph.addVertex(4);
newGraph.addVertex(5);
newGraph.addVertex(6);
newGraph.addVertex(8);
// newGraph.addVertex(7);
// newGraph.addVertex(8);
// newGraph.addVertex(9);
// newGraph.addVertex(10);

newGraph.addEdge(1,6)
newGraph.addEdge(6,3)
newGraph.addEdge(1,3)
newGraph.addEdge(1,4)
newGraph.addEdge(3,5)
newGraph.addEdge(4,5)
newGraph.addEdge(8,4)

//----------------------------------------------------------------->>>
//GRAFO - DIRIGIDOS - PONDERADO

class graphD {
  constructor() {
    this.nodes = 0;
    this.adjacentList = {};
  }
  addVertex(node) {
    this.adjacentList[node] = [];
    this.nodes++
  }

  // Cost es el ponderado, me pareció mejor imaginarlo cómo el costo de un viaje
  // cómo dijo el profesor
  addEdge(from, to, Cost) {
    let algo
    if(from == Number || to == Number || from <= this.nodes || to <= this.nodes || from >= 0 || to >= 0) {
      this.adjacentList[from][0] = {'NameRoute':`${from} --> ${to}`,'Cost':Cost};
      
      this.adjacentList[from][0].Route = this.adjacentList[to];
      return this
    }

  } 
  
}

const graphd = new graphD();

graphd.addVertex(1);
graphd.addVertex(3);
graphd.addVertex(4);
graphd.addVertex(5);
graphd.addVertex(6);
graphd.addVertex(8);

graphd.addEdge(1,6,2)
graphd.addEdge(6,3,5)
graphd.addEdge(1,3,6)
graphd.addEdge(1,4,1)
graphd.addEdge(3,5,7)
graphd.addEdge(4,5,6)
graphd.addEdge(8,4,9)

Aqu√≠ una peque√Īa l√≥gica para evitar conexiones repetidas en el grafo:

addEdge(node1, node2) {
    this.#checkAndAddEdge(this.adjacentList[node1],node2);
    this.#checkAndAddEdge(this.adjacentList[node2],node1);
    
    return this;
}
#checkAndAddEdge(list, node) {
    for (let i = 0; i < list.length; i++) {
        if (list[i] == node) {
            return false;
        }
    }
    list.push(node);
    return true;
}

Esta interesante esta forma de crear un grafo, pero aun no estoy muy seguro como se podría recorrer. Seguiré estudiando el código, pero mientras aquí dejo mi aporte:

class Graph{
  constructor(){
    this.nodes = 0;
    this.edgesAdjList = {};
  }
  addVertex(node) {
    this.edgesAdjList[node] = [];
    this.nodes++;
  }
  insert(node1, node2){
   //Si el node1 o node2 no existen, entonces se crean
    if (!this.edgesAdjList[node1]) this.addVertex(node1); 
    if (!this.edgesAdjList[node2]) this.addVertex(node2);

    this.edgesAdjList[node1].push(node2);
    this.edgesAdjList[node2].push(node1);
  }
}
const myGraph = new Graph();

Tengo un problema y es que quiero evitar que se creen nodos sin conexiones, pero no en encuentro una forma correcta de ocultar la funci√≥n addVertex() . ¬ŅAlg√ļn consejo?

hice el ejercicio con adjacent matrix, dejo mi peque√Īo aporte

addVertex(node) {
        this.adjacentList[node] = [];
        this.keys.push(node);
        this.adjacentMatrix[node] = [];
        for (let i = 0; i < this.keys.length; i++) {
            this.adjacentMatrix[this.keys[i]] = new Array((this.nodes + 1)).fill('0');
        }
        this.nodes++;
    }
    addMatrix(node1, node2) {
        const index1 = this.keys.indexOf(node1);
        const index2 = this.keys.indexOf(node2);
        this.adjacentMatrix[node1][index1] = '1';
        this.adjacentMatrix[node1][index2] = '1';
        this.adjacentMatrix[node2][index1] = '1';
        this.adjacentMatrix[node2][index2] = '1';
    }

ūüĎĆ