nekozye/project-2

project-2's Issues

Devin Romanoff - Code Review

Project-2/com/neko/rug/Main.java

Lines 104 to 105 in 6404460

	type = (type + 1) - selector;
	type = type - 1;

This seems redundant and can probably be reduced to one line.

Project-2/com/neko/rug/Main.java

Line 153 in 6404460

Graph glr = createLinkedList(10000);

Having slightly more verbose/less abbreviated variable names could help with readability]

Project-2/com/neko/rug/Node.java

Lines 18 to 22 in 6404460

	public String toString() {
	return "Node{" +
	"nodeVal=" + nodeVal+
	'}';
	}

Might be redundant because nodeVal is already a string

Project-2/com/neko/rug/Graph.java

Line 9 in 6404460

LinkedList<Node> nodes;

Project-2/com/neko/rug/Graph.java

Lines 77 to 82 in 6404460

	HashSet<Node> getAllNodes()
	{
	HashSet<Node> set = new HashSet<Node>();
	set.addAll(this.nodes);
	return set;
	}

The LinkedList could be a redundant data structure because you can iterate through a HashSet to get all the nodes and manipulate them too

Project-2/com/neko/rug/GraphSearch.java

Lines 21 to 68 in 6404460

	public ArrayList<Node> DFSRec(final Node start, final Node end)
	{
	HashSet<Node> visited = new HashSet<Node>();
	LinkedList<Node> nodelist = DFSRecHelper(start,start,end,visited);
	ArrayList<Node> nds = new ArrayList<Node>();
	for(int i = 0; i < nodelist.size(); i++)
	{
	nds.add(nodelist.get(i));
	}
	return nds;
	}
	//returns null if no destination reach. returns the list including start if exists.
	//makes sure the recursive happens before queueing the next log, so depth is searched first
	public LinkedList<Node> DFSRecHelper(final Node start, final Node current, final Node end, HashSet<Node> visited)
	{
	visited.add(current);
	if(current.equals(end))
	{
	LinkedList<Node> rtlist = new LinkedList<Node>();
	rtlist.addFirst(current);
	return rtlist;
	}
	LinkedList<Node> adjlist = graphToSearch.getAdjList(current);
	boolean deadEnd = true;
	for(int i = 0; i < adjlist.size(); i++)
	{
	if(!visited.contains(adjlist.get(i)))
	{
	deadEnd = false;
	LinkedList<Node> rtf = DFSRecHelper(start,adjlist.get(i),end,visited);
	if(rtf != null)
	{
	rtf.addFirst(current);
	return rtf;
	}
	}
	}
	if(deadEnd)
	{
	return null;
	}
	return null;
	}

The assignment states that DFSRec should recursively return an ArrayList, so while this is a recursive DFS I'm not sure it fully complies with the problem statement

Project-2/com/neko/dag/Main.java

Lines 126 to 142 in 6404460

	switch(decider)
	{
	case 2:
	if(nodesToAdd.isEmpty())
	break;
	nodeTemp = nodesToAdd.removeFirst();
	graphToReturn.addDirectedEdge(nodeInQuestion,nodeTemp);
	queue.addLast(nodeTemp);
	case 1:
	if(nodesToAdd.isEmpty())
	break;
	nodeTemp = nodesToAdd.removeFirst();
	graphToReturn.addDirectedEdge(nodeInQuestion,nodeTemp);
	queue.addLast(nodeTemp);
	case 0:
	break;
	}

This switch is redundant because case 1 and 2 execute the same code

Project-2/com/neko/dag/TopSort.java

Lines 59 to 60 in 6404460

	LinkedList<DirectCostNode> workStack = new LinkedList<DirectCostNode>();
	LinkedList<DirectCostNode> resultStack = new LinkedList<DirectCostNode>();

Is there an advantage of using a LinkedList over a Stack

Project-2/com/neko/dag/DirectCostNode.java

Lines 18 to 21 in 6404460

	public void addDirectedEdge(final DirectCostNode destination, int cost)
	{
	this.edges.put(destination,new Integer(cost));
	}

There should be a check in case an edge already exists

Project-2/com/neko/rug/GraphSearch.java

Lines 16 to 19 in 6404460

	public void switchGraph(Graph graphToSearch)
	{
	this.graphToSearch = graphToSearch;
	}

This operation could be performed in the constructor

Project-2/com/neko/rug/GraphSearch.java

Lines 168 to 173 in 6404460

	if (queue.isEmpty())
	{
	ArrayList<Node> rtbf = new ArrayList<Node>();
	rtbf.addAll(bflr);
	return rtbf;
	}

You might save space by making bflr an ArrayList to begin with and returning that

Andrew Peters - Code Review

Project-2/com/neko/rug/Node.java

Lines 4 to 10 in 6404460

	public String nodeVal;
	public Node(String nodeVal)
	{
	this.nodeVal = nodeVal;
	}

giving the Node class a visited variable would make it a lot easier to keep track of which nodes you have looked at already

Project-2/com/neko/rug/Main.java

Lines 86 to 90 in 6404460

	for(int i = 0; i < n; i++)
	{
	rug.addNode(String.valueOf(i+1));
	}

for you random graph, you do not add n random nodes to the graph. you add specific nodes 1 through n

Project-2/com/neko/rug/Main.java

