/COT5405-AOA-Graphs

Graph Algorithms with proof.

Primary LanguageTeX

COT5405-AOA-Graphs

Anmol Lingan Gouda Patil
UFID: 19673150

Graph Algorithms with proof for the following:

Cycle Detection: Design and implement an algorithm to find a cycle (just one cycle) in an undirected graph.

Minimum Spanning Tree: Consider undirected graphs that have n nodes and at most n+8 edges. For such graphs, design an efficient algorithm that finds the minimum spanning tree.

Prerequisites:

  • JGraphT library for random graph generation for running and testing the algorithms.
  • Java 8
  1. Download the jars of JGraphT via maven and add these to lib folder under Project.
  2. Steps to add the library in IntelliJ IDE:
    Navigate to
    File > Project Structure > Under Project Settings choose Libraries > Add library by clicking ➕ button (from maven) > type org.jgrapht in 🔍 search bar > download verion: org.jgrapht:jgrapht-core:1.3.0 > Apply settings.

GNM Random Graph Generator for all random graph generation.

Cycle Detection

  • To run the Cycle Find algorithm run CycleClient.main() inside algorithms/src/Cycle.java
  • The size of graphs considered are in increasing order to measure performance and verify time complexity.
  • Following are the Vertices and Edge sizes considered:

V = {10, 50, 100, 125, 500, 760, 1000, 2500, 5000, 6000, 10000, 13000, 23000, 50000};
E = {20, 70, 150, 170, 700, 850, 1400, 3000, 5800, 7000, 15000, 15000, 27000, 58000};
Gi(Vi, Ei) for testcase i.

  • Every knot is printed and verfified to validate the presence of cycle.
  • Performance Plots are available as part of the report.
  • Latex source of report available here.

Minimum spanning tree

  • To run the Minimum Spanning tree algorithm run MSTClient.main() inside algorithms/src/MST.java
  • The size of graphs considered are in increasing order to measure performance and verify time complexity.
  • Following are the Vertices and Edge sizes considered:

V = {10, 50, 100, 125, 500, 760, 1000, 2500, 5000, 6000, 10000, 13000, 23000, 50000};
Ei = Vi + 8
Gi(Vi, Ei) for testcase i.

  • The weight of minimum spanning tree generated for Gi using MinimumSpanningTreeDFS Algorithm is validated against the weight of JGraphT's KruskalMinimumSpanningTree applied on Gi using assert statement.
  • Performance Plots are available as part of the report.
  • Latex source of report available here.