Assignment 5: Graph

 

Assignment 5

 



 

Write a program to do the following:

 

(a)   Read a description of a graph and create its adjacency list representation.  The information at each node consists of a string no longer than 16 characters.  Data for the program will be supplied as follows:

 

        •   the names of the nodes;  each name is a one-word string consisting of letters and/or digits, for example, London.  This portion of the data  is terminated by the ‘name’ END.  The number of nodes is unknown beforehand.  The nodes are to be kept in a binary search tree (BST).

 

        •   the description of the edges of the graph.  The edges emanating from a node are specified by the name of the node, followed by an integer, n, (indicating the number of edges leaving the node), followed by n pairs of values.  Each pair consists of a node name (the child) and a positive integer weight (the cost of going from the node to the child).  The number of edges is unknown beforehand.  Edges from a node must be stored in alphabetical order by node name but they may be given in arbitrary order in the data.  However, the names of the nodes are NOT to be stored in the adjacency list; instead, the BST  location of the node must be stored. Data is terminated by a node END.

 

        Output the graph, listing the nodes in alphabetical order.  Each node is followed by the name and weight of the edges leaving it.

 

(b)   Read the names of two nodes and give the depth-first and breadth-first traversals of the graph from each of these nodes. Print only the names of the nodes.

 

(c)   Read the names of several nodes (one per line) and, for each node, find the minimal cost path to all the other nodes.  Data is terminated by END.  Use a heap structure to maintain the priority queue.  Output the path and the minimal cost to each node.  Use 9999 to represent an infinite cost.


Some sample input

England  Greece  Antigua 
Dominica France Canada  Belarus
END
France 3 England 25 Greece 45 Belarus 40
Canada 1 Antigua 20
Greece 1 Canada 15
Antigua 0
Dominica 3 France 30 England 20 Belarus 80
Belarus 3 Antigua 50 Canada 15 England 10
England 2 Greece 5 Canada 45
END
Dominica   England
Antigua
Dominica
END

Sample output

Antigua
Belarus  Antigua 50 Canada 15 England 10
Canada   Antigua 20
Dominica Belarus 80 England 20 France 30
England  Canada 45 Greece 5
France   Belarus 40 England 25 Greece 45
Greece   Canada 15

Depth-first:    Dominica Belarus Antigua Canada England Greece France
Breadth-first:  Dominica Belarus England France Antigua Canada Greece

Depth-first:    England Canada Antigua Greece Belarus Dominica France
Breadth-first:  England Canada Greece Antigua  Belarus Dominica France

Minimal cost path from Antigua: 
  to Belarus: 9999  path: unreachable
  to Canada:  9999  path: unreachable
  to Dominica:9999  path: unreachable
  to England: 9999  path: unreachable
  to France:  9999  path: unreachable
  to Greece:  9999  path: unreachable

Minimal cost path from Dominica: 
  to Antigua: 60  path: Dominica   England   Greece   Canada   Antigua
  to Belarus: 70  path: Dominica   France    Belarus
  to Canada:  40  path: Dominica   England   Greece   Canada
  to England: 20  path: Dominica   England
  to France:  30  path: Dominica   France
  to Greece:  25  path: Dominica   England   Greece