Assignemnt 05 - March 18, 19 , 2009

Use 2 graphs: Attach:graph1.txt , Attach:graph2.txt, both have 1000 vertices (0..999). For testing, use Attach:graph_small.txt.

Program the solutions for 1-4.

1. Create an undirected version of those graphs (making connections symmetric). You can use either adjacency lists or matrices. How many edges were in the original and in the undirected graph.

2. Traverse the directed graphs using BFS and DFS, from nodes 1, 10, 500, 999. How many nodes are reachable (in the directed graph).

3. Traverse the undirected graphs from task 1 in the same manner. Answer the same questions as in 2. Additionally, how many connected components?

4. Output the BFS and DFS search trees (the subgraph showing the order of discovery of all nodes) of the tasks 2 and 3 in the same graph format as in the original input.

5. Define 5 commercially meaningful, interesting, or otherwise challenging graph questions/problems on your favorite social network system (Facebook, LinkedIn, Skype,, ...). Use 1 paragraph description for each problem.

6. Bonus Visualise the original graphs and search trees by yourself (e.g. using SWOG, or other visualisation) (2p), or some graph layout program (1p). Note that your layout does not have to be pretty ;-). If the size is too big, cut the graphs smaller using consideration (how to choose a subgraph; which size is not too small ...).