graphshortestpath function visiting all nodes

Hi,

Is there a way I can manipulate this function in order to force the path include all nodes? I mean, how can I change the code in order to include each node to find the shortest path , but with the constrain that we must visit all nodes?

Thank you in advance

[Christine Tobler]

Do you want to visit each node exactly once, or would it be okay to visit some of the nodes twice, as long as each node is visited at least once? Also, is your graph directed or undirected?

[Jason]

W

   = [5 1 5 4 6 1 1 4 7 2 6 7 3 2 1 2 3 8 2 8];

DG = sparse([1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6],[2 3 1 3 4 5 1 2 4 5 2 3 5 6 2 3 4 6 4 5],W)

h = view(biograph(DG,[],'ShowWeights','on'))

[dist,path,pred] = graphshortestpath(DG,1,6)

set(h.Nodes(path),'Color',[0 1 1])

edges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));

set(edges,'LineColor',[0 0 1])

set(edges,'LineWidth',2)

I am implementing the above code, as I understand this function examines the shortest path among all the nodes.

I want to manipulate the code in order to visit all the nodes and outputs a graph that has visited all the nodes with the minimum distance.

[Jason]

Plus, I cannot visit the same node twice for example 1-2-3-1-4.

Answer 1

[Jason]

Any feedback on my last q staff?

https://www.mathworks.com/matlabcentral/answers/386714-graphshortestpath-function-visiting-all-nodes#comment_545301

Answer 2

[Christine Tobler]

As Steve Lord has said, in general this is an NP-complete problem, so could become quite expensive. For the 6-node graph you are looking at, this is easy to compute using an exhaustive search (I will use the graph object instead of the bioinfo variants here):

W = [5 1 5 4 6 1 1 4 7 2 6 7 3 2 1 2 3 8 2 8];
DG = sparse([1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6],...
            [2 3 1 3 4 5 1 2 4 5 2 3 5 6 2 3 4 6 4 5],W);

g = graph(DG);

% Construct all possible ways that we could traverse all nodes, starting at
% node 1 and ending at node 6:

paths = perms(2:5);
paths = [ones(size(paths, 1), 1) paths 6*ones(size(paths, 1), 1)];

% Check if a path is feasible (edges exist between all node pairs), and how
% long it is

dist = NaN(size(paths, 1), 1);

for ii=1:size(paths, 1)

      path = paths(ii, :);
      edgeID = findedge(g, path(1:end-1), path(2:end));

      if all(edgeID ~= 0)
          dist(ii) = sum(g.Edges.Weight(edgeID));
      end
  end

[~, id] = min(dist)
paths(id, :)

p = plot(g, 'EdgeLabel', g.Edges.Weight);
highlight(p, paths(id, :), 'EdgeColor', 'red')

[Jason]

Thanks for the quick repsonse Christine!

I' ll test what you coded there and give feedback.

In the meantime, I want to ask if I can implement this 6 node graph using the TSP (solver/problem based solution).

Thank you again!

[Jason]

I change the W and DG and I get this

Error using graph (line 227) Adjacency matrix must be symmetric.

The new W and DG are:

W = [3 1 5 4 1 5 4 3 5 4 2 1 3 1 3 3 5 2 4 1]

and

DG = sparse([1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5],... [2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4],W);

Respectively. I also change the paths = perms(2:5); to 2:4

and

paths = [ones(size(paths, 1), 1) paths 6-> 5*ones(size(paths, 1), 1)]

[Jason]

Any update on this?

[Steven Lord]

Do you have an undirected graph or a directed digraph? If your network is undirected and you try to construct the graph using the adjacency matrix input A, that input must be symmetric or you must specify the TYPE input when constructing your graph.

[Jason]

Well it is a directed graph.It has 5 nodes instead of 6. check it out.

W = [3 1 5 4 1 5 4 3 5 4 2 1 3 1 3 3 5 2 4 1];
DG = sparse([1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5],...
            [2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4],W);
g = graph(DG);
% Construct all possible ways that we could traverse all nodes, starting at
* *% node 1 and ending at node 6**:
paths = perms(2:5);
paths = [ones(size(paths, 1), 1) paths 6*ones(size(paths, 1), 1)];
% Check if a path is feasible (edges exist between all node pairs), and how
% long it is
dist = NaN(size(paths, 1), 1);
for ii=1:size(paths, 1)
      path = paths(ii, :);
      edgeID = findedge(g, path(1:end-1), path(2:end));
      if all(edgeID ~= 0)
          dist(ii) = sum(g.Edges.Weight(edgeID));
      end
  end
