store path of minimum spanning tree

hi,

i a 14 node system and i want minimum spanning tree from one node to some of the nodes but not all the nodes. at the moment am able to get minimum spanning tree of all the nodes. also is possible to get a full path from one node to the other node instead of the predecessor table?

thanks

Answer 1

[Steven Lord]

Use the shortestpath or shortestpathtree functions for graph and digraph objects.

[sibabalo noludwwe]

thank you. does the shortestpathtree function use the breadth first search or the depth first search.

thanks

[Christine Tobler]

It computes the shortest path from one point to another. If there are multiple paths between these points, it brakes the tie based on which node has the smaller index.

[Steven Lord]

The function allows you to specify different methods. Which method is used by default (either by specifying 'Method', 'auto' or by not specifying the 'Method' at all) depends on the properties of your network. See the documentation of the 'Method' name-value pair argument on the shortestpathtree documentation page for more information.

[sibabalo noludwwe]

thank you,

it seems impossible to specify method and also path form as shown below

[TR3,D]= shortestpathtree(G,13,target,'Method','positive','OutputForm','cell')

it does not seem to plot too, it just says invalid data argument

[sibabalo noludwwe]

OHK i think I see why it cant allow to plot but not sure you can still answer. so if I would want all possible paths ordered in terms of their weights this function wont work will it?

[Christine Tobler]

Yes, this funciton returns one path connecting two points, which has the shortest length possible among all paths connecting these points. It never returns multiple paths.

[sibabalo noludwwe]

Do you know which function will return all possible path and order them according to the edge weight.

while we on this, is it possible to find the shortest path of network directly from simulink system?

[Steven Lord]

Suppose the graph whose spanning tree you're trying to compute is this:

G = graph(ones(5)-eye(5));
plot(G)

One path from 1 to 3 is the edge (1, 3).

Another path from 1 to 3 is (1, 2), (2, 4), (4, 5), (5, 3).

Another path from 1 to 3 is (1, 2), (2, 4), (4, 5), (5, 2), (2, 4), (4, 5), (5, 3).

I can go around that cycle between 2, 4, and 5 an arbitrary number of times before continuing to 3 if I want. So there are an infinite number of possible paths.

Why might you want to go around that path repeatedly? Assume the nodes are cities and taking a path means going on a sales trip. If you make a profit transporting goods from 2 to 4, resupply at 4 and make a profit transporting other goods from 4 to 5, then resupply at 5 and make a profit transporting a third set of goods from 5 to 2 you could continue the cycle accumulating your profits. Even if one or two of the legs costs you money, if the total cost of the trip earns you money why not?

Since you mention your graph or digraph comes from a Simulink model, one type of cycle like that is called an algebraic loop.

Maybe if you tell us a little more about your ultimate goal we can offer suggestions for how to achieve that goal, even in the potential presence of an algebraic loop.

[sibabalo noludwwe]

so this is my goal Steven hope you will understand what am trying to do. I have a 13 bus IEEE test system in Simulink that I got from file exchange. I want to Simulate a fault in simulink for example to say that one of the connection lines is out, and from that I want to compute possible paths from a source to a certain load and run a load flow study of those paths and from there I select the shortest path that passes the load flow study.

at the moment my challenge is to automatically transfer the simulink network after the fault to matlab as a graph. for now I am manually doing the graph myself but it will get complicted as I simulate more faults meaning as i remove several edges.

So if you can assist with the first part I would appreciate it :-)