The objectives are

• List properties of graphs including incident, adjacent, neighbors, degree, isolated, and pendant
• Identify in-degree and out-degree on directed graphs
• Represent graphs with adjacency matrixes
• Represent graphs with adjacency lists
• Finds paths, simple paths, and circuits in graphs
• Determine is a graph is connected
• Find strongly connected components in a graph
• Apply Dijkstra's shortest path algorithm to graphs
• Learn Floyd's all-pairs shortest path algorithm

Problems

1. (2 points) 10.2.2
2. (2 points) 10.2.8
3. (3 points) 10.3.2
4. (3 points) 10.3.4
5. (2 points) 10.3.12
6. (2 points) 10.3.26 (8th ed. 10.3.30) - do for Exercise 2 only (not Example 2). Use the following labels for edges: graph
7. (4 points) 10.4.2
8. (1 points) 10.4.4
9. (3 points) 10.4.12
10. (3 points) 10.4.14
11. (2 points) 10.4.18
12. (6 points) 10.6.8 - Extend Dijkstra's algorithm to compute the actual path as well as the mileage. Show your work. Report both the mileage and the path.
13. (6 points) 10.6.21 - Extend Floyd's algorithm to compute the actual path as well as the cost. Report the cost between a and z and show how the path is reconstructed from your extension.
14. (6 points Extra Credit) Draw the “call graph” of the following program fragment. (The nodes of a call graph are methods and the edges are method calls)
1. What do cycles in a call graph mean?
2. What does it mean if the graph is disconnected?
MainProgram
main(String[])
DatalogProgram.evaluateQueryList(StringBuffer)
DatalogProgram
evaluateQueryList(StringBuffer)
QueryList.evaluate(StringBuffer)
FactList
canProve(Predicate)
Fact.equals(Object)
Predicate
set(int, Constant)
Fact
equals(Object)
RuleList
canProve(Predicate)
Rule.prove(Predicate)
Rule
prove(Predicate)
PredicateList.evaluate()
unify(Predicate)
matches(Predicate)
PredicateList
PredicateList(PredicateList)
PredicateList.initializeVariableInformation()
Query.initializeVariableInformation()
evaluate()
PredicateList.recurse(int)
recurse(int)
PredicateList.keepOnGoing(Boolean)
Query.keepOnGoing(Boolean)
PredicateList.recurse(int)
PredicateList.checkToSeeIfTrue()
checkToSeeIfTrue
FactList.canProve(Predicate)
RuleList.canProve(Predicate)
PredicateList.saveResult()
Query.saveResult()
saveResult()
setUpVariableLocationMapping()
initializeVariableInformation
PredicateList.setUpVariableLocationMapping()
keepOnGoing(Boolean)
QueryList
evaluate(StringBuffer)
Query.evaluate(StringBuffer)
Query
initializeVariableInformation()
evaluate(StringBuffer)
PredicateList.evaluate()
saveResult()
keepOnGoing(Boolean)