Return to Revisions

##Very Positive Aspects of the Code

1. Many of the comments are meaningful.
2. Many of the routine names are descriptive.

##Basic Comments

1. The assumption that the graph is undirected is mistaken:

Each segment of river is listed as pairs of addresses, from upstream to downstream. 2. In my opinion trying to define a graph based on nodes is a poor starting point. See my comments here and here. 3. Thinking about problems mathematically and writing a specification before writing code is recommended by at least one Turing Award winner.

##Decoupling It would be helpful to separate the business logic abstractions of Peggy and Sam and swimming, from the underlying mathematical abstractions of graphs and nodes upon which the business logic is built. Both the business logic and the mathematics should be separated from raw Java arrays and lists etc.

###Modularity Decoupling the code provides natural module boundaries. Node.java is a step in this direction, but more separation of abstractions would be beneficial.

#Program Specification

###Summary of Problem

1. The Map is given as a directed graph from upstream to downstream.
2. A list of vertices which must be avoided is given.
3. Peggy Piranha swims only downstream.
4. Sam Salmon swims only upstream.
5. Find the set of vertices reachable by both Peggy and Sam.

###Given:

• a digraph Map = {V, E} (vertices are implied).
• a list of dead vertices dead
• a list of Peggy starting vertices peggyStart
• a list of Sam starting vertices samStart

###1. Initialize:

• Create digraph G by removing all edges u -> v such that dead.member(u) || dead.member(v) == TRUE
• Create digraph G' such that for each edge u -> v in G there is an edge v -> u in G'.

###2. Find strongly connected components:

1. peggyPaths = the set of strongly connected components in G containing at least one element of peggyStart.
2. samPaths = the strongly connected component in G' containing at least one element of samStart.

###3. Find the set of common vertices:

1. peggyCanReach = the union of all vertices in peggyPaths.
2. samCanReach = the union of all vertices in samPaths.
3. return intersection (peggyCanReach, samCanReach)

##Implementation Details Finding the strongly connected components of a digraph can be done in linear time [O(n + m)] using Kosaraju's Algorithm.