For parsing a graph language a peg parser like pegjs is easiest
and can be tested via the tools or website

GML looks like json and is well supported with open source tools
jgf is a json format graph language

At parsing the nodes+edges must be put in data structures

This can be in a matrix and/or linked list

• An adjacency matrix is like a table that uses 1 to signal that the nodes connect and zero to signal that they don't. This method is great to represent finite graphs
• Adjacency List is like a dictionary in which each node value is a list of all the nodes it connects to. This is a different method used to represent finite graphs which are faster and easier to work with.
• The incidence matrix is also like a table but instead of tracking whether two-node connects or not, it tracks the direction of the edges where 1 is for when it uses the edge to connect to others, -1 is for when an edge connects to it, and zero when it has no connection with that edge. This method is perfect when you have edges with direction and value(weight) which makes it perfect for representing maps and navigations systems

`class Graph {  #vertices = new Set();  #adjacentList = new Map();    get vertices() {    return Array.from(this.#vertices)  }    get adjacentList() {    const list = {};        this.#adjacentList.forEach((val, key) => {      list[key] = Array.from(val)    })        return list  }}add node`
`class Graph {  ...  addVertex(vertex = null) {    if(     !this.#vertices.has(vertex) &&     vertex !== null &&      vertex !== undefined    ) {      this.#vertices.add(vertex);      this.#adjacentList.set(vertex, new Set());    }  }}add edge`
`class Graph {   ...   addEdge(vertex1 = null, vertex2 = null, directed = true) {     if(       vertex1 !== null && vertex1 !== undefined &&       vertex2 !== null && vertex2 !== undefined &&        vertex1 != vertex2     ) {       this.addVertex(vertex1);       this.addVertex(vertex2);       this.#adjacentList.get(vertex1).add(vertex2);       if(directed) {         this.#adjacentList.get(vertex2).add(vertex1);       }     }   }}doing a bfsThe concept is simple, by default all nodes are green, when you check a node it becomes yellow and when you visit all its adjacent nodes it becomes redconst COLORS = Object.freeze({  GREEN: 'green',  YELLOW: 'yellow',  RED: 'red'})When you do a breadth-first search you check all its adjacent nodes and while you check you create a queue of nodes to check next`
`function breathFirstSearch(graph, fromVertex, callback) {  const {vertices, adjacentList} = graph;    if(vertices.length === 0) return;    const color = vertices      .reduce((c, v) => ({...c, [v]: COLORS.GREEN}), {});  const queue = [];    queue.push(fromVertex);    while(queue.length) {    const v = queue.shift();    const nearVertex = adjacentList[v];    color[v] = COLORS.YELLOW;        nearVertex.forEach(w => {      if(color[w] === COLORS.GREEN) {        color[v] = COLORS.YELLOW;        queue.push(w);      }    });        color[v] = COLORS.RED;        callback && callback(v);  }}the queue is to track which vertex to visit next and from start, the vertex provided is the first to be visited. Check the queue data structure article to learn how it works.While there is something in the queue we will shift the queue to grab the vertex at the front, grab its adjacent list of nodes, and color it yellow as we already checked its value. Each vertex looped over is queued to be visited next and we color them yellow as long as they are green.Since we checked all vertex adjacent lists, we can color it red since it is fully visited and call the callback with its value. By this point, we should have something in the queue and the process continues if so`
`t`

he depth-first search algorithm works a little differently. Instead of checking all adjacent list nodes before visiting the next node in the queue, it visits the node as soon as it checks it using a stack data structure to track which node to check next.

The same color concept is used here and the implementation is based on recursive function instead of a while loop used in the breadth-first search algorithm. It looks something like this:

`function depthFirstSearch(graph, fromVertex, callback) {  const {vertices, adjacentList} = graph;    if(vertices.length === 0) return;    const color = vertices     .reduce((c, v) => ({...c, [v]: COLORS.GREEN}), {});    callback && callback(fromVertex);  color[fromVertex] = COLORS.YELLOW;    function visit(v) {    if(color[v] === COLORS.GREEN) {      callback && callback(v);      color[v] = COLORS.YELLOW;      adjacentList[v].forEach(visit);    }    color[v] = COLORS.RED;  }    adjacentList[fromVertex].forEach(visit);}t`

he function takes the same arguments and does the same checks and color setup as the breadth-first search function. After coloring all nodes green, it calls the callback with the first vertex then proceeds to color it yellow as it is checked at this point.

It declares a visit recursive function which is called for each current vertex adjacent node. This visit function checks if the node is green — not checked or visited, calls the callback with it, colors it yellow then grabs its adjacent list and for each, it calls itself again.

It only gets to color the node-red after it is done checking all its adjacent list nodes and their adjacent list nodes and so on. It goes deep first before it is done with the node and that's why it is called a dept-first search algorithm.

```dfs is used to put nodes at level, at new outgoing edge put follow node at level+1class Graph {
#vertices = new Set();

get vertices() {
return Array.from(this.#vertices)
}

const list = {};

list[key] = Array.from(val)
})

return list
}

if(vertex !== null && vertex !== undefined) {
}
}

addEdge(vertex1 = null, vertex2 = null, directed = true) {
if(
vertex1 !== null && vertex1 !== undefined &&
vertex2 !== null && vertex2 !== undefined &&
vertex1 != vertex2
) {
}

}

if(directed) {
}
}
}

toString() {
let str = '';

str += `\${key} -> \${Array.from(val).join(', ')};\n`;
});

return str;
}
}

const COLORS = Object.freeze({
GREEN: 'green',
YELLOW: 'yellow',
RED: 'red'
});

function breathFirstSearch(graph, fromVertex, callback) {

if(vertices.length === 0) return;

const color = vertices.reduce((c, v) => ({...c, [v]: COLORS.GREEN}), {});
const queue = [];

queue.push(fromVertex);

while(queue.length) {
const v = queue.shift();
color[v] = COLORS.YELLOW;

nearVertex.forEach(w => {
if(color[w] === COLORS.GREEN) {
color[w] = COLORS.YELLOW;
queue.push(w);
}
});

color[v] = COLORS.RED;

callback && callback(v);
}
}

function depthFirstSearch(graph, fromVertex, callback) {

if(vertices.length === 0) return;

const color = vertices.reduce((c, v) => ({...c, [v]: COLORS.GREEN}), {});

callback && callback(fromVertex);
color[fromVertex] = COLORS.YELLOW;

function visit(v) {
if(color[v] === COLORS.GREEN) {
callback && callback(v);
color[v] = COLORS.YELLOW;