matlab: check which lines of a path are used - graphshortestpath

The related problem comes from the power Grid in Germany. I have a network of substations, which are connected according to the Lines. The shortest way from point A to B was calculated using the graphshortestpath function. The result is a path with the used substation ID's. I am interested in the Line ID's though, so I have written a sequential code to figure out the used Line_ID's for each path.

This algorithm uses two for loops. The first for-loop to access the path from a cell array, the second for-loop looks at each connection and searches the Line_ID from the array.

Question: Is there a better way of coding this? I am looking for the Line_ID's, graphshortestpath only returns the node ID's.

Here is the main code:

for i = i_entries
    path_i = LKzuLK_path{i_entries};
    if length(path_i) > 3 %If length <=3 no lines are used.
        id_vb = 2:length(path_i) - 2;
        for id = id_vb 
            node_start = path_i(id);
            node_end   = path_i(id+1);
            idx_line = find_line_idx(newlinks_vertices, node_start, ...
                node_end);
            Zuordnung_LKzuLK_pathLines(ind2sub(size_path,i),idx_line) = true;
        end      
    end 
end

Note: The first and last enrty of path_i are area ID's, so they are not looked upon for the search for the Line_ID's

function idx_line = find_line_idx(newlinks_vertices, v_id_1, v_id_2)
% newlinks_vertices includes the Line_ID, and then the two connecting substations
% Mirror v_id's in newlinks_vertices:
check_links = [newlinks_vertices; newlinks_vertices(:,1), newlinks_vertices(:,3), newlinks_vertices(:,2)];
tmp_dist1 = find(check_links(:,2) == v_id_1);
tmp_dist2 = find(check_links(tmp_dist1,3) == v_id_2,1);
tmp_dist3 = tmp_dist1(tmp_dist2);
idx_line = check_links(tmp_dist3,1);
end

Note: I have already tried to shorten the first find-search routine, by indexing the links list. This step will return a short list with only relevant entries of the links looked upon. That way the algorithm is reduced of the first and most time consuming find function. The result wasn't much better, the calculation time was still at approximately 7 hours for 401*401 connections, so too long to implement.

Answers


I would look into Dijkstra's algorithm to get a faster implementation. This is what Matlab's graphshortestpath uses by default. The linked wiki page probably explains it better than I ever could and even lays it out in pseudocode!


Need Your Help

How Can I Draw Image with Text Wrapping on iOS?

objective-c ios uitableview nsstring core-text

I want to draw text just like the following style -- the image is always on the top right corner, and the text is around the image.

Magento transaction error "Please specify a shipping method"

magento magento-1.5

We use a custom checkout extension by Templates Master called "Firecheckout". Not sure if that's relevant, but figured I should mention it. Occasionally I see a transaction failed email with the ...