Converting Edge List to Adjancency List

In graph theory, especially when dealing with undirected graphs, using an edge list as input is common.

An edge list is a straightforward way to represent a graph using an array of arrays. Each subarray contains a pair of vertices that are connected by an edge. For example, consider the following graph:

The edge list representation of this graph would be:

[
  [1, 2],
  [1, 3],
  [2, 4],
  [3, 4],
  [3, 5],
  [5, 6],
];

This list tells us that there are edges between the following pairs of vertices:

• Vertex 1 and Vertex 2
• Vertex 1 and Vertex 3
• Vertex 2 and Vertex 4
• Vertex 3 and Vertex 4
• Vertex 3 and Vertex 5
• Vertex 5 and Vertex 6

While an edge list is straightforward, it is often more convenient to work with an adjacency list for various graph algorithms, as it makes it easier to traverse the graph, find neighbors of a node, and perform other graph operations efficiently. Let's look at how we can convert an edge list into an adjacency list.

---

Algorithm

• Iterate through the nested array of edges. For each edge (two-element subarray):
  • Extract the two connected vertices; we'll call them vertex A and vertex B.
  • If vertex A is not a key in the adjacency list, add it as a key with an empty list as its value.
  • Push vertex B into the value list of vertex A.
  • If vertex B is not a key in the adjacency list, add it as a key with an empty list as its value.
  • Push vertex A into the value list of vertex B.

Note that we must add both directions of each edge into our adjacency list because we're working with an undirected graph. We need to be able to use our adjacency list to move along edges in both directions.

---

Walkthrough

Let's do a quick walkthrough for the edge list [[1, 2], [2, 3], [3, 1]]. The graph represented by this list would look like this:

Step 1: In the first iteration, the subarray is [1, 2].

• The first element is 1. Since it's not a key in the adjacency list, we add it as a key with the value []. Next, we add the other element, 2, to the value array associated with 1.

• The second element is 2. Since it's not a key in the adjacency list, we add it as a key with the value []. Next, we add the other element, 1, to the value array associated with 2.

Step 2: In the second iteration, the subarray is [2, 3].

• The first element is 2. Since it's already a key in the adjacency list, we only need to add the other element, 3, to the value array of element 2.

• The second element is 3. Since it's not a key in the adjacency list, we add it as a key with the value []. Next, we add the other element, 2, to the value array of 3.

Step 3: In the third and final iteration, the subarray is [3, 1].

• The first element is 3. Since it's already a key in the adjacency list, we add the other element, 1, to the value array of element 3.

• The second element is 1. Since it's also present as a key in the adjacency list, we add the other element, 3, to the value array of element 1.

---

Implementation

Finally, let's see the code implementation:

function createAdjList(edgeList) {
  const adjList = new Map();

  edgeList.forEach(([vertex1, vertex2]) => {
    if (!adjList.has(vertex1)) adjList.set(vertex1, []);
    adjList.get(vertex1).push(vertex2);

    if (!adjList.has(vertex2)) adjList.set(vertex2, []);
    adjList.get(vertex2).push(vertex1);
  });
  return adjList;
}

// Helper Function
function printAdjList(adjList) {
  console.log(
    "{\n" +
      Array.from(
        adjList,
        ([key, value]) => `  ${key}: [${value.join(", ")}]`
      ).join(",\n") +
      "\n}"
  );
}

const edgeList1 = [
  [1, 2],
  [2, 3],
  [3, 1],
];

const adjList1 = createAdjList(edgeList1);
printAdjList(adjList1);
// {
//   1: [2, 3],
//   2: [1, 3],
//   3: [2, 1]
// }

const edgeList2 = [
  [1, 2],
  [1, 3],
  [2, 4],
  [3, 4],
  [3, 5],
  [5, 6],
];

const adjList2 = createAdjList(edgeList2);
printAdjList(adjList2);
// {
//  1: [2, 3],
//  2: [1, 4],
//  3: [1, 4, 5],
//  4: [2, 3],
//  5: [3, 6],
//  6: [5]
// }