Directed Graphs

●
Last week we discussed undirected graphs
●
They are graphs that can go in either direction
●
This week we are going to discuss directed
graphs
●
As the name implies, a “Digraph” or directed
graphs is one where the vertices are connected
by pairs but also go in one direction
●
They are notated with arrows
 Directed Graphs
●
Example of a graph
 Directed Graphs
●
A directed graph will limit the paths that can be
taken because we have to consider direction
●
In the previous example, the path from A – I goes
through F.
●
However, if we go from I – A then we need to go
through G instead
●
As shown in the example, a directed graph can
have two ways as well
●
That is noted by having an arrow on both sides
 Directed Graphs
●
Real life examples of directed graphs

If we use the above map and there are one-

way streets then the one-way streets are an
example of a directed graph
 Directed Graphs
●
In computer science, an implication graph is an
example of a directed graph
●
An implication graph is an example of if – then –
else statements
●
If something is true – then go one directed
direction
●
If it is not true, then go another direction
●
These are example of implications. Because if
something happens, then there are “implications”
 Directed Graphs
●
An example implication graph from sedgewick
below:
 Directed Graphs
●
Some example discussion…
●
If x6 is true then x5 is true
●
Likewise if one is false then the other is false
●
A developer can traverse the graph and if certain
things are true, then it follows that the pieces
where they are directed are true as well
●
Thus the name “implication” graph
●
If something is true then where it is directed has
the implication of being true as well
 Directed Graphs
●
Circuits and gates are examples of directed
graphs
●
In this case, a gate is a vertex
●
The wire is an edge
●
Circuits go one way through a gate
●
Thus they are directed graphs
 Directed Graphs
●
Sedgewick example of a circuit diagram
 Directed Graphs
●
In the circuit diagram in the previous example,
there are five gates
●
The gates are examples of vertices
●
The wires are the edges
●
The gates have logic within them, thus the
different shapes
●
However, the direction goes from left to right
●
The wires go into the gates and then one wire
comes out
●
This is a directed graph
 Directed Graphs
●
A data flow diagram is a form of a directed graph
●
The data begins in a source system
●
Based on certain events, the data will flow into
target systems
●
Only in small focused cases, will data be loaded
back into the source
●
However, that is just a two way directed graph
●
As the data flows it will move from source to
target
 Directed Graphs
●
List of directed graph examples
●
Transportation – Intersections are vertices, one-
way streets are directed edges
●
Web – web page is the vertex, hyperlink is the
edge
●
Scheduling – Task is a vertex, precedence
constraint is the directed edge
●
Financial – the bank is the vertex, the transaction
is the directed edge. Deposits go one direction,
withdrawals go another
●
Board Game – Board Position is the vertex, legal
move is the directed edge
 Directed Graphs
●
Some vocabulary around directed graphs
●
There is some that is the same as undirected
graphs
●
There are items that are new as well
●
It is important to work through the vocabulary so
we all can be on the same page
●
A simple one that is also in undirected graphs is
PATH. This will be a method that returns true or
false if there is or isn’t a path
 Directed Graphs
●
Shortest Path (Also in undirected graphs) – This
is the shortest path between A and B
●
Topological Sort (Only Directed) – Can a digraph
be drawn so all of edges point upwards
●
Strong Connectivity (Across the graph) – Is there
a directed path between all pairs of vertices
●
Transitive Closure – For which vertices is there a
path between v and w and w and v
 Directed Graphs API
●
We will go over from a general stand point some
example APIs with a directed graph
●
We will go over specific code examples on
Thursday
●
Today we will discuss from a general standpoint
what we will want to do with directed graphs
specifically
●
From a general stand point how these things will
get done
●
They can be done in any language
●
We will of course show them in Java on
Thursday
 Directed Graphs API
●
Like the undirected graphs, we will use a file
●
However, the file will have the idea of direction
●
We could have up to two lines for the same to
pairs
●
An example is 2 → 3 and 3 → 2
●
If the above is an undirected graph, we only
need one entry in the text file
●
In the example in a directed graph, we need two
because it is a two way example
●
However, 0 → 1 is one way so it will only have
one entry as an example
 Directed Graph APIs
●
In order to store directed graphs, maintain an
array of lists again
●
Where something is in the list makes a different
because of the direction
●
The array itself is the vertices
●
The edges are the list
●
Once again in the 2 → 3 and 3 → 2 example,
there is a 3 in the list from the 2 index then 2 in
the three index
●
However, if it is one way then the pair will only be
represented once
 Directed Graph Search APIs
●
Common computer science problem is
reachability
●
If we have a vertex s, what are all of the
reachable vertices from s in a directed way
●
All of the paths must be searched from s
●
As the path moves through the graph, then the
vertex list will be added
●
Once all of the directed paths and vertices are
discovered, the method returns the list of vertices
 Directed Graph Search APIs
●
An example from Sedgewick
 Directed Graph Search APIs
●
S is the upper left vertex
●
Due to the graph being directed, there is not
even a path to the vertex right below S
●
Even if the path starts by going right and working
through, there is no way to get to the vertex
below
●
The only reachable vertices are the vertices that
are in the shaded blue region
 Directed Graph Search APIs
●
With a digraph, we can use the same method as
with an undirected graph
●
An undirected graph is just a digraph that goes in
both directions
●
We mark the vertex we are on as visited, then
recursively call with all unmarked vertices
●
Once the vertices run out because nothing else
is reachable we are done
●
We then return all of the marked vertices
Directed Graph More Programming
Examples
●
Every data structure is a digraph
●
The vertex is the object
●
An edge is a reference
●
The reference is directed and can only go in one
direction
●
If something cannot be referenced then it is not
reachable
●
Objects that are indirectly accessible are still
reachable but just have to follow the chain of
pointers
 Directed Graph More Programming
Examples
●
Garbage collection is a directed graph example
●
Java does garbage collection
●
C and C++ does not do garbage collection
●
When garbage collecting the method will go
through and mark all reachable objects
●
The reachable objects are memory that is
needed
●
If something is not reachable then it is garbage
●
That memory can be freed at that point and
added to any free lists
 Directed Graph More Programming
Examples
●
Shortest path with a directed graph
●
Lets take the example below

●
Let S be in 1, 7, 10
●
Shortest path to 4 is 7, 6, 4
●
We cannot do adjacent to 4 because none of
them are in S
 Directed Graph More Programming
Examples

●
Application of breadth first search is a root web
page (www.northeastern.edu)
●
That is a source s
●
Then maintain a queue of websites to explore
●
Maintain a SET of discoverable websites
●
Dequeue the next website, enqueue the
websites to which it links
 Directed Graph More Programming
Examples
●
Graphic representation of web example
●
1 is the root
 Directed Graph More Programming
Examples
●
The above graph is a web crawler
●
Not everything is reachable by the root
●
Those are then labeled as such
●
What is reachable is marked as well
●
When we go through examples, we will start out
as simple as possible and just do the bare bones
web crawler
●
Of course it can be built up as more needs are
known