0:03

Today, we're, we're going to look at the vector graphs, which is another graph

Â processing model that's very useful in many applications.

Â It's very similar to the undirected grpah model that we looked at last time, but

Â there are some really profound differences.

Â After introducing the concept and looking at the API, we'll look at three important

Â classic algorithms for processing directed graphs.

Â The intro, introduction has to deal with just explaining the concept and seeing

Â what it does to our graph processing problems like the ones that we talked

Â about for undirected graphs last time. So, the idea isn't that the edges now have

Â direction. A directed graph or a digraph is a set of

Â vertices that are connected pairwise by directed edges.

Â So, it's list of pairs of vertices where the order of the pair matters.

Â So, an edge we say an edge goes from one vertex to another one. whereas, in

Â undirected graphs, we just talked about connections.

Â When we're processing such graphs or travelling around them, we have to follow

Â edges in the given direction. So, for example, if we talk about a path

Â in the diagram there's, it looks like there's a connection between two and zero,

Â but it only goes from two to zero. If you want to go from zero to two, you

Â have to follow the edges in direction going from zero to five to four and then

Â to two. In the directed graph, in this digraph you

Â can see two directly from zero. Similarly, a directed cycle follows the

Â edges around the direction to get back to the original vertex. also vertices have

Â in-degree and out-degree in digraphs. And the out-degree, obviously, is the

Â number of variables leaving the vertex and in the in-degree is the number of

Â variables coming into the vertex. Those are the basic definitions. let's

Â look at a couple of applications one obvious one is road networks where we put

Â a vertex according to intersection in an edge for roads.

Â And we look at a situation where most, where the roads are one way or can be one

Â way. So, if you've driven in lower Manhattan,

Â you're very familiar with this map, which has lots of one-way streets.

Â And it's not always clear how to get from one place to another.

Â You can have some two-way streets that have edges in both directions.

Â But with digraphs, we allow the abstraction of one-way streets.

Â 2:55

Although there are some orange links that go from blue to red and a few purple ones

Â that go from red to blue. And this gives some insight to the in the

Â political blogosphere at least in 2004. Here's another one.

Â This is a study of the crash in 2008, and it was a graph that showed the structure

Â of banks lending to one another. An edge corresponds from an overnight loan

Â and a vertex corresponds to the bank. And from studying this diagram, experts

Â can see how the banks divided into groups and were therefore vulnerable in these

Â groups and we'll look at a more detailed definitions of how these groups are

Â defined a little later on. This is just an example of the use of a

Â digraph. And it's a digraph, the bank.

Â One bank lends money to another, that's not the same as the banks being connected,

Â in some as in an undirected graph. The direction really matters.

Â This is another one from logic where the vertices correspond to Boolean variables

Â and the edges correspond to implication. And people use graphs like this to study

Â in, in logical verification, and also studying electric circuits.

Â Electric circuits themselves can be diagraphs where circuit elements have

Â input and output. And so, the edge of course takes the

Â output of one element to the input of another.

Â Trying to understand the behavior of such a circuit involves processing a digraph.

Â Here's another abstraction so-called wordnet graph.

Â Where vertices correspond in what is called synsets and edges correspond to

Â hypernym relationships where a, a word is an instance of another one.

Â So, there's a lot of different events like a miracle or human activity and so forth.

Â And graphs of this type are very useful in studying applications involving meanings,

Â meanings in human languages. Here's a famous one.

Â General McChrystal said that once we understand this graph the war in

Â Afghanistan will be over. So, with all these types of applications

Â and there's many, many others just as with graph processing.

Â Now, the digraph as it, as it is modeled distinct from graph processing is

Â important. There's many direct applications where we

Â have connections between objects but the direction of the connection matters.

Â So, what about digraph processing algorithms.

Â Well, we're going to look at many problems that are very similar to the ones that we

Â looked at for undirected graphs. But you can see that they are going to be

Â a bit more complicated. Even a human has trouble looking at a

Â diagraph trying to figure out a simple problem like, is there a path from s to t

Â in this, in this diagraph. Seems like there's quite a few

Â possibilities to consider to convince yourself whether or not there's a path.

Â And for the huge diagraphs examples that I looked at before obviously we're going to

Â need a computer program. And we're going to have a bit of a

Â challenge figuring what's going on. Of course, you might want to know the

Â shortest directed path from s to t for example, if you are driving around lower

Â Manhattan and certainly, I want to have a solution to that problem.

Â Then, there's another problem called the topological sort problem which is a

Â general model that's useful in all kinds of applications where were scheduling

Â events that involve precedence constraints.

Â In the graph obstruction or the digraph obstruction, it amounts to the problem of

Â trying to draw the digraph so that all the edges point up.

Â That's called topological sorting. And then, connectivity is more complicated

Â for digraphs than for undirected graphs. There's the concept of strong

Â connectivity, which means for any given pair of vertices u and v, you want to know

Â is there going to be a directed path from u to v and another directed path from v to

Â u. That's a much more complicated problem

Â than connectivity in undirected graphs. And, a generalization of, of that or a

Â query related to strong connectivities, so-called transitive closure.

Â And for that, you just want to be able answer the query given vertices v and w as

Â their path from w to v, a transitive closure.

Â And actually, you're familiar with the web is a gigantic directed graph.

Â If there's a link from page a to page b, B, that's a directed edge.

Â And digraph processing is used in famous page rank algorithm to determine the

Â importance of a web page. Those are just a couple of examples of

Â digraph processing problems that introduce the idea.

Â