Home > matgraph > @graph > bridges.m

bridges

PURPOSE ^

bridges(g,algo) --- find all cut edges in g

SYNOPSIS ^

function blist = bridges(g,algo)

DESCRIPTION ^

 bridges(g,algo) --- find all cut edges in g
 algo specifies the algorithm. Current choices are these:

 'path'    Deletes each edge from the graph and checks if there is a path
           between its endpoints. A few tricks are employed so we don't
           have to check every edge.

 'matrix'  Uses a basis for the null space of the signed incidence
           matrix. 

 No decision yet on which of these is better as the default. 

 Main idea for the path code due to Mel Janowitz.

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function blist = bridges(g,algo)
0002 % bridges(g,algo) --- find all cut edges in g
0003 % algo specifies the algorithm. Current choices are these:
0004 %
0005 % 'path'    Deletes each edge from the graph and checks if there is a path
0006 %           between its endpoints. A few tricks are employed so we don't
0007 %           have to check every edge.
0008 %
0009 % 'matrix'  Uses a basis for the null space of the signed incidence
0010 %           matrix.
0011 %
0012 % No decision yet on which of these is better as the default.
0013 %
0014 % Main idea for the path code due to Mel Janowitz.
0015 
0016 DEFAULT_ALGORITHM = 'matrix';
0017 
0018 if nargin < 2
0019     algo = DEFAULT_ALGORITHM;
0020 end
0021 
0022 switch lower(algo)
0023     case {'path', 'paths'}
0024         blist = path_bridges(g);
0025     case 'matrix'
0026         blist = matrix_bridges(g);
0027     otherwise
0028         error(['Unknown algorithm: ', algo]);
0029 end
0030 
0031 function blist = matrix_bridges(g)
0032 % Based on the following observation. Let M be the signed incidence matrix
0033 % of the graph. An edge e is a bridge of g if and only if every vector in
0034 % the null space of M has a 0 in the e'th coordinate.
0035 
0036 M = full(incidence_matrix(g,'signed'));
0037 N = null(M);
0038 
0039 % find rows that are entirely zero (or nearly so)
0040 N = abs(N) < 100*eps;
0041 idx = all(N,2);
0042 
0043 blist = edges(g);
0044 blist = blist(idx,:);
0045 
0046 
0047 function blist = path_bridges(g)
0048 % Implement the path method for finding bridges
0049 
0050 bgraph = graph;     % hold the cut edges
0051 notbridges = graph; % hold the non cut edges
0052 gsave = graph;      % save a copy of g since our code modifies g
0053 copy(gsave,g);
0054 
0055 elist = edges(g);  % list of edges
0056 m = ne(g);         % number of edges
0057 
0058 for k=1:m
0059     % xy is the edge we're considering
0060     x = elist(k,1);
0061     y = elist(k,2);
0062     
0063     % if xy is in a cycle, we skip the rest of this iteration
0064     if (has(notbridges,x,y))
0065         continue
0066     end
0067     
0068     % find an xy-path in G-e
0069     delete(g,x,y);
0070     P = find_path(g,x,y);
0071     
0072     
0073     % if no such path, we have a cut edge
0074     if isempty(P)
0075         add(bgraph,x,y)
0076     else
0077         % otherwise, note that xy and all edges on P cannot be cut edges
0078         add(g,x,y);
0079         add(notbridges,x,y)
0080         for j=1:length(P)-1
0081             add(notbridges,P(j),P(j+1))
0082         end
0083     end
0084 end
0085 
0086 blist = edges(bgraph);
0087 
0088 % restore g
0089 copy(g, gsave)
0090 % release temporary storage
0091 free(bgraph)
0092 free(notbridges)
0093 free(gsave)

Generated on Fri 05-Feb-2010 13:55:18 by m2html © 2003