4
$\begingroup$

For a directed graph g, one can obtain its adjacency matrix as:

SeedRandom[3];
g = RandomGraph[{10, 20}, DirectedEdges -> True, VertexLabels -> "Name"]
AdjacencyMatrix[g] // MatrixForm

Then, a subgraph of g defined by all the pathways from vertex 6 to 4 is:

fp = FindPath[g, 6, 4, Infinity, All]
hfp = HighlightGraph[g, Subgraph[g, fp, VertexLabels -> "Name"]]

I want to find the adjacency matrix of hfp, showing the highlighted edges in hfp in a 10 by 10 matrix (the size of the original digraph g).

$\endgroup$
3
  • $\begingroup$ Have you tried PathGraph? Like this: pgs = PathGraph /@ fp; You can then get the matrices for all paths AdjacencyMatrix /@ pgs and combine those. Cycles won't be preserved though. $\endgroup$
    – flinty
    Apr 25, 2021 at 20:23
  • $\begingroup$ Also what's wrong with just sg // AdjacencyMatrix where sg = Subgraph[g, fp, VertexLabels -> "Name"]; ? $\endgroup$
    – flinty
    Apr 25, 2021 at 20:28
  • $\begingroup$ @flinty: Both of your suggestions generate a (5,5) AdjacencyMatrix. However, I want to create a (10,10) Adjacency Matrix (the size of the original directed graph) which incorporates the paths generated. $\endgroup$ Apr 25, 2021 at 20:38

2 Answers 2

4
$\begingroup$
am = AdjacencyMatrix[Graph[VertexList @ g, EdgeList @ Subgraph[g, fp]]];

am // MatrixForm // TeXForm

$\left( \begin{array}{cccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right)$

$\endgroup$
5
$\begingroup$

For a subgraph of g defined by all the pathways from vertex 6 to vertex 4, find the adjacency matrix that represents only the edges of the subgraph of the paths.

SeedRandom[3];
g = RandomGraph[{10, 20}, DirectedEdges -> True, VertexLabels -> "Name"];
fp = FindPath[g, 6, 4, Infinity, All];

We can find the edges of g that are not in Subgraph[g, fp] using Complement[EdgeList[g], EdgeList[Subgraph[g, fp]]], then remove these edges from g using EdgeDelete. The adjacency matrix of g2 is the matrix of g with only the edges of the subgraph.

g2 = EdgeDelete[g, Complement[EdgeList[g], EdgeList[Subgraph[g, fp]]]];
MatrixForm[m = WeightedAdjacencyMatrix[g2]]

$$ {\small\left( \begin{array}{cccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right)} $$

Sort@EdgeList[Subgraph[g, fp]] === EdgeList[g2]
(* True *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.