Graph Shortest Path (Non-Negative Directed Graph)

Dear all,

I am using sparse before using the graphshortestpath function in Matlab. However, there is some edge that I modify to have a 999 value to prevent the algorithm to visit that node. The problem is, the shortest path using Dijkstra method still visiting these nodes and I am not sure why. Here is a sample code of mine

for i=1:length(Value)
    if tf(i) ~= 0
        Value(i) = Value(i) + 999
    else
        Value(i) = Value(i)
    end
end

SparseGraph                         = sparse(from,to,Value);
MatrixGraph                         = full(SparseGraph);
%Adding an additional row to the full matrix so that the matrix is symmetrical
MatrixGraph_1=cat(1,MatrixGraph,zeros(1,size(MatrixGraph,2)));
%Converting matrix back to sparse
SparseGraph                         = sparse(MatrixGraph_1);
[Output_Optimum_time,Output_Optimum_path,Output_Optimum_pred] = graphshortestpath(SparseGraph,1,...
max(to),'Method','Dijkstra');

Thank you for your time

Answer 1

[Dheeraj Singh]

There can be two issues:

1. There is no path without including the edge
2. There are other edges with higher edge_weights due to which it is following that edge for the shortest path

To check, you may increase the edge weight to say something like 999999. If it still uses that edge it means, there is no path to the destination without including that edge.

Answer 2

[Steven Lord]

Rather than using the graphshortestpath function from Bioinformatics Toolbox, I recommend creating a graph or digraph object from your sparse adjacency matrix and using the shortestpath function for graph and digraph objects. You can do a lot with graph and digraph objects; see the documentation for a list of functions that can work on these objects.

To remove edges connected to a node, you can use outedges (and inedges if your network is a digraph) then call rmedge. Let's create a graph using the Buckyball data and display it.

G = graph(bucky);

f1 = figure;
p1 = plot(G);
title('Full bucky graph');

Now let's remove all edges connected to node 17 and plot the resulting graph.

edgesConnectedTo17 = outedges(G, 17);
Gm17 = rmedge(G, edgesConnectedTo17);

figure
p2 = plot(Gm17);
title('Bucky graph minus edges connected to 17')

Both plots display all 60 nodes of the bucky graph but they have different layouts. Since node 17 isn't connected to anything in the second plot, it's displayed off to the side. The layout differences does make it a little difficult to compare the two plots. Let's make one more plot.

f3 = figure;
p3 = plot(Gm17, 'XData', p1.XData, 'YData', p1.YData);
title('Bucky graph minus edges connected to 17, nodes in the same place')

To keep node 17 (and the rest of the nodes) in the same place as in the first plot, the third plot uses the node coordinates from the first. If you quickly switch between the first and third figure, the only differences should be the title, the three edges that are present in the first but not the third, and the tick labels on the axes (which are present because I explicitly specified coordinates when I created the third plot.) As a warning, the code below will flicker quite a bit.

for k = 1:1000
    figure(f1)
    drawnow
    figure(f3)
    drawnow
end