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