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:
• 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:

## 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)
0076     else
0077         % otherwise, note that xy and all edges on P cannot be cut edges
0080         for j=1:length(P)-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