Transcript ppt

Using a Directed Graph
Drozdek Chapter 8
1
Objectives
You will be able to
 Understand and use a C++ ADT for a
directed graph.
 Describe and implement an algorithm for
finding the shortest path between two
nodes in a directed graph.
2
New Project
3
New Project
4
Implementation of a Directed Graph ADT


Download to project directory:
http://www.cse.usf.edu/~turnerr/Data_Structures/Downloads/
2011_04_25_Directed_Graphs/



Digraph.h
shortest_path.cpp
NetworkFile.txt

Delete .txt from the .h and .cpp files

Add the .h and .cpp files to the project
5
Implementation of a Directed Graph ADT

Examine Digraph.h

Adjacency list representation.

The Digraph is a vector of Vertex objects



Node ID is the index.
Element 0 is not used.
Each Vertex object has a data member


Template class T
A list of integers (Node IDs)

Nodes adjacent to this node.
6
NetworkFile.txt


Example: Digraph with string as template
parameter.
Class Digraph method read() sets up the
digraph with contents of a file.
7
NetworkFile.txt
1
First number in each list is the
number of adjacencies.
2
The then IDs of adjacent cities.
3
4
5
Note that Denver has an
adjacency to itself.
(Sight-seeing flight? )
6
7
8
8
Adjacencies in NetworkFile.txt
Bos
5
Chi
LA
4
1
Den
3
NY
6
SF
2
NO
8
Miami
7
9
template <typename T>
void Digraph<T>::read(ifstream & inStream)
{
Vertex vi;
int n;
// number of adjacent vertices
int vertex_id;
// the number of a vertex
Digraph<T>::read()
// Create a garbage 0-th value so real indices start with 1
digraph.push_back(vi);
while (true)
{
inStream >> vi.data;
if (inStream.eof()) break;
vi.adjacencyList.clear();
inStream >> n; // Number of adjacent vertices
for (int i = 1; i <= n; i++)
{
inStream >> vertex_id;
assert(inStream.good());
vi.adjacencyList.push_back(vertex_id);
}
digraph.push_back(vi);
}
}
Digraph<T>::display( )
template <typename T>
void Digraph<T>::display(ostream & out)
{
out << "Adjacency-List Representation: \n";
for (size_t i = 1; i < digraph.size(); i++)
{
out << i << ": " << digraph[i].data << "--";
for (list<int>::iterator
it = digraph[i].adjacencyList.begin();
it != digraph[i].adjacencyList.end(); it++)
out << *it << " ";
out << endl;
}
}
11
Depth First Search

Public method:
void depthFirstSearch(int start = 1);
...
template <typename T>
inline void Digraph<T>::depthFirstSearch(int start)
{
vector<bool> unvisited(digraph.size(), true);
depthFirstSearch(start, unvisited);
}
12
Internal Depth First Search Method
// Internal (recursive) depth first search method
template <typename T>
void Digraph<T>::depthFirstSearch(int start, vector<bool> & unvisited)
{
visit(digraph[start].data);
unvisited[start] = false;
// Traverse the adjacency list, performing depth-first
// searches from each unvisited vertex in it.
list<int>::iterator it;
list<int>::iterator begin = digraph[start].adjacencyList.begin();
list<int>::iterator end = digraph[start].adjacencyList.end();
for (it = begin; it != end; it++)
{
// check if current vertex has been visited
if (unvisited[*it])
{
// Do a depth first search from this vertex
depthFirstSearch(*it, unvisited);
}
}
}
13
The visit() Method
template <typename T>
void Digraph<T>::visit(T& node_data)
{
cout << node_data << endl;
}


A Virtual Method
Intended to be overridden in a derived class in
order to do something useful at each node.
14
get_digraph()
void get_digraph()
{
ifstream network_file;
while (true)
{
cout << "Enter name of network file: ";
string filename;
cin >> filename;
network_file.open(filename.c_str());
if (network_file.is_open())
{
break;
}
cout << "Could not open " << filename << endl;
cout << "Please try again" << endl;
}
digraph.read(network_file);
network_file.close();
cout << "The Digraph's adjacency list representation:\n";
digraph.display(cout);
cout << endl;
}
15
Initial main()
int main()
{
get_digraph();
cout << endl << "Normal termination" << endl;
cin.get();
cin.get();
return 0;
}
16
The Adjacency Lists
17
Depth First Search

Let's do a Depth First Search.
int main()
{
get_digraph();
digraph.depthFirstSearch();
cout << endl << "Normal termination" << endl;
cin.get();
cin.get();
return 0;
}
18
Depth First Search from LA
19
Depth First Search from LA
Bos
5
Chi
LA
4
1
Den
3
NY
6
SF
2
NO
8
Miami
7
20
Depth First Search from Boston