[~, id] = min(dist)
paths(id, :)
p = plot(g, 'EdgeLabel', g.Edges.Weight);
highlight(p, paths(id, :), 'EdgeColor', 'red')

Do I have to change the perms? maybe 2:4? I say this because this is a 5-node graph.

Plus another Question, Why cant I implement any code i order to manipulate the graphshortestpath to force the code pass by all the nodes. Cannot understand why this is so complicated.

[Steven Lord]

If it is a directed graph then you need to use digraph rather than graph. The graph function creates an undirected graph.

As for why it's so complicated, did you read the second link in my answer? The key point from that article: "Both problems [determining whether a graph has a Hamiltonian path or whether it has a Hamiltonian cycle] are NP-complete." The phrase NP-complete is itself a link to another Wikipedia article, whose key paragraph is the following (I added some emphasis on a few key points.)

"Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place; the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today."

Note that P versus NP is one of the Millennium Prize problems and is worth US $1 million in prize money if you can solve it.

The question "Is there a Hamiltonian path in my graph?" is simple to ask but not so simple to answer for larger graphs. You want an even harder variant of that, not just looking for a Hamiltonian path but a shortest Hamiltonian path.

For a small graph, use Christine's exhaustive approach. For a larger graph, use Christine's exhaustive approach and wait a while or implement one or more of the algorithms whose papers are linked in the References section on the "Hamiltonian path problem" Wikipedia page.

[Jason]

Ok I understand there.

I changed to digraph but the thing is that it doesnot give me the shortest path. Using the bioinfo variants I can check which is the shortest path between specific nodes and thats ok but I want this path to include all nodes. meaning starting from 1 and coming back to it but through the optimal path.

[Christine Tobler]

Sorry I just realized I forgot to check up on this post. The shortest path between two nodes will likely not go through all the nodes - so it's a question of where the priority is.

I'm not quite sure what answer you are looking for. Could you tell me in a small example, what answer you are getting, and what answer you are expecting to get?

[Jason]

Hi Christine and thank you for your reply. I am looking for a code which does what the bioinfo variants do,namely, finding the optinmal path between two nodes BUT I want to find the this path -for example between node 1 and node2- which passes by ALL the nodes. I am looking for a command, constraint or whatever that can manipulate this piece of code in order to force the path include ALL nodes. Thank you again.

[Steven Lord]

We understand what you have asked for. Computing that can be extremely difficult and/or time consuming.

Can you tell us why you want what you have asked for, how you would use it if you were able to compute it? There may be a way to accomplish what you want to do with a different approach or technique, one that avoids the NP-complete problem of finding a Hamiltonian path or cycle.

[Jason]

Hi Steven, and thank you for the response. Its part of my diploma thesis . Its similar the TSP but I want to return to the beginning node. I know there is a function for the TSP problem but I dont like the thing that it computes intermediate routes. Whats your opinion on this alternative you are talking about?

[Jason]

I know I cannot find the top of the top optimum path but I think I can work this out for lets say 5-7 nodes as an exmaple.

[Christine Tobler]

So you are looking for a variant of the code above, but instead of "start at node 1, visit each of nodes 2-5 once, end at node 6" you are looking for "start at node 1, visit each of nodes 2-5 once, end at node 1"? That can easily be achieved with a small change:

W = [3 1 5 4 1 5 4 3 5 4 2 1 3 1 3 3 5 2 4 1];
DG = sparse([1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5],...
    [2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4],W);

g = digraph(DG);

% Construct all possible ways that we could traverse all nodes, starting at
% node 1 and ending at node 6:

paths = perms(2:5);
paths = [ones(size(paths, 1), 1) paths];

% Check if a path is feasible (edges exist between all node pairs), and how
% long it is

dist = NaN(size(paths, 1), 1);

for ii=1:size(paths, 1)

      path = paths(ii, :);
      edgeID = findedge(g, path(1:end), path([2:end 1]));

      if all(edgeID ~= 0)
          dist(ii) = sum(g.Edges.Weight(edgeID));
      end
  end

[~, id] = min(dist)
mypath = paths(id, :)

p = plot(g, 'EdgeLabel', g.Edges.Weight);
highlight(p, mypath([1:end 1]), 'EdgeColor', 'red')

Note this will not work for every possible graph: It's possible that no path that visits all nodes exists (for example if one node has no outgoing / no incoming edges).

[Jason]

Thank you very much Christine. So one of the prerequisites to run this code is to have a similar graph as the one on which this certain code is applied.

