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.
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)