Issues I saw with some student implementations:
·
Did not follow instructions:
o Allocated
storage for edges. Big points taken off.
o Templates
or generics were not used
o Accessing IGraph through Grid, rather than grid through IGraph.
o Grid could
not be queried using row and column.
·
Poor choice of variable names, parameter names, method
names:
o I, j
instead of row column.
o X,y – even worse to an old Fortran programmer
o Size, edges
method names
o EdgeExist – not a question. EdgeExists would be better. Starting with a verb seems to
be the trend.
·
Not thinking of the problem:
o With
indexed vertices, there is no need to iterate over the vertex labels, just use getNodeLabel.
·
Overly complex
o BigInteger rather than int
or Integer
o Not using
the grid methods to implement the IGraph methods.
01 /**
02 * @author Prof. Roger Crawfis
03 *
04 */
05 public interface IGraph<N, E> {
06 //
07 // Methods dealing with the overall topology
08 //
09 public int NumberOfNodes();
10 public int NumberOfEdges();
11 public Boolean HasEdge(int fromNodeIndex, int toNodeIndex);
12 public int getNumberAdjacentNodes(int nodeIndex);
13 //
14 // Design Problem - Java Generics have limitations:
15 // Sadly, Java decided not to update the JVM when it added
16 // generics, so all generics need to be of reference type.
17 // Hence an array might be a better return type than an
18 // array if performance is key. Alternatively, we could
19 // make our own iterator type specific to integers. This
20 // would not follow Java's Iterable Iterator interfaces. Why
21 // this over arrays? Arrays may lead to confusion. Can I set
22 // the value of an index. If so, what happens?
23 //
24 //public Iterable<Integer> getAdjacentNodes(int nodeIndex);
25 public int[] getAdjacentNodes(int nodeIndex);
26 //public MyIntegerInterator getAdjacentNodes(int nodeIndex);
27 //
28 // Methods dealing with Node labels.
29 //
30 // This could be factored out into its own interface
31 // Alternatively, implementers without nodal values can just
32 // return a default value. Possible in C# for all types -
33 // primitive and reference types. Java can return null, since
34 // all generics are reference types only. Separate classes are
35 // required for value types :-(. Backward compatibility.
36 //
37 public N getNodelLabel(int nodeIndex);
38 //
39 // Methods dealing with Edge labels.
40 //
41 // This could be factored out into its own interface as above.
42 // However, bifurcating node and edge labels into two separate
43 // interfaces is problematic for the using class as they need
44 // to deal with two different types rather than a single polymorphic
45 // type.
46 //
47 public E getEdgeLabel(int fromNodeIndex, int toNodeIndex);
48 }
001 import java.security.InvalidParameterException;
002 import java.util.Iterator;
003
004 /**
005 * @author Prof. Roger Crawfis
006 *
007 */
008 public class Grid<N, E> implements IGraph<N, E> {
009
010 //
011 // IGraph Interface
012 //
013 @Override
014 public Boolean HasEdge(int fromNodeIndex, int toNodeIndex) {
015 int fromRow = getRow(fromNodeIndex);
016 int fromColumn = getColumn(fromNodeIndex);
017 int toRow = getRow(toNodeIndex);
018 int toColumn = getColumn(toNodeIndex);
019 return HasEdge(fromRow, fromColumn, toRow, toColumn);
020 }
021
022 @Override
023 public int NumberOfEdges() {
024 // Count each node's South and West edges only (North and East will be counted
025 // by the adjacent nodes).
026 return 2*((numberRows-1)*(numberColumns-1)) + (numberRows-1) + (numberColumns-1);
027 }
028
029 @Override
030 public int NumberOfNodes() {
031 return numberRows * numberColumns;
032 }
033
034 @Override
035 public Iterable<Integer> getAdjacentNodes(int nodeIndex) {
036 return new NodeIterable(nodeIndex);
037 }
038
039 // Bad Design #1?
040 // TODO Fix Bad Design in Interface?
041 // Was this really needed?
042 @Override
043 public int getNumberAdjacentNodes(int nodeIndex) {
044 int count = 0;
045 for( int index : getAdjacentNodes(nodeIndex))
046 count++;
047 return count;
048 }
049 // @Override
050 // public int getNumberAdjacentNodes(int nodeIndex) {
051 // int row = getRow(nodeIndex);
052 // int column = getColumn(nodeIndex);
053 // if(!ValidIndex(row,column))
054 // return 0;
055 //
056 // int count = 4;
057 // if( row == 0 || row == (numberRows-1))
058 // count--;
059 // if( column == 0 || column == (numberColumns-1))
060 // count--;
061 // return count;
062 // }
063
064 // Bad Design #2
065 // TODO Fix Bad return value
066 @Override
067 public E getEdgeLabel(int fromNodeIndex, int toNodeIndex) {
068 return null;
069 }
070
071 @Override
072 public N getNodelLabel(int index) {
073 int row = getRow(index);
074 int column = getColumn(index);
075 return getNodelLabel(row,column);
076 }
077
078
079
080 //
081 // Specific Public Methods for Grid.
082 //
083 // Bad Design #3
084 // TODO Fix bad constructor
085 public Grid(N[][] nodeValues) {
086 this.nodeValues = nodeValues;
087 this.numberRows = nodeValues.length;
088 this.numberColumns = nodeValues[0].length;
089 }
090
091 public Boolean HasEdge(int fromRow, int fromColumn, int toRow, int toColumn) {
092 // Check the row and column indices are within the grid.
093 if( !ValidIndex(fromRow, fromColumn))
094 return false;
095 if( !ValidIndex(toRow, toColumn))
096 return false;
097
098 // Compare the row and column indices to see if this is a valid edge for a grid.
099 int rowDifference = Math.abs(fromRow - toRow);
100 int columnDifference = Math.abs(fromColumn - toColumn);
101 if( rowDifference > 1)
102 return false;
103 if( columnDifference > 1)
104 return false;
105 // Pretty simple now that we know a) both nodes are valid and
106 // b) all indices are within one from each other. Now we just
107 // need to make sure that we do not have a diagonal.
108 if(rowDifference == columnDifference)
109 return false;
110 // Alternatively, the last three if statements can be combined as follows:
111 //if( (rowDifference+columnDifference) != 1)
112 // return false;
113 return true;
114 }
115
116 public N getNodelLabel(int row, int column) {
117 if(!ValidIndex(row,column))
118 throw new InvalidParameterException();
119 return this.nodeValues[row][column];
120 }
121
122 //
123 // The next three methods could have private access or package access
124 //
125 public int getColumn(int nodeIndex) {
126 return nodeIndex % numberColumns;
127 }
128
129 public int getRow(int nodeIndex) {
130 return nodeIndex / numberColumns;
131 }
132
133 public int getIndex(int row, int column) {
134 return row*numberColumns + column;
135 }
136
137
138 //
139 // Implementation
140 //
141 private Boolean ValidIndex( int row, int column ) {
142 return ValidRow(row) && ValidColumn(column);
143 }
144
145 private Boolean ValidRow( int row ) {
146 if( row < 0)
147 return false;
148 if(row >= numberRows)
149 return false;
150 return true;
151 }
152
153 private Boolean ValidColumn(int column) {
154 if(column < 0)
155 return false;
156 if(column >= numberColumns)
157 return false;
158 return true;
159 }
160
161 //
162 // Private member variables
163 //
164 private N[][] nodeValues;
165 private int numberRows;
166 private int numberColumns;
167 // Kind of annoying I need to declare these constants here. I want them
168 // only in NodeIterator :-(.
169 private static final int[] rowStep = { 0, 1, 0, -1 };
170 private static final int[] columnStep = { -1, 0, 1, 0 };
171
172
173 //
174 // Nested supporting classes
175 //
176 class NodeIterable implements Iterable<Integer> {
177
178 @Override
179 public Iterator<Integer> iterator() {
180 return new NodeIterator(nodeIndex);
181 }
182
183 NodeIterable(int nodeIndex) {
184 this.nodeIndex = nodeIndex;
185 }
186
187 private int nodeIndex;
188
189 class NodeIterator implements Iterator<Integer> {
190 @Override
191 public boolean hasNext() {
192 return currentIndex < 4;
193 }
194
195 @Override
196 public Integer next() {
197 int index = getIndex(row+rowStep[currentIndex], column+columnStep[currentIndex]);
198 currentIndex++;
199 MoveNext();
200 return index;
201 }
202
203 @Override
204 public void remove() {
205 throw new UnsupportedOperationException("no remove allowed");
206 }
207
208
209 NodeIterator(int nodeIndex) {
210 this.row = getRow(nodeIndex);
211 this.column = getColumn(nodeIndex);
212 Initialize();
213 }
214
215 private void Initialize() {
216 if(!ValidIndex(row, column))
217 currentIndex = 4;
218 MoveNext();
219 }
220
221 private void MoveNext() {
222 while( currentIndex < 4 && !ValidIndex(row+rowStep[currentIndex], column+columnStep[currentIndex]))
223 currentIndex++;
224 }
225
226 private int row, column;
227 private int currentIndex = 0;
228 }
229 }
230 }
C++
Implementations· Note the use of const. Does this imply it is immutable? Is the Java interface immutable?
· I will go through three steps of design in the iterator for this. There are problems (design problems) with all three. The implementation can be similar to the Java implementation, but we will use a stored list (std::vector) to show the three possible choices.
· Another possibility is of course to return the vector directly. Why might you not want to do this? Why not return an array of int’s as in Java? Similar reasoning.
Well, I think I deleted this, but it was basically creating a vector, creating a class EdgeIterator whose constructor copies over the vector. The methods Next and HasNext simlpy walk through the vector. The Grid's GetAdjacentNodes created the vector and created the EdgeIterator with the vector passed into it.
As a first step towards removing the vector, we moved the logic to compute the vector to the iterator, and gave it the necessary information to compute it, height, width, row and column. The Grid's GetAdjacentNodes simply returned an instance of the iterator now.
The problem with the above solution is that the iterator is only good for grid’s, but we put it in the interface for graphs. Be careful of this common trap! The solution is to factor out the iterator into its own interface and use that in the graph interface. However, now we have to return pointers, so the graph interface changes as well. This leads to the bigger problem of who owns the returned iterators and is responsible for deleting this heap allocated memory. Here, the client is responsible for deleting the iterator after it is done with it. This can be easily solved with smart pointers in the Boost library or other libraries. Note, this could and probably should be made a template in C++. The Graph interface would then indicate it returned a Iterator<int>* type.
#ifndef ITERATOR_H#define ITERATOR_H namespace Crawfis
{
namespace CSE680
{
class Iterator
{
public:
virtual int Next() = 0;
virtual bool HasNext() const = 0;
}; }}
#endif
#ifndef GRIDEDGEITERATOR_H
#define GRIDEDGEITERATOR_H
#include <vector>
namespace
Crawfis
{
namespace
CSE680
{
class
EdgeIterator : public Iterator
{
public:
EdgeIterator(const int nodeIndex, const int width, const int height);
virtual int Next();
virtual bool HasNext() const;
private:
void Initialize();
int nodeIndex;
int
width;
int
height;
unsigned int
position;
std::vector<int> adjacentNodes;
};
}
}
#endif
Iterator<int>* edgeIterator = graph.getAdjacentNodes(7);
cout << "AdjacentNodes of node 7: ";
while( edgeIterator->HasNext() == true )
{cout << edgeIterator->Next() << " ";
}cout << endl;
delete edgeIterator;