CSC 322 Lab 5 (Graphs)

Objectives

1. Show off your C skills
2. Demonstrate understanding of graphs
3. Study the time implications of graph algorithms

Problem

• 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

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
2. Guesstimate how long this lab will take and record it.
3. Create a software development report include the two previous items and :
   1. include a discussion on the fragility of your program in the security report
4. Create a tar ball with all .c, .h, makefile, and SDR and submit it via Canvas (no .o)

Challenges

• add more algorithms