# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Find the path matrix of a graph

Contributed by:
Peter Burbery

ResourceFunction["GraphPathMatrix"][ gives the path matrix of the graph |

An entry *p*_{ij} of the path matrix is 1 if there is a path between vertex *ν*_{i} and vertex *ν*_{j}, and 0 otherwise.

The path matrix is related to the Floyd-Warshall algorithm.

ResourceFunction["GraphPathMatrix"][*g*,SparseArray] gives the path matrix as a SparseArray object.

An undirected connected graph will have all matrix entries equal to 1. These are not terribly interesting. The function is better suited to directed graphs where not all components are connected rather than to graphs where every vertex is reachable.

Find the path matrix representation of a directed graph:

In[1]:= |

Out[1]= |

A random graph:

In[2]:= |

Out[2]= |

A directed graph generated from the Price graph distribution:

In[3]:= |

Out[3]= |

Random cycle graph:

In[4]:= |

Out[4]= |

Directed graph from graph product:

In[5]:= |

Out[5]= |

Directed graph from graph product of multigraphs:

In[6]:= |

Out[6]= |

A parametric k-ary tree graph:

In[7]:= |

Out[7]= |

A parametric complete k-ary tree graph:

In[8]:= |

Out[8]= |

A random directed graph:

In[9]:= |

Out[9]= |

An acyclic directed graph:

In[10]:= |

Out[10]= |

Another acyclic directed graph:

In[11]:= |

Out[11]= |

A random Bernoulli graph:

In[12]:= |

Out[12]= |

A random disconnected spatial directed graph with random orientations for the directed edges:

In[13]:= |

Out[13]= |

Find the path matrix representation of the Petersen graph with script capital letters for the vertex names:

In[14]:= |

Out[14]= |

Find the path matrix representation of the undirected graph:

In[15]:= |

Out[15]= |

Output the matrix as a sparse array for efficiency:

In[16]:= |

Out[17]= |

Wolfram Language 13.2 (December 2022) or above

- 1.0.0 – 02 June 2023

This work is licensed under a Creative Commons Attribution 4.0 International License