0:00
. To develop. Digraph processing Algorithms, we're going to need an A.P.I.
We'll use the same design pattern that we use for undirected graphs, where we
develop an A.P.I. for building graphs that can serve as a client for all our graph
processing algorithms. And it's very similar, it's not close to identical to
the undirected graph A.P.I., except the class is named digraph. And other than
that. It's got add edge, where we add a directed edge. But now, we're saying it's
an edge from V to W. and then an iterator. that gives the vertices that point from
the given vertex. So we're getting, those were the edges we can travel along to get
around the graph. We have V and E. and another new method that is not relevant
for undirected graphs is the reverse. So that's, a, a method that returns a
di-graph where all the edges are reversed. and we'll see that's an important method
to have for one of the algorithms that we'll talk about today. so here's a
typical client very similar to the one that we did for undirected graphs, where
we read the diagram from input stream, so that's pairs of edges, pairs of vertices
where, that represent an edge from or one vert, first vertex to the second one And
then for every vertex we'd print out. for every edge that you can get to from that
verte-, for every other vertex you get to from that vertex, we put out a,, print out
a little graphical representation of the edge V2W, where the little arrow we use a
minus sign and a greater than. So for example with the input file tinyDG.txt for
directograph, the one's got thirteen vertices, 22 edges. It's got an edge from
four to two, from to two to three, three to two and so forth and if we execute this
sample client, we get the edges printed out. it builds the graph and then prints
out the edges. By the way, the order in which they come out is in order of vertex
and order in which the judge comes out depends on the representation just these
four graphs. we'll skip through the possibilities of keeping a list of edges,
or using a matrix for, diagr aphs, cause again. impractical problems, the graphs
are huge and sparse, so the average vertex degree in-degree and out-degree is low. We
can't afford, to, keep space proportional to the number of possible vertices, that a
vertex can connect to for each vertex. so, it's very similar to or exactly the same,
really, to the one that we use for undirected graphs. We keep a vertex
indexed array. Where, for each vertex, we can keep a bag of all the vertices that
you can get to from that vertex. So vertex six, has out degree four. And there's four
vertices on its list. Nine, four, eight, and zero. And when we process the graph,
we're gonna visit those vertices, in that order. Which is just determined by the
order in which they appeared in the input. So here's the implementation that we used
for un-directed graphs last time. and you'll see that the only difference for
die graphs is we change graph to die graph and we only have one representation of
each edge, V goes to W. for undirected graphs we had W goes to V as well,
otherwise the code's exactly the same, we have an iterator for the vertices adjacent
to V but that. It's the difference between directed graphs and undirected graphs. so
again the reason we do that is that we can get basic graph processing processed in a
reasonable amount of time. Where every time we deal with a vertex we can get to
its neighbors are the places you can get to from that vertex in time proportional
to the number of vertices. You simply can't afford to do that with other
representations. So that's the digraph API. Which is virtually identical to the
graph API.
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Kevin WayneSenior Lecturer