Lines 106 to 125 in 6404460

	switch(type)
	{
	case 3:
	select = random.nextInt(listnodes.size());
	nd = nodearr[select];
	rug.addUndirectedEdge(node,nd);
	case 2:
	select = random.nextInt(listnodes.size());
	nd = nodearr[select];
	rug.addUndirectedEdge(node,nd);
	case 1:
	select = random.nextInt(listnodes.size());
	nd = nodearr[select];
	rug.addUndirectedEdge(node,nd);
	case 0:
	select = random.nextInt(listnodes.size());
	nd = nodearr[select];
	rug.addUndirectedEdge(node,nd);
	break;
	}

since you do the same code every time with just one of them having an additional break, you don't need a switch statement. you can just use an if statement and say if type == 0, then break

Project-2/com/neko/rug/GraphSearch.java

Lines 9 to 19 in 6404460

	Graph graphToSearch;
	public GraphSearch(Graph graphToSearch)
	{
	switchGraph(graphToSearch);
	}
	public void switchGraph(Graph graphToSearch)
	{
	this.graphToSearch = graphToSearch;
	}

isn't it kinda redundant to have the method switchGraph? in your GraphSearch constructor you can just assign graphToSearch to the parameter

Project-2/com/neko/rug/GraphSearch.java

Lines 24 to 30 in 6404460

	LinkedList<Node> nodelist = DFSRecHelper(start,start,end,visited);
	ArrayList<Node> nds = new ArrayList<Node>();
	for(int i = 0; i < nodelist.size(); i++)
	{
	nds.add(nodelist.get(i));
	}
	return nds;

you can save memory space by making the helper method return an arraylist and just make nodeList an arraylist type

Project-2/com/neko/rug/GraphSearch.java

Lines 21 to 31 in 6404460

	public ArrayList<Node> DFSRec(final Node start, final Node end)
	{
	HashSet<Node> visited = new HashSet<Node>();
	LinkedList<Node> nodelist = DFSRecHelper(start,start,end,visited);
	ArrayList<Node> nds = new ArrayList<Node>();
	for(int i = 0; i < nodelist.size(); i++)
	{
	nds.add(nodelist.get(i));
	}
	return nds;
	}

if you helper method ends up returning null, then the main function would return an empty list instead of null, and the question asked to return null if no path is found

Project-2/com/neko/dag/DirectedGraph.java

Lines 55 to 60 in 6404460

	public void addDirectedEdge (final DirectCostNode first, final DirectCostNode second) {
	if(this.nodes.contains(first) && this.nodes.contains(second))
	{
	first.edges.put(second,1);
	}
	}

you should add some kind of check to make sure there is not already an existing edge from first to second

Project-2/com/neko/dag/Main.java

Lines 103 to 151 in 6404460

	public static DirectedGraph createRandomDAGIter(final int n){
	DirectedGraph graphToReturn = new DirectedGraph();
	LinkedList<DirectCostNode> nodesToAdd = new LinkedList<DirectCostNode>();
	for(int i = 0; i < n; i++)
	{
	DirectCostNode nd = new DirectCostNode(String.valueOf(i));
	nodesToAdd.addLast(nd);
	graphToReturn.addNode(nd);
	}
	Random rand = new Random();
	LinkedList<DirectCostNode> queue = new LinkedList<DirectCostNode>();
	queue.addLast(nodesToAdd.removeFirst());
	while(!queue.isEmpty())
	{
	int decider = rand.nextInt(3);
	DirectCostNode nodeInQuestion = queue.removeFirst();
	DirectCostNode nodeTemp = null;
	switch(decider)
	{
	case 2:
	if(nodesToAdd.isEmpty())
	break;
	nodeTemp = nodesToAdd.removeFirst();
	graphToReturn.addDirectedEdge(nodeInQuestion,nodeTemp);
	queue.addLast(nodeTemp);
	case 1:
	if(nodesToAdd.isEmpty())
	break;
	nodeTemp = nodesToAdd.removeFirst();
	graphToReturn.addDirectedEdge(nodeInQuestion,nodeTemp);
	queue.addLast(nodeTemp);
	case 0:
	break;
	}
	if(queue.isEmpty() && !nodesToAdd.isEmpty())
	{
	queue.addLast(nodesToAdd.removeFirst());
	}
	}
	return graphToReturn;
	}

your random DAG code does not check to make sure it is not adding an edge backwards, so this could create a cycle in the graph, and a DAG is acyclic

Project-2/com/neko/dag/TopSort.java

Lines 58 to 60 in 6404460

	LinkedList<DirectCostNode> visited = new LinkedList<DirectCostNode>();
	LinkedList<DirectCostNode> workStack = new LinkedList<DirectCostNode>();
	LinkedList<DirectCostNode> resultStack = new LinkedList<DirectCostNode>();

you could save memory space by having a visited variable in the node class and just using a stack to track what you have processed

Project-2/com/neko/grid/GridGraph.java

Lines 24 to 36 in 6404460

	public void addUndirectedEdge(final GridNode first, final GridNode second)
	{
	boolean nextTo = isNextTo(first,second);
	if(nextTo)
	{
	GridNode.GridDirection gd = getSide(first,second);
	if(gd != GridNode.GridDirection.ERR)
	{
	first.setSide(gd,second);
	second.setSide(GridNode.GridDirection.flip(gd),first);
	}
	}
	}

you first check if node second is next to node first, and then you check which side the node second is on and then add as long as that side isn't an error. you probably don't need to have 2 separate checks to add the node. you can just have one check to determine what side node second is on, and if returns an error then you know that second is not a neighbor