What does it mean by "Path Matrix" and "Transitive Closure" of a graph (Directed and Undirected)?

Question

I the discussion of various graph algorithms, I see the terms "Path Matrix" and "Transitive Closure" which are not well-defined anywhere.

What does it mean by "Path Matrix" and "Transitive Closure" in case of both Directed and Undirected graphs?

Answer 1

Path Matrix in graph theory is a matrix sized n*n, where n is the number of vertices of the graph. The element on the ith row and jth column is 1 if there's a path from ith vertex to jth in the graph, and 0 if there is not.

The Floyd Algorithm is often used to compute the path matrix.

The definition doesn't differentiate between directed and undirected graphs, but it's clear that for undirected graphs the matrix is always symmetrical.

Transitive Closure is a similar concept, but it's from somewhat different field. Imagine you have a set of objects and for some of them you know that one is definitely better than the other, so you can write a > b (">" being the shorthand for "better"). Definitely you should assume that if a > b and b > c then a > c. This is called the transitivity rule. Then for any two objects you want to know, whether one of them is better than the other, or it's unknown. This is the closure: first you have a relation that's possibly not transitive, but after assuming transitivity you can complete it up to a transitive one.

To solve this problem you construct a directed graph, where a vertex corresponds to every of the mentioned objects (a, b, c, etc.) where a directed edge u -> v exists if and only if u > v. Then you can construct the path matrix defined in the first paragraph and it will give you the answer: obviously, the existence of a path between two vertices is equivalent to existence of a chain of relations as u > a > b > ... > z > v so, by the transitivity rule, u > v.

As a sidenote for transitive closure, as you asked about both directed and undirected graphs, the example given uses a non-symmetric relation (>), and thereafter the graph was directed, but it's not always the case. Any equivalence relation, for example, always satisfies transitivity but also has to satisfy symmetry, so corresponding graph is undirected. You can find a transitive closure of symmetrical relation (or graph).

Answer 2

I think unkulunkulu's answer is pretty complete, but given JMSA seems unsatisfied, I'll make another attempt.

Let's start not with the path matrix, but with the adjacency matrix. The adjacency matrix is the standard representation of a graph. If adj is the adjacency matrix for some graph G, then adj[i][j] == 1 if vertex i is adjacent to vertex j (i.e. there is an edge from i to j), and 0 otherwise. In other words, adj[i][j] == 1 if and only if we can get from vertex i to vertex j in one "step".

Now, let's define another matrix which I'll call adj2: adj2[i][j] == 1 if and only if we can get from vertex i to vertex j in two steps or less. You might call it a "two-step adjacency" matrix. The important thing is that adj2 can be defined in terms of adj:

def adj2(i,j):
    if adj(i,j) == 1:
        return 1
    else:
        for k in range(0,n): # where n is the number of vertices in G
            if adj(i,k) == 1 and adj(k,j) == 1:
                return 1
    return 0

That is, adj2[i][j] is 1 if i is adjacent to j (i.e. adj[i][j] == 1) or if there exists some other vertex k such that you can step from i to k and then from k to j (i.e. adj[i][j] == 1 and adj[k][j] == 1).

As you can imagine, you can use the same logic to define a "three-step" adjacency matrix adj3, adj4, adj5, and so on. If you go on long enough (e.g. to adjn, where n is the number of vertices in the graph), you get a matrix that tells you whether there's a path of any length from vertex i to vertex j. This, of course, would also be the graph's path matrix: adjn[i][j] == path[i][j] for all i, j. (Note: Don't confuse path matrix with distance matrix.)

A mathematician would say that path[i][j] is the transitive closure of adj[i][j] on the graph G.

Transitive closures exist independently from graph theory; adj is not the only thing with a transitive closure. Roughly speaking, all functions (in the programming sense) that take two arguments and return a Boolean value have a transitive closure.

The equality (==) and inequality (<, >, <=, >=) operators are familiar examples of such functions. These differ from adj, however, in that they are themselves transitive. "f(i,j) is transitive" means that if f(i,j) == true, and f(j,k) == true, then f(i, k) == true. You know that this property is true of, say, the "less than" relation: from a < b and b < c, you can infer that a < c. The transitive closure of a transitive function f is just f.

adj is not generally transitive. Consider the graph:

v1---v2---v3

In this graph, adj might represent the function busBetween(city1, city2). Here, there's a bus you can take from v1 to v2 (adj[1][2] == 1) and a bus from v2 to v3 (adj[2][3] == 1), but there's no bus from v1 directly to v3 (adj[1][2] == 0). There is a bus-path from v1 to v3, but v1 and v3 are not bus-adjacent. For this graph, adj is not transitive, so path, which is the transitive closure of adj, is different from adj.

If we add an edge between v1 and v3,

v1---v2---v3
 \        /
   \----/

then adj becomes transitive: In every possible case, adj[i][j] == 1 and adj[j][k] == 1 implies adj[i][k] == 1. For this graph, path and adj are the same. That the graph is undirected corresponds to the "symmetry" property. If we added loops to each vertex so that v1, v2, and v3 were each adjacent to themselves, the resulting graph would be transitive, symmetric, and "reflexive", and could be said to represent equality (==) over the set {1,2,3}.

This begins to illustrate how graphs can represent different functions, and how properties of the function are reflected in properties of the graph. In general, if you let adj represent some function f, then path is the transitive closure of f.

For a formal definition of transitive closures, I refer you to Wikipedia. It isn't a hard concept once you understand all the math jargon.