Implement a Graph Data Structure in JavaScript

Graphs are fundamental data structures used to model relationships between objects. They are widely applied in areas like social networks, navigation systems, and recommendation engines. This challenge focuses on implementing a versatile graph data structure in JavaScript, allowing you to represent and manipulate connections between nodes.

Problem Description

Your task is to create a Graph class in JavaScript that can represent both directed and undirected graphs. The graph should support adding nodes, adding edges between nodes, and retrieving information about the graph's structure.

Key Requirements:

1. Node Representation: Each node in the graph should be uniquely identifiable (e.g., by a string or number).
2. Edge Representation: Edges connect two nodes. For directed graphs, an edge goes from one node to another. For undirected graphs, an edge connects two nodes symmetrically.
3. Adjacency List: The graph should internally use an adjacency list representation. This means for each node, you should store a list of its adjacent nodes.
4. Methods: Implement the following methods for the Graph class:
   • addNode(node): Adds a new node to the graph. If the node already exists, it should do nothing.
   • addEdge(node1, node2, isDirected = false): Adds an edge between node1 and node2.
     • If isDirected is true, the edge is from node1 to node2.
     • If isDirected is false (default), the edge is undirected, meaning it goes both ways (node1 to node2 and node2 to node1).
     • If either node1 or node2 does not exist in the graph, they should be added first.
   • getNeighbors(node): Returns an array of nodes directly connected to the given node. If the node doesn't exist, return an empty array.
   • hasNode(node): Returns true if the node exists in the graph, false otherwise.
   • hasEdge(node1, node2): Returns true if an edge exists between node1 and node2 (considering direction for directed graphs). Returns false otherwise.
   • removeNode(node): Removes a node from the graph and all edges connected to it.
   • removeEdge(node1, node2, isDirected = false): Removes an edge between node1 and node2.
     • If isDirected is true, only the edge from node1 to node2 is removed.
     • If isDirected is false, both directions of the undirected edge are removed.

Expected Behavior:

• The graph should handle cases where nodes are added multiple times (idempotent).
• Edges should be added correctly for both directed and undirected scenarios.
• Retrieval of neighbors, existence of nodes, and edges should be accurate.
• Node and edge removal should be comprehensive.

Edge Cases to Consider:

• Adding edges to non-existent nodes.
• Retrieving neighbors for a non-existent node.
• Checking for edges that don't exist.
• Removing non-existent nodes or edges.
• Graphs with no nodes or edges.

Examples

Example 1: Undirected Graph

const graph = new Graph();
graph.addNode("A");
graph.addNode("B");
graph.addNode("C");
graph.addEdge("A", "B");
graph.addEdge("B", "C");

console.log(graph.getNeighbors("A")); // Output: ["B"]
console.log(graph.getNeighbors("B")); // Output: ["A", "C"]
console.log(graph.hasEdge("A", "B")); // Output: true
console.log(graph.hasEdge("B", "A")); // Output: true
console.log(graph.hasEdge("A", "C")); // Output: false

Explanation: An undirected graph is created. Node "A" is connected to "B", and "B" is connected to "C". getNeighbors("B") returns both "A" and "C" because the edges are bidirectional. hasEdge("A", "B") and hasEdge("B", "A") are both true.

Example 2: Directed Graph

const graph = new Graph();
graph.addNode("X");
graph.addNode("Y");
graph.addNode("Z");
graph.addEdge("X", "Y", true); // Directed edge from X to Y
graph.addEdge("Y", "Z", true); // Directed edge from Y to Z

console.log(graph.getNeighbors("X")); // Output: ["Y"]
console.log(graph.getNeighbors("Y")); // Output: ["Z"]
console.log(graph.hasEdge("X", "Y")); // Output: true
console.log(graph.hasEdge("Y", "X")); // Output: false (because it's a directed edge)

Explanation: A directed graph is created. There's an edge from "X" to "Y" and from "Y" to "Z". getNeighbors("Y") only returns "Z" because the edge is directed from "Y". hasEdge("Y", "X") is false as the edge direction is reversed.

Example 3: Node and Edge Removal

const graph = new Graph();
graph.addNode("P");
graph.addNode("Q");
graph.addNode("R");
graph.addEdge("P", "Q");
graph.addEdge("Q", "R");
graph.addEdge("P", "R", true); // Directed edge from P to R

console.log(graph.hasNode("Q")); // Output: true
console.log(graph.hasEdge("P", "Q")); // Output: true

graph.removeNode("Q");

console.log(graph.hasNode("Q")); // Output: false
console.log(graph.hasEdge("P", "Q")); // Output: false
console.log(graph.hasEdge("Q", "P")); // Output: false
console.log(graph.getNeighbors("R")); // Output: ["P"] (Edge between Q and R removed implicitly)

graph.removeEdge("P", "R", true);
console.log(graph.hasEdge("P", "R")); // Output: false

Explanation: Node "Q" is removed, which also removes all its incident edges. The directed edge from "P" to "R" is then explicitly removed.

Constraints

• Node identifiers will be strings or numbers.
• The graph can contain up to 1000 nodes.
• Each node can have up to 1000 neighbors.
• The number of edges can be up to 100,000.
• The implementation should aim for reasonable time complexity for common operations (e.g., adding/removing nodes/edges, getting neighbors).

Notes

• Consider using a JavaScript Map or an object to store the adjacency list, where keys are nodes and values are arrays (or Sets) of their neighbors.
• Think about how to efficiently handle undirected edges by storing them in both directions in the adjacency list.
• When removing a node, ensure you also remove it from the adjacency lists of all other nodes it was connected to.
• For getNeighbors, ensure it returns a copy of the neighbors list to prevent external modification of the internal graph state.