Do a depth first search from Boston.
int main()
{
get_digraph();
digraph.depthFirstSearch(5);
21
Depth First Search from Boston
22
Depth First Search from Boston
Bos
5
Chi
LA
4
1
Den
3
NY
6
SF
2
NO
8
Miami
7
23
Providing Our Own Visit Method


Add derived class Digraph2.h
http://www.cse.usf.edu/~turnerr/Data_Structures/Downloads/
2011_04_25_Directed_Graphs/

Delete the .txt
24
Digraph2.h
#pragma once
#include "digraph.h"
template <typename T>
class Digraph2 : public Digraph<T>
{
public:
void visit(T& node_data);
};
Override visit()
method in base class
template <typename T>
void Digraph2<T>::visit(T& node_data)
{
show_length(node_data);
}
25
In shortest_path.cpp
#include "Digraph2.h"
Digraph2<string> digraph;
void show_length(string name)
{
cout << "Length of " << name << " is "
<< name.length() << endl;
}
26
Own Visit Method
End of Section
27
Paths

Routing problems – find an optimal path in a
network



Example – a directed graph that models an
airline network



A shortest path in a digraph.
A cheapest path in a weighted digraph.
Vertices represent cities.
Arcs represent flights connecting cities.
Task: Find most direct route between two cities.

(Fewest flights)
28
Paths in Directed Graph

Most direct route



Shortest path.
Path from start vertex to destination vertex
with minimum number of arcs.
Search algorithm for a shortest path:


A minor modification of the breadth-first
search algorithm.
Do a breadth first traversal, keeping track of
the predecessor of each node reached.

Stop upon reaching the destination node.
29
Shortest Path Algorithm

Given a directed graph with nodes 1 to n, a
starting node ID, start, and a destination
node ID, dest:
 Let dist[] be an array of ints


Let pred[] be an array of node IDs.


dist[v] will hold the distance from start to
node v.
pred[v] will be the predecessor to node v on a
shortest path from start to dest.
Initialize dist[start] to 0 and dist[v] to
infinity for all other nodes.
30
Shortest Path Algorithm


Initialize vertex_queue as a queue of ints, initially
containing just the starting vertex ID.
While dest has not been visited and vertex queue
is not empty:


Remove the front item from the vertex queue as v.
For each node, w, adjacent to v:
 If dist[w] is infinity
 Set dist[w] to dist[v]+1
 Set pred[w] to v.
 Add w to the vertex queue.
31
Shortest Path Algorithm



At this point, either we have reached dest or we have
exhausted the possibilities.
If dist[dest] is infinity report failure.
Else
 Initialize a stack with dest.
 Initialize v as dest.

Do the following


Set v to pred[v]
Push v onto the stack

until v is start.

The stack now holds a shortest path from start to dest.
32
Implementation of Shortest_Path
In digraph.h
template<typename T>
vector<int> Digraph<T>::Shortest_Path(int start, int dest)
{
int n = digraph.size();
vector<int> dist(n, INT_MAX);
// Distance from start
vector<int> pred(n, 0);
// Predecessor on shortest path
int v; // The current vertex
queue<int> vertex_queue;
vertex_queue.push(start);
dist[start] = 0;
33
Implementation of Shortest_Path
while (dist[dest] == INT_MAX && !vertex_queue.empty())
{
v = vertex_queue.front();
vertex_queue.pop();
list<int>::iterator it;
list<int>::iterator begin = digraph[v].adjacencyList.begin();
list<int>::iterator end = digraph[v].adjacencyList.end();
for (it = begin; it != end; ++it)
{
int w = *it;
if (dist[w] == INT_MAX)
{
dist[w] = dist[v] + 1;
pred[w] = v;
vertex_queue.push(w);
}
}
}
34
Implementation of Shortest_Path
// Now reconstruct the shortest path if there is one
if (dist[dest] == INT_MAX)
{
cout << "Destination not reachable from start vertex\n";
return path;
}
stack<int> reverse_path;
reverse_path.push(dest);
v = dest;
do
{
v = pred[v];
reverse_path.push(v);
} while (v != start);
35
Implementation of Shortest_Path
vector<int> path;
while (!reverse_path.empty())
{
v = reverse_path.top();
path.push_back(v);
reverse_path.pop();
}
return path;
}
36
main()
int main()
{
get_digraph();
char response;
do
{
int start, destination;
cout << "Number of start city? ";
cin >> start;
cout << "Number of destination? ";
cin >> destination;
vector<int> path = digraph.Shortest_Path(start, destination);
if (path.size() > 0)
{
display_path(path);
}
else
{
cout << digraph.get_data(destination)
<< " is unreachable from "
<< digraph.get_data(start) << endl;
}
cout << endl << "More (Y or N)?";
cin >> response;
} while (response == 'y' || response == 'Y');
37
Try it!
38
Computing Shortest Paths
39
A Defect

What happens if we ask for the shortest
path from a city to itself?
40
A Defect
41
A Defect

What is the program doing?

What should it do?
End of Presentation
42