数学建模论文COEN 244 Project Description
Introduction
As an engineer or scientist, one might often want to create robust data structures to model
mathematical problems. One simple, useful and well known model is Graph. A graph will allow
you to define objects and object relations and therefore perform various tasks, such as search,data rearrangement, simulation, reasoning, prediction and much more.
The purpose of this project is for you to
• Make a simple graph library around a set of given nodes and produce graph objects
• Produce various representations and use the one that is appropriate for each of the algorithms
you will have to develop
• Develop different search strategies on a given graph
• Use search strategies to perform various tasks such as finding shortest path between two
nodes or detecting cycles along a given path
Definitions
A graph is an abstract representation of a set of objects where some pairs of the objects are
connected by links. The interconnected objects are represented by mathematical abstractions
called vertices, and the links that connect some pairs of vertices are called edges. Typically, a
graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves
for the edges. Two nodes are adjacent if they have an edge in common.
An example: The figure defines graph G = {V, E} as follows
6 vertices: V = {1, 2, 3, 4, 5, 6}
7 edges: E = { {1,2, 0}, {1,5, 0}, {2, 3, 0}, {2, 5, 0}, {5, 4, 0}, {4, 3, 0}, {4, 6, 0} }
Figure 1: Example Graph
For instance, edge {1,2,0} represents an edge, connecting node 1 and node 2. Weight of this
edge is 0.
A Path in a graph is a sequence of vertices such that from each of its vertices there is an edge
to the next vertex in the sequence. A path may be infinite, but a finite path always has a first
vertex, called its start vertex, and a last vertex, called its end vertex. The other vertices in the
path are internal vertices.
Weighted graph: A weighted graph associates a weight with every edge in the graph. Weights
are usually real numbers. They may be restricted to rational numbers or integers. Certain
Page 1 of 6
algorithms require further restrictions on weights; many work only on positive weights. (1,3, 5)
could represent an edge connecting vertex 1 to vertex 3 and the weight associated to this edge
is 5. For this project we are dealing with weighted graphs.
A cycle is a closed path in which a vertex appears more than once (i.e. the start and the end
vertices are the same).
A Connected Graph is a graph in which there exists at least one path between any and every
pair of nodes.
An Adjacency list representation is a representation of all edges as a list. The following is the
adjacency list representation of the graph in fig. 1.
1 : 2,5
2 : 3,5,1
3 : 2,4
4 : 3,5,6
5 : 1,2,4
6 : 4
An Adjacency matrix representation of a finite graph G on n vertices is the n × n matrix where
the non-diagonal entry Aij is the number of edges from vertex i to vertex j, and the diagonal
entry Aii, depending on the convention, is either once or twice the number of edges (loops) from
vertex i to itself. For example the following is the adjacency matrix of the graph in fig. 1.
Ver te
x
1 2 3 4 5 6
1 0 1 0 0 1 0
2 1 0 1 0 1 0
3 0 1 0 1 0 0
4 0 0 1 0 1 1
5 1 1 0 1 0 0
6 0 0 0 1 0 0
Table 1: Adjacency matrix representation of graph in fig. 1
Breadth First Search (BFS) is one of the simplest algorithms for searching a graph. Given a
graph G = (V, E) and a distinguished source vertex s, breadth-first search systematically
explores the edges of G to “discover” every vertex that is reachable from s. Breadth first search
is so named because it expands the frontier between discovered and undiscovered vertices
uniformly across the breadth of the frontier. That is the algorithm discovers all vertices at
distance k from s before discovering any vertices at distance k+1.
1. Enqueue the root node.
2. Dequeue a node and examine it.
• If the element sought is found in this node, quit the search and return a result.
• Otherwise enqueue any successors (the direct child nodes) that have not yet been
discovered.
3. If the queue is empty, every node on the graph has been examined – quit the search and
return "not found".
4. Repeat from Step 2.
Pseudocode:
1 procedure BFS(Graph,vertex):
2 create a queue Q
3 enqueue vertex onto Q
4 mark vertex
5 while Q is not empty:
6 dequeue an item from Q into v
7 for each edge e incident on v in Graph:
8 let vertex w be the other end of e
9 if w is not marked:
10 mark w
11 enqueue w onto Q
Tasks
Your program is expected to have the following functionalities:
• Load information of an initial graph from a source file graph.txt from current directory. This file
will provide enough information to construct an initial graph G = { V, E } and produce a valid
graph object (see graph.txt). A graph object has at least two main attributes. One is a set of
vertices where each vertex is a C++ construct. Each edge could look like (1,2, 10) . This will
allow you to keep track of the weight associated with that edge.
• The graph object that is now created must be able to perform a few basic operations (graph
manipulations)
• bool adjacent(Vertex struct1, Vertex struct2): to test whether vertex objects are adjacent
• vector <Vertex> neighbors(Vertex v) to list all adjacent vertices to v
• bool addEdge(Vertex v1, Vertex v2) to add an edge between v1 and v2 if it is not already
there
• bool deleteEdge(Vertex v1, Vertex v2) to delete an edge if it already exists
• int getEdgeValue(Vertex v1, Vertex v2) to return the weight of edge connecting v1 and v2.
You can assume there is at most one edge between any two vertices
• void setEdgeValue(Vertex v1, Vertex v2) to update weight associated to the edge
connecting v1 and v2
• bool isConnected() to test whether the current graph is connected or not
• Develop the breadth-first-search( ) algorithm so that you can search a graph for specific
information. For instance to find all possible paths from a source vertex to a destination vertex.
Your search method must print out all paths that it finds at each step.A breath first search from
vertex 1 to vertex 6 through the graph of our example would produce following paths at each
step. Note that at each step k the distance between the currently visiting node from the root
node is equal to k.
Page 3 of 6
Step 1:
1 -> 5
1 -> 2
Step 2:
1 -> 5 -> 2
1 -> 5 -> 4
1 -> 2 -> 5
1 -> 2 -> 3
Step 3:
1 -> 5 -> 2 -> 3
1 -> 5 -> 2 -> 1 (cycle)
1 -> 5 -> 4 -> 6 (solution)
1 -> 5 -> 4 -> 3
1 -> 2 -> 5 -> 1 (cycle)
1 -> 2 -> 5 -> 4
1 -> 2 -> 3 -> 4
Step 4:
1 -> 5 -> 2 -> 3 -> 4
1 -> 5 -> 4 -> 3 -> 2
1 -> 2 -> 5 -> 4 -> 6 (solution)
1 -> 2 -> 5 -> 4 -> 3
1 -> 2 -> 3 -> 4 -> 6 (solution)
Step 5:
1 -> 5 -> 2 -> 3 -> 4 -> 6 (solution)
1 -> 5 -> 4 -> 3 -> 2 -> 5 (cycle)
1 -> 5 -> 4 -> 3 -> 2 -> 1 (cycle)
1 -> 2 -> 5 -> 4 -> 3 -> 2 (cycle)
As you can see, cycles are also detected during this search process.
• The program must also be able to generate random connected graphs of size 1 to 256 nodes.
Your edges must be randomly generated (Hint: an undirected graph with n nodes can have up
to n(n-1)/2 unique edges). The random graph must initialize edge weights randomly to an
integer value from [0, 10]
Sample run
Choose either option:
1-Generate random graph
• Enter number of nodes:
2-Load graph
• Graph.txt loaded
Now you have either generated or loaded a graph object . . .
Main menu:
Choose one of the following operations:
1-Print adjacency matrix representation
2-Print adjacency list representation
3-Print Graph information
• List of Vertices, Total number of vertices, List of edges and
their weights, Total number of edges
4-Print adjacent node
• Ask for name of a node, and print all its adjacent nodes.Node
names are of type string
5-Add edge
• Ask user for 2 vertices and an integer weight value. You must
handle cases where the edge already exists properly to preserve
uniqueness of edges
6-Delete edge
• Ask user for two vertices and remove the edge if it already exists
7-Search for all paths from source to destination
• Ask for 2 vertices and print all possible paths between these
two. Print sum of weights of each path at each iteration step as
well.
8-Find the cheapest path from source to destination
• Again, ask for two vertices and search for cheapest path between
these two paths.
9-Save current graph into outputStudentID.txt
• Your output file must be saved on current directory following the
same format as the graph.txt input file.
10-Exit
Your program must remain in the main menu for further operation after each operation.
Remember
• You must handle I/O exceptions and other exceptions properly
• You must organize your code into classes, template classes and make proper use of the
material learnt in class. Failing to do so will affect your grade.
• Your programʼs main menu must be stable and fully functional
• Your sourse code will be carefully investigated as your usage of the right material and
approach is subject to evaluation
• You must demonstrate every and each task described in “tasks” section of this document has
been properly addressed.
• You will have to submit one main.cpp file along with related .h or .cpp files.
• You are responsible to make sure that compilation instructions of your code are clear and
straight forward
• For bonus marks, you can describe a short simple hypothetical problem, use graphs and
search strategies you have developed to model and solve the problem.
• Never cheat or act unethically; any suspected attempt at cheating or unethical behavior will be
formally reported to the proper university body, and (you can be sure) treated with extreme
seriousness. Keep your lives simple and stay away from it.
Sample graph.txt
directed = false
V = city1,city2,city3,city4,city5,city6
E = (city1, city5, 8), (city1, city2, 6), (city5, city4, 12), (city5, city2, 3), (city2, city3, 4), (city3,
city4, 7), (city4, city6, 12)
Page 5 of 6