Hello $$$\mathfrak{Code}\color{blue}{\mathfrak{Forces}}$$$,

This blog assumes that you are already familiar with the basic concepts of Graph Theory.

First of all I'd like to thank my coach fegla who taught me those tricks and I'll try to share some of them with you. I think that there is no tutorial for this graph representation (at least no English tutorial, I've seen some Chinese coders using this representation). So, here we go!

I'd like to introduce this uncommon graph representation (I'm not sure if it has a proper name or not, but we used to call it adjacency edge list).

Let's say we have this directed graph: note that the numbers on edges are just the order of adding edges:

0 1
0 3
1 2
2 3
0 2
2 4
3 4

We will represent this graph using only two arrays/vectors:

int head[MAX_NODES]; the size of this array will be the maximum number of nodes, and the value for each node will represent the index of the latest added outgoing edge in the edges array.

edgeData edges[MAX_EDGES]; the size of this array will be the maximum number of edges, it contains all the needed data from the edge. and the edgeData must contain nxt which will point to the index of the next edge.

Let's see all the outgoing edges from node $$$0$$$, the indices of the edges in order are $$$[0, 1, 4]$$$. initially head[0] = -1 which means that there is no outgoing edges from node $$$0$$$.

Let's add the edge with index $$$0$$$ 0 1 we will update edges[0].to = 1, edges[0].nxt = head[0], which means that edges[0].nxt = -1. after that update the head to the index of this edge head[0] = 0.

Let's add the edge with index $$$1$$$ 0 3 we will update edges[1].to = 3, edges[1].nxt = head[0], which means that edges[1].nxt = 0. after that update the head to the index of this edge head[0] = 1.

Let's add the edge with index $$$4$$$ 0 2 we will update edges[4].to = 2, edges[4].nxt = head[0], which means that edges[0].nxt = 1. after that update the head to the index of this edge head[0] = 4.

Now, Can you guess how to traverse the next neighbor nodes from node $$$0$$$?

for (int curEdgeIndex = head[0]; curEdgeIndex != -1; curEdgeIndex = edges[curEdgeIndex].nxt) {
  int v = edges[curEdgeIndex].to; // v is a neighbor node.
}

So, it's more like we push_front the edges, the new edge will point to the last edge added which is head[node], then we can update head[node] to point to the new added edge.

Next tables show the updates after adding the edges mentioned before in order.

..

#include <bits/stdc++.h>
using namespace std;

const int MAX_NODES = 1e5;
const int MAX_EDGES = 2e5;

/* the head points to the index of last added edge, if no connected edges then it will be -1 */
int head[MAX_NODES];

struct edgeData {
  int to, cost, flow;
  int nxt; /* nxt: is the index of the next edge */
} edges[MAX_EDGES];

int edge_count;

void init() {
  memset(head, -1, sizeof head);
  edge_count = 0;
}

/* the index of the new added edge will be "edge_count" 0-based
 * we update the edge data (to, cost, nxt, ...)
 * then we update the head of the "from node" to the index of this edge
 * after that "edge_count" should be incremented  */
void addEdge(int from, int to, int cost) {
  edges[edge_count].to = to;
  edges[edge_count].cost = cost;
  edges[edge_count].nxt = head[from];
  head[from] = edge_count;
  edge_count++;
}

int main() {
  int n, m;
  cin >> n >> m;
  init(); // don't forget to call this before adding any edges
  for (int i = 0; i < m; i++) {
    int from, to, cost;
    cin >> from >> to >> cost;
    addEdge(from, to, cost);
  }
  for (int i = 0; i < n; i++) {
    cout << i << ":";
    for (int e = head[i]; ~e; e = edges[e].nxt) {
      cout << " " << edges[e].to;
    }
    cout << endl;
  }
  return 0;
}

$$$ $$$

Undirected graph trick

It's obvious how to create undirected graph (just add two opposite edges).

The trick is when we add the first directed edge, we must add the opposite one directly after it, so their indices are next to each other.

So the first edge will have two directed edges with indices $$${0, 1}$$$, and the second edge with indices $$${2, 3}$$$, and so on.

This trick is very useful when we have an edge and we want to get the opposite edge in min cost max flow algorithms.

Can you guess how to do this quickly in $$$\mathcal{O}(1)$$$?

int oppositeEdgeIndex = curEdgeInex ^ 1;

/* add undirected edge, or add two opposite directed edges */
void addBiEdge(int from, int to, int cost) {
  addEdge(from, to, cost);
  addEdge(to, from, cost);
}

Why this is useful?

1. If you know the maximum number of edges from the start, then you can allocate the exact needed memory to the arrays on the stack or data segment, this is useful when you work on embedded systems where you cannot allocate memory on the heap.

2. Sometimes we need to visit edges in a graph, so I think this representation is more convenient, because each edge has its own index.

3. Maintainable, sometimes when you need to add extra information to the edges, all you need to do is add the info to edgeData struct, and you will not change a lot in the old code.

That's it, Thanks for reading and I hope it was useful. Any suggestions or improvements are welcome.