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