Dijkstra’s Research Objectives: |
In this research, we will be applying programming features, including pointers and dynamic memory, recursion, classes, inheritance, overloading, and templates in the efficient implementation of programs realizing presented data structures and algorithms. Again we will describe and implement data structures such as linked lists, stacks, queues, binary trees, hashes, and graphs and implement search algorithms such as depth-first, breadth-first, and Dijkstra’s algorithm. While analyzing the run-time complexity of a given algorithm. |
Overview
In this assignment, we will create a graph and traverse this graph in multiple ways.
Guidelines and Expectations
Is to implement a Graph data structure using a professional library. We will construct a graph using the functions or methods it provides and then apply three common algorithms to process the data/information.
Requirements
- Properly implement a graph data structure using existing graph libraries that include at least 20 vertices and 20 edges.
- Utilize three different algorithms on your graph.
- Documentation (Lab Report)
- Display or represent the graph in 2 ways, if the library enables this. (for example, Adjacency matrix, Adjacency List, Edge List)
- Describe in your own words the Algorithms implemented.
- Describe the inputs and outputs of the Algorithms
- Present and analyze the results of the Algorithms after they are implemented and executed on your graph.
- Briefly describe when or why you would use the algorithms.
Guidelines
Common Algorithms for Implementation
The following algorithms are commonly used on graphs (this list is not all-inclusive).
You can select some of these or find others that are implemented by your library and utilize them in meaningful ways.
Shortest Path
- Bellman-Ford
- Dijkstra’s
- A*
Minimum Spanning Trees
- Prim’s
- Krustkal’s
- Tarjan’s
Topological Sort
Depth First Search
Breadth-First Search
Cycle Finding Algorithms
Clustering Algorithms
Resources
Professional Graph Libraries
C++
Boost – http://www.boost.org/doc/libs/1_62_0/libs/graph/doc/index.html
(Boost’s graph implementation is incredibly powerful, but also extremely complex. I would highly recommend not using Boost for this, but it is an option.)
Lemon – http://lemon.cs.elte.hu/trac/lemon
Helpful Resources
- Presentation – http://lemon.cs.elte.hu/pub/doc/lemon-intro-presentation.pdf
- Documentation – http://lemon.cs.elte.hu/pub/doc/latest/index.html