Alright, so I’ve redrawn the graph from the previous
examples just to make a little bit more room and
what we’ve got so far is the original graph and the –
a tree version of the graph that we built by search,
some kind of data depth-first, breadth-first – any kind
of search actually will do, as long as we now have
these green edges pointing downward and these red
no-tree edges connecting nodes that need to be
connected if the edge wasn’t actually part of this
tree. Then we post ordered the nodes and now what
do we do next.We now compute the number of
descendents for each node in the graph and the
number of descendents is the number of nodes that
are either the node or reachable from the node by
following green edges only. So this is easiest to start
at the bottom here, F has just the node itself and no
descendants, so it’s got a number of descendant of
one, same thing with G.E has one descendant, one
descendent plus itself for three. D has the three
descendants of E plus itself for four. C has the four
descendants of D plus itself is five. B has just itself
and A has B’s descendants, C’s descendants plus
itself for seven. So the next thing we’re going to
compute is for each of the nodes, we’re going to
consider the set of nodes that are descendants of
the node or reachable from the descendants of the
node by one hop of a non-tree edge and of all those
nodes that are reachable, we’re going to look at the
post-order value that is the smallest, we’ll call that L.
So in the case of F, F has itself and it also can reach
G, the smallest value there is two. G has no
descendants but it can reach by one red edge F. So
the smallest least values two and three is two. E has
F and G and itself that it can reach no other nodes
by non-tree edges and the smallest of those
numbers is two. D can reach all of these nodes in
itself but also by a non-tree edge it can reach this
node and the smallest of those numbers is one. C
can reach all of these nodes and through one of
those nodes one tree edge gets it to one. B values
itself as one so that’s going to be the smallest. And
A includes everything, so that’s going to include the
one, so that’ll be the smallest. H is the same idea
except of those that same set that we computed for
L, we want to know the largest value. For G between
F and G the largest value is three. For E between E,
F and G the largest value is four. For D, D,E,F, G
and B reachable by a red edge, the largest value is
itself five. C same set for adding in C now and the
largest value becomes six and A set contains
everybody so that’s going to include itself with the
value of seven. Alright, now we’ve decorated these
nodes with lots of interesting numbers, now we can
get to the last step. So given all these nicely
decorated nodes, we now have a rule for figuring out
which ones are the bridge edges and this is the rule.
All the bridge edges are ones that are green, they
have to be three edges and the green number is
less or equal black number and the red number is
bigger than the blue number minus the black
number or in words the – each value has to be less
or equal to the post order value, the lowest value
has to be bigger than the number of descendants
minus the post order value. So apart from the fact
that it’s not immediately obvious why this is the right
rule let’s apply it to the tree to see what gets picked
out. So, what we’re doing here is we’re looking at
each green edge and we’re checking the numbers
on the downward part of the edge. So here is a
green edge and let’s look at the numbers here and
see if they fit the pattern. We need the green
number to be less or equal to the black number. So
that doesn’t work, right. Here is another green edge.
You need the green number to be less or equal to
the black number, oh that works. So the red number
needs to be bigger than the difference between the
black and the blue. So black and the blue the
difference is two. The red number is two, so that
doesn’t work. Alright next edge to check is this one,
so we need to check is green less or equal to black,
yes. Is red bigger than black minus blue? Two is
bigger than one, so yes. So this edge has been
identified as a tree edge. That’s the right answer and
none of the other edges are tree edges but let’s just
check them just to be sure. For this edge, we have –
we need green to be less or equal to black which we
have. And we need red to be bigger than the
difference between blue and black but one is not
bigger than one, so this edge is out. How about this?
We need green less or equal to black, yes. We need
red bigger than the difference, no. Green number is
five because the D node is reachable by a non-tree
edge. Alright, so green less or equal to black, no.
Alright, well that’s it. Those are all the edges. So in
this example anyway the one edge that the
algorithm finds is exactly the bridge edge. Can we
get a handle on why this works? It seems kind of
magic at this point.