Return to Answer

##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.

##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.

##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 union(pegghCanReach, samCanReach)

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

##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.

##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. Foreach vertex v in peggyStart find the strongly connected component in G.
2. Foreach vertex v in samStart find the strongly connected component in G'.

###3. Find the set of common vertices: The set of vertices defined by the intersection of the union of all Peggy's strongly connected components with the union of all Sam's strongly connected components is the set of all possible vertices at which Sam and Peggy could meet.

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

Hash based set operations are O(1).

##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 union(pegghCanReach, samCanReach)

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