CSC322S2025Graphing < CenterForComputing

Tags: view all tags
---+CSC 322 Lab 5 (Graphs)
---++Objectives
   1. Show off your C skills
   1. Demonstrate understanding of graphs
   1. Study the time implications of graph algorithms

---++Problem
Write C code to:
   * implement graphs.  It is encouraged that you use adjacency lists.  You may also allow the program/user to do so (based in the ratio of number of edges to number of vertices)
      * this should allow the user to input the graph from a file 
         * first line: number of nodes followed by the type of graph (u, d, w), 
         * next n lines the names of each node, 
         * then one line per edge: node_name node_name with an optional weight
   * This is to be an interactive graph and should allow the following:
      * the graph to be undirected, a digraph and/or a weighted graph
      * determine if the graph is acyclic or not
      * list all pendants in the graph
      * determine if the graph is connected (or strongly connected)
      * do a breadth first traversal from a user specified vertex
      * do a depth first traversal from a user specified vertex
      * do a shortest path traversal from a user specified vertex
      * implement a min. spanning tree algorithm
      * implement one other algorithm on the graph of your choosing (but must be approved by me)
   * Each function/method you write needs to include a big O analysis (including routines it calls).  Anything that not obvious must be explained
   * Study the implications of different tables sizes in your analysis
<br>
Note: For this lab, you are required to do all work (except the writeup) on your virtual Linux machine.  
---++Details
   1. Come up with a plan for steps for coding and include those steps in your report (under design) and a statement about how well you followed it
   1. Guesstimate how long this lab will take and record it.
   1. Create a software development report include the two previous items and :
      a. include a discussion on the fragility of your program in the security report
   1. Create a tar ball with all .c, .h, makefile, and SDR and submit it via Canvas (no .o)
---++Challenges
   * add more algorithms
Topic revision: r1 - 2025-04-03 - CathyBareiss