# Number of paths from Start to End through each node

Posted 1 month ago
335 Views
|
5 Replies
|
1 Total Likes
|
 Given an acyclic network g I am trying to figure out how to compute the number of paths in g going from the Start vertex to the End vertex through each vertex, i, in the network.The closest function I found is BetweennessCentrality[g]. This looks at all pairs of start and end vertex and finds the fraction of the 'shortest paths' which goes through a vertex,i, of interest. This is close to what I want and shows that the basic functionality of computing number of paths through a vertex exists within Mathematica. However, this isn't what I am looking for as I am not not interested in all possible start and end nodes and I am not interested in just shortest paths.thx
5 Replies
Sort By:
Posted 1 month ago
 Given that the graph g is acyclic, there is one and only one path between any two vertices. The path is necessarily the shortest path, and in general will not include every vertex.I think you need to reconsider the your problem more carefully, and then you will find the solution.
Posted 1 month ago
 What you wrote is true if the Start vertex and the Edge vertex are part of the same edge
Posted 1 month ago
 Thanks for your reply but ... for an acyclic graph(1) there are typically many paths between two vertices, (See FindPath documentation of Mathematics) (2) Most of these paths will not be the shortest path
 Hi Les,It is not clear exactly what you are after. Let's use a specific example g = ExampleData[{"NetworkGraph", "Friendship"}] All paths between "Ben" and "James" pathsBenJames = FindPath[g, "Ben", "James", Infinity, All] (* {{"Ben", "Anna", "Rudy", "James"}, {"Ben", "Carol", "Anna", "Rudy", "James"}, {"Ben", "Rose", "Anna", "Rudy", "James"}, {"Ben", "Anna", "Larry", "Linda", "James"}, {"Ben", "Carol", "Anna", "Larry", "Linda", "James"}, {"Ben", "Rose", "Nora", "Larry", "Linda", "James"}, {"Ben", "Rose", "Nora", "Anna", "Rudy", "James"}, {"Ben", "Rose", "Anna", "Larry", "Linda", "James"}, {"Ben", "Anna", "Nora", "Larry", "Linda", "James"}, {"Ben", "Carol", "Anna", "Nora", "Larry", "Linda", "James"}, {"Ben", "Rose", "Nora", "Larry", "Anna", "Rudy", "James"}, {"Ben", "Rose", "Nora", "Anna", "Larry", "Linda", "James"}, {"Ben", "Rose", "Anna", "Nora", "Larry", "Linda", "James"}, {"Ben", "Anna", "Rose", "Nora", "Larry", "Linda", "James"}, {"Ben", "Carol", "Anna", "Rose", "Nora", "Larry", "Linda", "James"}} *) How many are there? Length@pathsBenJames (* 15 *) Which paths include "Rudy" pathsRudy = pathsBenJames // Select[MemberQ[#, "Rudy"] &] (* {{"Ben", "Anna", "Rudy", "James"}, {"Ben", "Carol", "Anna", "Rudy", "James"}, {"Ben", "Rose", "Anna", "Rudy", "James"}, {"Ben", "Rose", "Nora", "Anna", "Rudy", "James"}, {"Ben", "Rose", "Nora", "Larry", "Anna", "Rudy", "James"}} *) Length@pathsRudy (* 5 *) Length of each path Length /@ pathsRudy (* {4, 5, 5, 6, 7} *) I think that answers your first question, right?Using the above example, can you explain what you mean by Also, what I really want to know is which nodes have the highest count, ie I want to do this for all nodes, i, and then sort the count.