Directed Graph Code Example

●
This example code will create the graph from a
file – overall it is like the undirected graph
●
The file will first contain an integer for the
number of vertices
●
The second number is the number of edges
●
Each vertex is one per line
●
Once the vertices and edges are taken in, then
the next piece is to show all of the adjacent
vertices – with direction
 Directed Graph Code Example
●
In this coding example, it expects to see the
vertices followed by the edges
●
This data can be stored multiple ways and
using multiple techniques
●
In this example we will use a file
●
The following are the two lines in the file
 Directed Graph Code Example
●
Once the first two lines are read, then the rest
of the file is the graph that we are creating
●
The file must have as many lines as the number
of vertices (13) – Like undirected graph
●
We will use arrays to store this
●
The arrays will be used so the index will start
with 0 and go up to 12
 Directed Graph Code Example
●
Like the undirected graph, the constructor will
show all of the adjacent vertices
●
The additional piece is indegree which gives the
graph directionality – see code below
 Directed Graph Code Example
●
In the case of a directed graph, the order of the
edges matter
●
The indegree will validate the vertex and then
recursively call itself
●
When there is an edge, then it is assumed that
the it goes from the vertex in the array and to
the vertices in the list
●
It is assumed that it goes in a direction
 Graph Code Example
●
In this example, we use a Bag as the data
structure to store the graph – like an undirected
graph
●
The bag is good for this implementation
because bags don’t rely on order
●
Anything can be deleted or created from the
bag
●
The code will go through the file and then
create the edges and vertices using the bag
and the array
 Directed Graph Code Example
●
The code that we brought up in the prior slide
has the bag
●
The code is repeated below
 Directed Graph Code Example
●
The bag has all of the vertices
●
Once the vertices are created, we need to
create the edges
●
In the case of this code, the edges then are
created in a particular order in a stack
●
The stack is reversed so the graph is in the
order of the text file
 Graph Code Example
●
The edges list is done with a for loop like the
vertices
●
In this case we have 22 edges just like the
number of vertices
 Directed Graph Code Example
●
Once the graph is generated, then we format
the graph so that it is readable
●
The toString method in the Graph class does
this formatting
●
It will convert the integers to a string and be
able to label pieces like vectors and edges
●
The toString method is over loaded. If it is of a
graph type than this one is called
 Directed Graph Code Example
●
In a similar way, the println is also over loaded
in StdOut – Like Undirected
●
The println(G) is a graph
●
Over loading the operators is nice because it is
an easy way to convert items to strings and
print out the graph
●
The developers must be aware of this because
it can cause confusion
 Directed Graph Code Example
●
The toString method is in the Graph class
●
An excerpt is as follows (Like Undirected)
 Directed Graph Code Example
●
The println that is overloaded is in StdOut
●
In this case, the generic Object is the ID
●
The Object is the parameter and will be bound
at run time
●
Other printlns are in the class for other types
 Directed Graph Code Example
●
The main will just create the graph and print out
the graph
●
The main will take an argument that is the file
name
●
Then process the file
 Directed Graph Code Example
●
These are the basics of the graph but there are
other key methods in the Graph class
●
The first one is the ability to return all of the
vertices from the graph
●
The code… Just like undirected graph
 Directed Graph Code Example
●
Additionally we can return the edges
●
A developer may need the list of edges to
understand how to create paths
●
If the edges are to be returned, then the
following code will return the edges (Like
Undirected)
 Directed Graph Code Example
●
Another method is to validate a vertex
●
The vertex is between certain numbers when
loaded
●
In this case the highest vertex is 12
●
We can validate if a given vertex exists with the
following code (Like undirected)
 Directed Graph Code Example
●
Once the file is loaded with the graph, we can
add more edges to the graph
●
It may be important to edit the graph based on
different algorithms that we need to generate
●
Keep in mind we are not adding a vertex (Like
Undirected)
 Directed Graph Code Example
●
One difference is there is not a degree method
●
Degree is simple with an undirected graph
●
The indegree becomes a part of the directed
graph and can be used for degree as well
●
Since things can only go one way – then the
degree is implicit in the graph
 Directed Graph Code Example
●
Consider the following directed graph…
●
 Directed Graph Code Example
●
File from previous example
 Graph Algorithms
●
The remainder of today and into next week we
will work through some graph algorithms
●
We discussed some graph problems and
needed tasks with graphs
●
Things like searching, finding paths and other
needed tasks
 Graph Algorithms
●
The first one we will discuss is depth first
search
●
This discussion will examine a depth first
search from a general point of view
●
Depth first searches are done with both
undirected and directed graphs
 Graph Algorithms
●
Depth first search will visit the first vertex in a
graph
●
Then it will mark that vertex and recursively call
the depth first search method on all the vertices
adjacent to the vertex it is on
●
It will continue the recursive calls until all of the
vertices have been visited (That can be visited)
 Graph Algorithms
●
With depth first search, we can search and
understand edges that have paths to the
starting vertex
●
Another use case is to search for a specific
vertex
●
If searching for a specific vertex then depth first
search would complete when the vertex is
found
●
Or it will return false if the given vertex does not
exist after a full search is completed
 Graph Algorithms
●
As discussed, an undirected graph can be
thought of as a directed graph with every edge
going in both directions
●
If we think of directed and undirected graphs in
this way, then depth first search is an identical
algorithm for both directed an undirected
graphs
●
The only difference is that in a directed graph
certain vertices are not adjacent because the
edge goes the wrong direction
 Graph Algorithms
●
Thinking about the graph below…
 Graph Algorithms
●
If the graph was undirected then 0 points to 1,
2, 6, and 5
●
But in the directed graph it is only pointing to 1
and 5
●
Depth first search in a directed graph will not
search through the entire graph
●
It will only search through edges that has a path
from the starting vertex in a directed graph
●
In an undirected graph, if I start a search I know
I can search the entire graph