Description of bridges

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:

• add add --- add edge(s) to the graph
• copy copy(g,h) --- overwrite g with a copy of h
• delete delete --- delete vertices or edges from a graph
• edges edges(g) --- list the edges in g as a 2-column matrix
• find_path find_path(g,u,v) --- find a shortest path from u to v
• free free(g) --- free the graph from the system
• full full(g) --- convert internal storage for g to full
• graph graph: constructor for the graph class
• has has --- check if the graph has a particular vertex or edge
• incidence_matrix incidence_matrix(g) --- return the vertex/edge incidence matrix.
• ne ne(g) --- number of edges in g or ne(g,h) --- check for inequality

This function is called by:

SUBFUNCTIONS

• function blist = matrix_bridges(g)
• function blist = path_bridges(g)

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 Thu 13-Mar-2008 14:23:52 by m2html © 2003