20.5. Examples of W Matrices

So, before proceeding to the Warshall’s algorithm, let me give you an example to make clear what exactly I mean by these W matrices. So, imagine this is your given relation R. So, the diagram or the directed graph for this relation is as follows. So, the nodes will be 1, 2, 3, 4. Since 1 is related to 4, you have this directed edge, 2 is related to 1, you have this directed edge and so on.

In this chunk, the lecturer sets up the stage for understanding W matrices by introducing a specific example. The nodes are labeled numerically (1, 2, 3, and 4) and describe a directed graph representing the relationships between these nodes. Each directed edge indicates a relationship from one node to another, establishing a visual representation to help students understand how paths between nodes will be evaluated in subsequent parts of the lesson.

Think of the directed graph as a city map where each node represents a landmark (like a park or a restaurant). The directed edges signify one-way streets connecting these landmarks, showing how one can travel from one location to another. This helps students visualize how paths in a graph work - just like finding a route between different places in a town.

We start with the matrix W0, which is the matrix for your relation R (M). So, what I have done here is that I have just added the entry 1 for (i, j) pair if i is an edge to the node j; otherwise, the entry is 0.

The lecturer explains the concept of the initial W matrix, W0. This matrix is constructed such that for every pair of nodes (i, j), an entry of 1 is recorded if a direct connection (edge) exists from node i to node j in the relation R. If no direct edge exists, the entry is 0. This matrix serves as the foundation for further calculations in Warshall's algorithm, where paths between nodes will be assessed based on the allowable internal nodes.

Envision a social network where individuals can follow one another. The W0 matrix works like a list showing connections: if person A follows person B, we mark it with a 1 in the matrix; if not, a 0. This initial setup helps determine if there are more complex connections (or paths) as we assess potential indirect relationships later on.

Now let us see the matrix W1. The interpretation of W1 is that the i, jth entry will be 1 if a path with only node 1 as intermediate node is present from i to j.

In moving to the W1 matrix, we look specifically for paths that only use node 1 as an intermediate node between other nodes. This means that if a direct connection from i to j exists or if i can reach j through node 1, the entry will be marked as 1. Otherwise, it remains 0. The progression from W0 to W1 shows how the addition of allowed intermediate nodes can reveal new paths previously unconsidered.

Return to the city map: if we are only allowed to use 'Park 1' as a stopover, we mark potential routes by checking if we can get to 'Restaurant 3' from 'Cafe 2' through 'Park 1'. If we can get from one to another using just that park, we note that route as valid.

So, now Warshall’s algorithm boils down to the following that how exactly I am going to update my matrix W(k - 1) to the matrix W(k).

The update operation involves checking existing entries in the current W matrix and updating them for the next iteration k. The matrix entry W(k) will be set to 1 if either there is an existing connection in W(k - 1) or if a new path can be formed through node k. This process illustrates a systematic approach to finding relationships and enhancing the connectivity mapping as new intermediate nodes are included.

Imagine adding more bus routes in a public transport system: If there are already connections between stops (entries being 1), they remain valid. But if we introduce new stops (like bus route through node k), we reassess to see if people can reach new destinations from old ones by including the new route.

I will say that this will be my matrix for R*, and this is because you can check that only those nodes which are reachable from any other node for those particular entries the i, jth entry will become 1 here in W4.

In the final matrix W4, a mark of 1 signifies that there is a reachable path from node i to node j through any combination of the allowed intermediary nodes. This final matrix outputs the connectivity of the graph, giving a comprehensive view of how nodes interact with one another based on the established relations.

Returning to the social network example, W4 summarizes the complete connectivity of individuals. If 'Person A' can indirectly reach 'Person C' through a series of mutual friends, that is captured as a connection in this final matrix. It's as if we drew a full map of relationships, showing who can reach whom directly or indirectly.

--