Skip to content

Instantly share code, notes, and snippets.

@codecademydev

codecademydev/Graph.js Secret

Created August 17, 2023 17:49
Show Gist options
  • Save codecademydev/164dac4edfbac2f59d743cd97fee63a2 to your computer and use it in GitHub Desktop.
Save codecademydev/164dac4edfbac2f59d743cd97fee63a2 to your computer and use it in GitHub Desktop.
Download ZIP
Codecademy export
Raw
breadthFirstTraversal.js
const testGraph = require('./testGraph.js');
const Queue = require('./Queue.js');
const breadthFirstTraversal = (start) => {
const visitedVertices = [start];
const visitQueue = new Queue();
visitQueue.enqueue(start);
while (!visitQueue.isEmpty()) {
const current = visitQueue.dequeue();
console.log(current.data);
current.edges.forEach((edge) => {
const neighbor = edge.end;
if (!visitedVertices.includes(neighbor)) {
visitedVertices.push(neighbor);
visitQueue.enqueue(neighbor);
}
})
}
};
breadthFirstTraversal(testGraph.vertices[0]);
Raw
Graph.js
class Graph {
constructor(isDirected = false, isWeighted = false) {
this.vertices = [];
this.isDirected = isDirected;
this.isWeighted = isWeighted;
}
addVertex(data) {
const newVertex = new Vertex(data);
this.vertices.push(newVertex);
return newVertex;
}
removeVertex(vertex) {
this.vertices = this.vertices.filter(v => v !== vertex);
}
addEdge(vertexOne, vertexTwo, weight) {
const edgeWeight = this.isWeighted ? weight : null;
if (vertexOne instanceof Vertex && vertexTwo instanceof Vertex) {
vertexOne.addEdge(vertexTwo, edgeWeight);
if (!this.isDirected) {
vertexTwo.addEdge(vertexOne, edgeWeight);
}
} else {
throw new Error('Expected Vertex arguments.');
}
}
removeEdge(vertexOne, vertexTwo) {
if (vertexOne instanceof Vertex && vertexTwo instanceof Vertex) {
vertexOne.removeEdge(vertexTwo);
if (!this.isDirected) {
vertexTwo.removeEdge(vertexOne);
}
} else {
throw new Error('Expected Vertex arguments.');
}
}
getVertexByValue(value) {
return this.vertices.find(vertex => vertex.data === value);
}
print() {
const vertexList = this.vertices;
vertexList.forEach(vertex => vertex.print());
}
}
class Vertex {
constructor(data) {
this.data = data;
this.edges = [];
}
addEdge(vertex, weight) {
if (vertex instanceof Vertex) {
this.edges.push(new Edge(this, vertex, weight));
} else {
throw new Error('Edge start and end must both be Vertex');
}
}
removeEdge(vertex) {
this.edges = this.edges.filter(edge => edge.end !== vertex);
}
print() {
const edgeList = this.edges.map(edge =>
edge.weight !== null ? `${edge.end.data} (${edge.weight})` : edge.end.data) || [];
const output = `${this.data} --> ${edgeList.join(', ')}`;
console.log(output);
}
}
class Edge {
constructor(start, end, weight = null) {
this.start = start;
this.end = end;
this.weight = weight;
}
}
module.exports = {
Graph,
Vertex,
Edge,
};
Raw
LinkedList.js
const Node = require('./Node');
class LinkedList {
constructor() {
this.head = null;
}
addToHead(data) {
const newHead = new Node(data);
const currentHead = this.head;
this.head = newHead;
if (currentHead) {
this.head.setNextNode(currentHead);
}
}
addToTail(data) {
let tail = this.head;
if (!tail) {
this.head = new Node(data);
} else {
while (tail.getNextNode() !== null) {
tail = tail.getNextNode();
}
tail.setNextNode(new Node(data));
}
}
removeHead() {
const removedHead = this.head;
if (!removedHead) {
return;
}
this.head = removedHead.getNextNode();
return removedHead.data;
}
printList() {
let currentNode = this.head;
let output = '<head> ';
while (currentNode !== null) {
output += currentNode.data + ' ';
currentNode = currentNode.next;
}
output += `<tail>`;
console.log(output);
}
findNodeIteratively(data) {
let currentNode = this.head;
while (currentNode !== null) {
if (currentNode.data === data) {
return currentNode;
}
currentNode = currentNode.next;
}
return null;
}
findNodeRecursively(data, currentNode = this.head) {
if (currentNode === null) {
return null;
} else if (currentNode.data === data) {
return currentNode;
} else {
return this.findNodeRecursively(data, currentNode.next);
}
}
}
module.exports = LinkedList;
Raw
Node.js
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
setNextNode(node) {
if (!(node instanceof Node)) {
throw new Error('Next node must be a member of the Node class');
}
this.next = node;
}
setNext(data) {
this.next = data;
}
getNextNode() {
return this.next;
}
}
module.exports = Node;
Raw
Queue.js
const LinkedList = require('./LinkedList');
class Queue {
constructor(maxSize = Infinity) {
this.queue = new LinkedList();
this.maxSize = maxSize;
this.size = 0;
}
hasRoom() {
return this.size < this.maxSize;
}
isEmpty() {
return this.size === 0;
}
enqueue(data) {
if (this.hasRoom()) {
this.queue.addToTail(data);
this.size++;
} else {
throw new Error('Queue is full!');
}
}
dequeue() {
if (!this.isEmpty()) {
const data = this.queue.removeHead();
this.size--;
return data;
} else {
throw new Error('Queue is empty!');
}
}
}
module.exports = Queue;
Raw
testGraph.js
const { Graph } = require('./Graph.js');
const simpleGraph = new Graph(true, false);
const startNode = simpleGraph.addVertex('v0.0.0');
const v1 = simpleGraph.addVertex('v1.0.0');
const v2 = simpleGraph.addVertex('v2.0.0');
const v11 = simpleGraph.addVertex('v1.1.0');
const v12 = simpleGraph.addVertex('v1.2.0');
const v21 = simpleGraph.addVertex('v2.1.0');
const v111 = simpleGraph.addVertex('v1.1.1');
const v112 = simpleGraph.addVertex('v1.1.2');
const v121 = simpleGraph.addVertex('v1.2.1');
const v211 = simpleGraph.addVertex('v2.1.1');
simpleGraph.addEdge(startNode, v1);
simpleGraph.addEdge(startNode, v2);
simpleGraph.addEdge(v1, v11);
simpleGraph.addEdge(v1, v12);
simpleGraph.addEdge(v2, v21);
simpleGraph.addEdge(v11, v111);
simpleGraph.addEdge(v11, v112);
simpleGraph.addEdge(v12, v121);
simpleGraph.addEdge(v21, v211);
module.exports = simpleGraph
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment