Draw Graph from distance to other nodes

Question

I have a matrix that shows the distance from a node to another node:

  A B C D E
A 0 2 4 3 1
B 2 0 2 1 3
C 4 2 0 2 1
D 3 1 2 0 2
E 1 3 1 2 0

To clearify: The 2 at A and B means there are 2 "hops" from A to B like

A ------ X ------ B

X is unknow, it could be anything, even nodes that are not in the list.

Assuming this is a tree graph, how can I draw the graph to this matrix using fewest possible nodes that are not in the matrix?

Answer 1

Assuming that you are talking about simple undirected graphs (so there are no multiple edges, no loops, and if there is an edge between $A$ and $B$ then there is also an edge between $B$ and $A$ - this is equivalent to the matrix you've given being symmetric), then all you need to consider is the position of the $1$'s in your matrix. These tell you the neighbours of a given vertex. Thus by starting with an arbitrary vertex you can draw the graph.

For example in the above you could start with vertex $A$, and then as the entry in row $A$ column $E$ is a $1$, you know that $E$ is a neighbour of $A$. Since this is the only $1$ in row $A$, it will be the only neighbour of $A$.

The other entries in the matrix should just give you "checks", i.e. ways of checking that you have drawn your graph correctly.

However, as pointed out by @Arthur, the matrix you have given is not a valid matrix in this context.

Answer 2

There are many ways to break a tree into subtrees. A solution to your problem might correctly break the matrix into several small matrices giving related smaller problems. Solve them (by breaking down further) and then these subtrees can be fit together.

If the information in the matrix is consistent then there is a single minimal tree which attains it. I'll give a few short methods and then a slightly more detailed one. First some comments. Look for the largest number in each row and column, these identify the degree one vertices in the final tree. Such a node is called a leaf.

Call the distance from $A$ to $B$ $d(A,B).$ Then we have to have $d(A,B) \le d(A,E)+d(E,B)$, this is true for any graph, tree or not, and your matrix of random example integers actually fails the condition because $4=d(A,C) \gt d(A,E)+d(E,C)=2$.

In a tree, $d(A,C)+d(C,B)-d(A,B)$ is twice the distance from $C$ to the nearest point on the unique shortest path from $A$ to $B$. When this number is $0$ then $C$ is on the path and we say that $C$ is between $A$ and $B$.

Delete the leaves if you have a $1$ in your matrix in a leaf row then draw the edge connecting that leaf $L$ to its neighbor $M$ and then delete that row and column from your matrix. This makes $M$ a leaf. Repeat if desired.

Delete an edge Suppose you have a $1$ in the matrix corresponding to an edge $AB$ with neither $A$ nor $B$ leaves. Then for every other vertex $C$ either $d(A,C)=d(B,C)-1$ (an $A$-node) or $d(A,C)=d(B,C)+1$ (a $B$-node) or the matrix is faulty. Make a matrix for the $A$ nodes and $A$ and another for the $B$ nodes and $B$. This gives two smaller problems to find a tree. Solve them then connect the two trees by edge $AB.$

Generalized What if there are not any $1$s? (or even if there are?) Pick any non leaf pair $A,B$ at distance $d(A,B)=k,$ then there are three cases for a node $C$: If $d(C,B)=d(C,A)+k$ we have an $A$ node ($A$ is between $B$ and $C$). If $D(C,B)=d(C,A)-k$ we have a $B$ node. Make two trees as before. The third case (a middle node) is none of the above. Use these nodes to make a third subtree together with $A$ and $B$. Now join up the three trees by their overlap at $A$ and $B$.

Delete a vertex If there is a vertex $C$ which you suspect has high degree (like there are many $1$s in its row) but at a minimum not a leaf vertex then then sort the other nodes into groups with $A,B$ in the same group exactly when $C$ is not between $A$ and $B$. If $C$ is not between $A$ and $B$ and also not between $A$ and $B'$ then $C$ can't be between $B$ and $B'$ either. Make one matrix for each group together with $C$. This gives lots of smaller problems with smaller matrices. Solve each by your favorite of the methods then glue them together at $C$.

Note: If you happen to have a matrix at some stage like

$$\ X\ Y$$ $$X\ 0\ 5$$ $$Y\ 5\ 0$$

then you know that there is a path with $4$ new nodes which joins $X$ to $Y$ but otherwise have no edges on them, so you can just put them in right away.

Overview of a more detailed method:

• Find a longest path in the tree (say $k+1$ edges)
• Delete the $k+1$ edges to break the tree into two isolated vertices and $k$ little trees (some perhaps consisting only of one vertex).
• Find and use the smaller matrix for each little tree to recreate it (repeat the process).
• Then restore the path to get the whole tree.

Details

• Find the largest number in your matrix (it could occur several places, just pick any one) say it is $d(A,B)=k+1.$ Then $A$ and $B$ are connected by a unique path with $k+1$ edges and $k$ internal nodes $A-v_1-v_2-\cdots-v_k-B.$ The names $v_i$ are temporary for now.
• For each node $C$ from the matrix compute the numbers $$j=\frac{d(A,C)+d(C,B)-(k+1)}2$$ and $$i=\frac{d(A,C)-d(C,B)+(k+1)}2.$$ If $j=0$ then $C=v_i$ otherwise $v_i$ is the closest point to $C$ on the path and the distance from $C$ to $v_i$ is $j$. So I know which of the $v_i$ are already in the matrix and which are new nodes.
• Ignore $A$ (on the single edge $A-v_1$) and $B$ (on the single edge $v_k-B$). Now for each $v_i$ gather it and the (matrix) nodes closer to it than to any other of the $v_j$ (but ignore $A,B$). let $E$ be one of these vertices. Then I know $d(E,v_i)=j$ from my calculation. This allows me to create the matrix giving the distances between these vertices. Use the same process on these smaller matrices to add even more vertices as needed and find the associated tree. Together with the $k+1$ edges from before you have the whole tree.

Comments If $v_i=C$ then I have $d(E,v_i)=d(E,C)$ both from my matrix and my calculation. Unless these agree, the given matrix is flawed.

If the starting matrix had $n$ rows and largest entry $k+1$ then each new matrix will have largest entry at most $k$ and also at most $n-1$ rows ($A$ and $B$ are gone and at most one of the new vertices is involved) Also, the total number of rows from all the new matrices combined is at most $n+k$ (each previous node shows up in only one of the new matrices).