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.

Â