How do I construct the biadjacency matrix of a DAG?

Question

For a bipartite graph, you can substitute the adjacency matrix with what is called its biadjacency matrix:

The adjacency matrix A of a bipartite graph whose parts have r and s vertices has the form

    A =  O  B
         BT O

where B is an r × s matrix and O is an all-zero matrix. Clearly, the matrix B uniquely represents the bipartite graphs, and it is commonly called its biadjacency matrix.

Now, a DAG is a bipartite graph, for example, you could topologically sort it and have the sets U and V being nodes that are on an odd or even topological level, respectively.

This means, that for a DAG with n nodes, I only need a (n/2)² matrix (on average) instead of a n² matrix. Problem is, I don't know how to construct it. Any hints?

Answer 1

I believe you can't construct a biadjacency matrix for a DAG, because not every DAG is a bipartite graph.

Here is a simple example: consider a directed graph with 3 vertices, and denote them as A, B and C. The edges connect A to B, B to C and A to C. The graph is clearly a DAG, since it is directed and there are no cycles (A->B->C<-A isn't a cycle). However, the graph is not bipartite: there is no way to divide A, B and C to two disjoint sets, where there are no edges between vertices in the same set.

The conclusion is that there graphes which are DAGs but not bipartite, so not every DAG is bipartite.

Note that the fact that you can topologically sort a DAG and divide the vertices to two disjoint sets, does not mean there are no edges between vertices of the same set.

Answer 2

Both the stated symmetry of your biadjacency matrix A, and your intention to use topological sorting to isolate a bipartite structure in the graph - point out that you are in fact referring to an indirected, acyclic, graph - i.e., a tree. (A being symmetric explicitly says that if you have an edge from x to y, you must have an edge from y to x - hence, directedness becomes meaningless).

Assuming that is indeed your intention:

(1) As for any indirected graph, you can immediately settle for around 0.5*(n^2) (exactly: n(n-1)/2), by storing just the upper triangle of the adjacency matrix.

(2) Suppose you must store just B.

You must first identify disjoint subsets, say R & S, each having no internal edges. Topological sorting is a plausible option - in a tree, it amounts to picking a root and labeling vertices by being on even/odd levels above the root (in contrast with common visualizations, I prefer to think of a tree as actually growing above its root..). I understand from your question that you're comfortable with that, so I won't even give pseudo-code.

Next you need to re-label the vertices so that all R's vertices come first, and all S's vertices follow:

Allocate NewLabels(r + s);
CurRSize = 0;
CurSSize = 0;
for each (TreeLevel)
    if #CurLevel is even  // append to R vertices
       NewLabels(CurRSize : CurRsize + CurLevelSize - 1) = CurLevelVertexNums;
       CurRSize += CurLevelSize;
    else // append to S vertices
       NewLabels(r+s - (CurSSize+CurLevelSize) : r+s - (CurSSize + 1) = CurLevelVertexNums;
       CurSSize += CurLevelSize;

(Some optimizations immediately come to mind, but they're not important here).

Then, you can serially scan the graph edges, and store them as entries into the r x s matrix B, indexed by the new vertex labels:

Allocate B(r,s);
Zero(B);
for each (edge = x<-->y)
   i = NewLabels(x);
   j = NewLabels(y) - r; // must adjust, to index just B
   B(i,j) = 1;

HTH.