Plus the answer for the path is completely correct, but I if the id returns the path cost/distance then 15 -in this certain occasion- is wrong. This can be checked through the tables we create in the beginning, so the path distance is 5. And one more question, what happens when I change the perms? If I have a similar graph with 6 or 7 nodes what do I change?

[Jason]

and one more -sorry for that-.

Can you please explain what paths = [ones(size(paths, 1), 1) paths]; does?

and what dist = NaN(size(paths, 1), 1); does?

[Steven Lord]

id is the index of the minimum distance and the path that achieves that minimum distance, not the minimum distance itself. For the distance itself you'd want dist(id) (or replace the ~ in the min call with a variable in which you want the minimum distance to be stored.)

Let's look at each of the paths and their corresponding distances in tabular form.

pathsAndDistances = table(dist, paths)

Each row of the paths variable in the pathsAndDistances tables contains a 1 followed by a permutation of the vector 2:5. If you had a digraph with 6 or 7 nodes, those rows would each contain a 1 followed by a permutation of the vector 2:6 or 2:7 respectively.

[Jason]

Hi Steven,

Thanx for your prompt response!

Ok I changed the ~ and everything works fine!

Can you please explain to me what is exactly done inside the whole "for"?? and the mathematical meaning of perms(2:5)?

thank you in advance once again!

[Jason]

any update?

[Steven Lord]

The body of the loop isn't very long. Take a look at the documentation for the findedge function. Under what circumstances does it return 0? When it returns something other than 0, what does that return value represent?

Once you know that, under what circumstances would the if statement condition be satisfied?

As for perms, the documentation describes what it does and includes several examples showing what it does.

[Jason]

Thanks Steven. I took a look at everything you told me.

When I have a directed graph like this one should I always start from node 1? for example if I want to start from node 2 and finish at node 2 do I have to change the paths=perms( 3:5) ? and something inside the for or maybe ?

Thank you in advance again.

[Steven Lord]

Do you want a path or a cycle? If you want a cycle it doesn't really matter where you start. If you want a path and want to start from a different place, permute the numbers of the other nodes then put your starting node at the start of the matrix of permutations.

[Jason]

What is the the matrix of permutations in the given example from Christine?

[Steven Lord]

The output of perms.

[Jason]

Ok I get it. But the example I am talking about is this one : I got 7 nodes and I want o start from node 1 end at node 7. The path includes 3 of the nodes 2,3,4,5,6 which has the max distance instead of min. I get the previous code and changed it to this

W = [22 30 41 50 52 40 0 60 48 38 44 30 0 80 60 50 75 40 0 60 65 66 68 61 0 71 70 65 44 49 0 50 41 52 55 47 0 0 0 0 0 0];
DG = sparse([1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7],...
    [2 3 4 5 6 7 1 3 4 5 6 7 1 2 4 5 6 7 1 2 3 5 6 7 1 2 3 4 6 7 1 2 3 4 5 7 1 2 3 4 5 6],W);
g = digraph(DG);
% Construct all possible ways that we could traverse all nodes, starting at 
% node 1 and ending at node 5 : 
paths = combnk(2:6,3);
paths = [ones(size(paths, 1), 1) paths];
% Check if a path is feasible (edges exist between all node pairs), and how 
% long it is 
dist = NaN(size(paths, 1), 1);
for ii=1:size(paths, 1)
      path = paths(ii, :);
      edgeID = findedge(g, path(1:end), path([2:end 1]));
      if all(edgeID ~= 0)
          dist(ii) = sum(g.Edges.Weight(edgeID));
      end
  end
[shortest_path_distance, id] = min(dist)
mypath = paths(id, :)
p = plot(g, 'EdgeLabel', g.Edges.Weight);
highlight(p, mypath([1:end 7]), 'EdgeColor', 'magenta')

The correct answer for this example is 1->5->3->4->7

But I get something different like 1->4->5->6->1 and the output for the shortest_distance_path is NaN.

[Steven Lord]

path(1:end), path([2:end 1])

How many edges does g have that end at node 1 (which is the first column of each row in the paths variable?) You can find this using the predecessors function.

Rather than waiting for us to respond, if your code does something other than what you expect I recommend using the debugging tools to step through the code and make sure it's doing exactly what you think it's doing and what it should be doing.

[Jason]

ok sorry for this Steven.

[Jason]

Anyway, can you at least show me how to create a matrix with ones in the last column, something like

paths = [ones(size(paths, 1), 1) paths];

but not in the first column. Namely, add ones in the last column of this matrix.

thank you

[Steven Lord]

Move the ones call after the paths variable rather than before.

Answer 3

[Steven Lord]

So you want the shortest Hamiltonian path? That may be very hard.