I believe that the expected value for the first test should be 85 instead of 86. since: Weight between java.awt.Point[x=0,y=0] and java.awt.Point[x=1,y=0] is 85
I'll have to look into it. Your observation only shows that maxLoad should be AT LEAST 85. There could be another route which supports more weight. Have you checked for this?
Thinking about this a little more, it is really a lot more likely that I made an off-by-one error in my reference code. So, probably all the test values are too large by one. If anyone can check this, I'd appreciate it.
I'll post a JAR with corrected values in the next couple of days.
I think that 86 should be a valid weight based on my tests on the WeightedGraph class so far. Here's the output that I got by printing out all the weights of the adjacent nodes to the start node:
I've confirmed that my tester had an off-by-one error. There's a new JAR you can download in the Assignments section. It has updated unit tests, and also a little visualizer tool you can use to visually inspect WeightedGrid2D objects.
It was coded in a rush, so please excuse its mediocre quality.
I need some help with the StressTester interface. In StressTesterTester it looks like the Node arguments are Point(s). It seems like Point is what I want as the WeightedGrid2D methods take Point, but I need to implement the StressTester interface with Node(s). I don't know what Node is in the interface.
So going over the requirements - are we returning highest load from the shortest path (which could be one of many shortest paths) or just the highest possible load path with no consideration of length (since longer paths could potentially yield higher load paths)?
So if we are looking at all s->f paths, we should build a graph starting at s (or f) in all directions until reaching node limit (and other end hopefully) and then we should try to calculate the maximum load s.t. we can still travel s->f? Or do you expect something smarter? ~ Alex
@Hera/Alex, The main drawback to your suggestion is that you are going to take a perfectly good implicit representation of the graph and convert it into an explicit representation of part of the graph.
In more detail, this is (1) inelegant (2) it's always going to cost you MAX_VERTS steps at the beginning. But this is usually a waste, since the path you will ultimately find is usually not very long.
My advice: don't worry about the MAX_VERTS/infinite loop issue until you have come up with your plan for calculating the maximum load. It should be a fairly small fix at that point.
I've been thinking about to go about this, and I'm wondering if the following concept is a good one: Use a version of Dijkstra's that searches outward from both the start and finish vertices simultaneously, since it could be possible that one or both is in a small unreachable component at the given weight. Also, I'm considering examining the location of the start and target vertices and looking at the distance between them, and drawing a sort of "bounding box" that will not allow my search to go beyond a certain factor of that distance in a direction opposite that of the other vertex.
I was thinking of something similar but the more we know about the end and its location the more this turns into A*, which is effectively Dijkstra's that uses a heuristic to keep you moving towards the end. Really efficient.
Trick is you have to use the max value, not the min.
I dont understand your "given weight" thinking though. Do we know anything about a specified minimum weight?
What I meant by given weight was that when you're actually running the algorithm, you're going to be testing specific weights to determine what the max load is, so the given weight is the weight that is being tested at that particular moment.
I don't know anything about A*, so I can't comment on that.
Dijkstra's and A* are algorithms for Shortest Path, where Path Cost = sum of edge costs.
For this problem, Path Value = min of edge costs, and we are trying to maximize Path Value.
These are very different problems. We will be happy with a really long path in PA2, as long as the whole path can support a heavy load. Dijkstra's algorithm will essentially never choose a really long path, since the weights get summed up.
Re test 7, the correct value for maxLoad is 50. My BFS starting at (0,0) had to search about 11500 nodes before finding the path that could support weight 50, which is why it was giving up.
I don't think it's worth reposting the JAR just to fix that one test. Feel free to edit your local copies to fix it. If your program is outputting 49, try upping your cutoff on how many nodes to search.
Todd - I got the expected answers for 16 and 18. Values around the midpoint are harder - you can travel a long way and not have the max min weight change (you can get to most places with a weight of ~50). I was running out of memory before finding a solution for several cases. Searching from both directions solves the problem. My worst case took less than 1700 iterations.
I was reading over the posts from kdpotter and Tom's response from 11/26/11. Could someone please clarify what Tom meant when he said "You're doing it wrong"? I understand we want to write our search in a generic way. I thought by having the signature correct as Tom mentions that the isVertex, isEdge, and neighbors methods would be available, but they are not(Eclipse doesn't prompt them) for the nodes. These are I believe should be prompting so I can create my search method. Could someone help me understand what is needed to make them available or why my thinking they would be available is incorrect?
Yes, you may assume the load values will always be from 0 to 99 inclusive. Although, since actually binary search can pinpoint an int between 0 and MAXINT in at most 31 steps, you shouldn't need this assumption.
My worst run time, for one function call, is approx 100ms (depending on the comp I am using). Is this in the valid range? This is with all tests passing. (most are 3-20ms)
I'm having trouble coming up with an effective strategy for searching the graph quickly. I can perform the breadth first search and I believe eliminating some nodes from the search could have to do with the weights coming from the edges of the destination node as the max load would have to be <= to one of those. In the lab Justin mentioned that professor Hayes had provide hints regarding searching from both ends and using binary search. I'm not sure I quite understand how these might apply. Could someone possibly clarify?
I had a question about how the program was going to be graded as well. I'm able to pass 20/23 tests every time, but the 3 that I'm not passing are all 1 less than the expected output.
Are the outputs going to be pass/fail or is it going to account how close we are to the expected? For some reason my answers don't change even when I change how many nodes it's including in the search, which is probably due to my implementation.
Also, I was wondering about the speed constraints brought up by @kstolleis. I'm able to pass one more test if I do a search from s and from t individually, but it is significantly slower (about 1000 slower) to get an answer that is 1 away from the previous answer (which is wrong by 1 but about 1000 times faster).
So I guess my question is, are we going for speed or correctness?
@kstolleis, Lucas: > So I guess my question is, are we going for speed or correctness?
Correctness is the top priority. However, if your code is taking longer than ten seconds to pass the test suite, you should take it as an indication that you are doing something less efficiently than you could.
Yes, answers which are close will be worth more than answers that are way off.
I was having the same problem but instead of restricting the number of search nodes, I restricted the number of visited nodes and that seemed to get me out far enough to pass those tests. They might take a bit of time but its not really that bad.
@rtrujillo The binary part is related to the loading - the hint is you can find the right load in log(99)base2... (hope that helps without giving too much away.)
I had Dr Hayes clarify that you dont need to search from both ends to pass. I am not and my runtime for the entire suite is around .5 seconds, with all correct answers.
Don't worry, 3 is Theta(0.5). Also, you are aware that kstolleis goes through a tank of liquid nitrogen every day, cooling his massively overclocked hardware?
But seriously, my code also takes a couple seconds of wall time. But I don't feel bad, because I know that a lot of that is due to good design decisions that will pay off in fewer bugs and more readable code. Also, the running time gap may narrow as the problem size scales up.
Anyone else having trouble with the 11th test? (Or is it test #11? They are numbered from 0.)
@rtrujillo - the BFS strategy you describe is what I implemented, with the same .5s runtime as kstolleis. It may be more efficient than you think, give it a shot first and then add binary search in once you have it working =).
Test 11 fails below around 4450 nodes. Interesting thing is that using search with Integer.MAX_VALUE does not really increase search times despite the extra iterations. Below 4000 visited failures become frequent.
Test #1 seems to be the really slow one.
And I am not using my computer as a space heater, yet.
I did this using non-recursive BFS search for expanding and recursive function for corrections.
The thing with this approach is that some tests require 40 additional layers after finish node was found, while for others, this is needless overhead which causes performance issues.
I cannot come up with something more intuitive than "run for additional 40 BFS layers" as a stopping criteria. Not that I haven't tried.
Another question. I managed to compile MyStressTester using jar. Now I am trying to run the program using the following command and getting the following error. What shall I add to my command to run the thing? Thanks
java -cp CS361Project2-v2.jar edu.unm.cs.cs361.fall2011.hayes.tom.graphs.StressTesterTester Exception in thread "main" java.lang.Error: Unresolved compilation problem: MyStressTester cannot be resolved to a type
@Lucia, Hmm, that is a strange error message. It generally means the class loader is having trouble finding a class file.
There is no class Node. Node is a generic type variable that can refer to any class. As such, the only place you should be referring to "Node" is within the body of your maxLoad function. Hope this helps.
Lucia, in this case Node is a generic and there is no Node class in the provided jar. I believe there are some posts from Prof. Hayes earlier in this discussion regarding this matter if you want to try and find them.
Make sure that your MyStressTester class is properly implementing the StressTester interface
@Lucia, re your second question, you will need to add an import statement to StressTesterTester.java, so the compiler knows which package you have put MyStressTester in. See the comment in the source file for StressTesterTester.
@Lucia, why don't you email me your code? I'm curious to see now.
@ollie, those numbers are way off. Are you using BFS? Also, I suggest you figure out what your code is doing on test 18. You can transport a load of weight 0 anywhere.
@ollie, This tutorial page might help: http://docs.oracle.com/javase/tutorial/extra/generics/methods.html
It means that the maxLoad method is a generic method, and so can effectively have lots of different method signatures. For instance, when the test code actually invokes it, it does so with calls to the method MyStressTester.maxLoad(WeightedGraph < Point >,Point,Point). But any other class could be used here instead of Point.
Also, annoyingly, it seems one has to put spaces around < and > symbols, so blogger doesn't think they are html markup, and delete them.
So far I have Dijkstra's algorithm successfully find the shortest path (in overall edge weight) in my graph. But how should we modify this so it finds the maximum load? My assumption was to have my priority queue extract the element with the longest distance from the source (rather than the shortest), but it still produces edges hat are smaller than all edges in other paths from s to t. Any suggestions?
@Ryan, I don't think you can get anywhere using Dijkstra's algorithm. See my comment from 11/29, 10:22pm.
Also note that the weights in the WeightedGraph object represent "load capacities" rather than "distances." So, summing them up doesn't make much sense.
I found out the problem with the generic method. I have to parametrize everything I used in the method.
I am using a modified version of Dijkstra Algorithm. The algorithm never visit the terminal node in case 18. In other error cases, the algorithm does reach the terminal nodes but can't figure out the correct weight for the node.
I did come up with something that is based on the Dijkstra Algorithm. I modified the meaning of "distance", "shortest v.s. heaviest" and the way "shortest distance" is updated in the loop.
@Tom I apologize if this throws people of from the correct solution or is too revealing, but to address your question:
I expand in all directions from [S] and keep track of {[N], MaxWeight ([S]->[N])}.
Eventually [F] will be found. If I stop, I pass around 6 | 7 of your tests because if Layer[i] contains path/weight to [F], Layer[i+1] may reveal a better path/weight to [F].
Corrections are back tracking. Suppose you can reach any node in some cluster with weight 60, the maximum weight (so far) to reach (some of) that cluster is 10 from [S]. It may be the case than in the next layer a better path will be revealed to that cluster. Thus the whole cluster's maxWeight must be updated accordingly.
So we are allowed/required to search for infinite number of paths from s to t and find the one that allows the heaviest load? The problem with this one is that it is too easy to get into an infinite loop. Is there a special purpose algorithm for this one?
@Lucia, on the StressTester's javadoc, it says that we are only required to search out 10,000 nodes for the path with the heaviest load capacity.
It seems like prof. Hayes has been hinting "BFS" throughout this discussion, and I would recommend starting there. If you can figure out how to successfully modify Dijkstra's as some people have, that's another method.
Regarding "modified Dijkstra's algorithms", I deliberately gave an unfamiliar problem for this assignment, so people could come up with the algorithm on their own. So, I'm not telling you how to solve the problem.
That being said, there are advantages to using the algorithms we've learned as "black boxes," rather than modifying them to solve different problems. Perhaps most important is that they provide a common language among computer scientists and programmers, for describing and discussing possible solutions to problems. Also, when you choose the most appropriate algorithm for the job, it is much easier to check that you are solving the right problem.
By the way, if you modify Dijkstra's algorithm enough, you get other named algorithms, such as Prim's algorithm.
@Hera, it would be good to try to find some more principled way to decide when you are done, rather than the ad-hoc method of going 40 levels beyond F.
I can say this - I went down the alternative path - Prim's to be exact - and although I think it works just fine I found the implementation to be complex in that you have to provide a comparator and store the entire path you find. The comparator turned out to be a real PITA so...
I am at a loss on how to determine when I am done. The only thing I can think of is to build BFS from both sides and see if the results are the same. ~Alex
@Lucia: Your two problems sound almost identical to the first two problems I had. Here's what I did:
In StressTester.java, there's a method signature for maxLoad() defined, so I copied and pasted it into my file, and I modified my helper functions to look like that signature.
I unzipped the jar file and have been running the class files from the unzipped directory. The trick is to go to the directory you unzipped in, and specify the complete path to each file you want to compile or execute. Unfortunately, you can't just go to the directory and run them there, or java will give you a bizzare error message. I have a directory ~/pa2/ that I unzipped in and under that is edu/unm/cs/cs361/fall2011/hayes/tom/graphs/, so I use the command "java edu/unm/cs/cs361/fall2011/hayes/tom/graphs/StressTesterTester" from ~/pa2/ to run the program.
@everyone: For my algorithm, tests 2, 16, and 18 are all hard in the forward direction, but easy going backwards. If you're having problems with specific tests, I'd try switching the direction you run your tests and see if it does better. Mine has a relatively hard time with 3 tests in the forward direction and 5 tests in the backwards direction, but *all of them are easy* in the opposite direction.
I don't know if switching directions will end up working for all algorithms, but it's something worth trying, and it's easy to implement.
I have my program “done”, but still don’t understand the generic parameter Node. My maxLoad function has signature:
@Override public < Node > int maxLoad(WeightedGraph< Node > g, Node s, Node t) {
Tom said it should be
@Override public int maxLoad(WeightedGraph g, Node s, Node t) {
( this causes eclipse to suggest a list of things including implement class Node)
In my maxLoad method I have to cast Points to Nodes to call g.getWeight(u, v) (same with neighbors()), which seems odd because getWeight is implemented using Points. I am not sure how to propose a useful question, but if something jumps out at you, let me know.
@Unknown - ok, my method signature is correct - the other issues remain.
In my maxLoad method I have to cast Points to Nodes to call g.getWeight(u, v) (same with neighbors()), which seems odd because getWeight is implemented using Points. I am not sure how to propose a useful question, but if something jumps out at you, let me know.
getWeight is actually implemented with generics, so it could be anything:
int getWeight(T v, T w) throws NonEdgeException;
so, when your MyStressTester class, which implements the StressTester interface, implements the maxLoad method, your signature should look like:
public (Node) int maxLoad(WeightedGraph(Node) g, Node s, Node t)
note: the (Node) parameters should be the less-than and greater-than signs, not parentheses.
So, when you call g.getWeight(u,v), you will have to surround with a try/catch block because of the exception it is throwing, but you should not have to cast anything...it will know you're getting the weight between two nodes.
Yes, I do have this line, but if I use the jar, then I cannot run the program and, obviously, modify the jar. And when I unjar it, then the Eclipse doesn't see the graphs.*
It is my first time using Eclipse and I haven't been programming in Java for probably 5 years. :/
OK, in Eclipse, I believe you want to select the "src" directory for your project, then choose File>Import>General>Archive File, Then choose the jar file you want.
If the Jar file gets imported into the wrong directory, then the compiler won't be able to find the classes. In that case, you may be able to fix it by dragging the package from wherever it ended up into your "src" directory.
Actually, I'm also a relative newbie to Eclipse, so if someone else has a better answer, feel free to chime in.
@Lucia: I'm not using Eclipse, I'm doing all the compiling and running of the code from the command line.
The command line I used to make a runnable jar file: "jar cfvm project2.jar Manifest.txt edu/unm/cs/cs361/fall2011/hayes/tom/graphs/ edu/unm/cs/cs361/fall2011/mshaw02/project2/"
Manifest.txt is a one-line file with the following contents (things I found about this on the web mentioned the importance of ending this file with a newline): "Main-Class: edu.unm.cs.cs361.fall2011.hayes.tom.graphs.StressTesterTester"
My compilation command line (all the other java files had .class files already, so no need to recompile those): "javac edu/unm/cs/cs361/fall2011/hayes/tom/graphs/StressTesterTester.java edu/unm/cs/cs361/fall2011/mshaw02/project2/MyStressTester.java"
My command line to run the program: "java edu/unm/cs/cs361/fall2011/hayes/tom/graphs/StressTesterTester"
This is all from the directory that I unzipped the jar in.
I don't know if Eclipse includes these command line utilities, but if it doesn't and you don't already have them installed, you shouldn't have to do anything other than download/install the JDK to get them. Other than flipping the direction of slashes on windows and changing mshaw02/project2/ to whatever directory you use, you should be able to use this as is. On Linux, pressing the up arrow gets you the previous command, saving tons of typing, and IIRC windows has the same thing.
I don't know if you'll want to do it that way or not, but that is what I did.
Tom, I had spoken to you today about my programming assignment and you mentioned that if I include a bound check and not enqueue any nodes beyond these bounds then my algorithm should work. But I have not passed any more tests. Is there something I'm missing? Here is my code: while(it.hasNext()) { v=it.next(); if(!visited.contains(v)) { //do not enqueue //any nodes that have already been visited if(v.getX()<10000 && v.getY()<10000){ //do not //enqueue any nodes within 10000 nodes from origin distance.put((Point) v, g.getWeight(u,(Node)v)); //store the distance from u to v predecessors.put((Point) v, (Point)u); //mark u as the predecessor (or parent) of v q.add((Point) v); //enqueu v into priority queue } } }
@Ryan (1) I know I spoke to you today as if Nodes and Points were interchangeable, but this casting back and forth between them totally undermines the generic nature of your code. I suggest, instead of checking the X and Y coordinates, you keep track of how many hops away from the start node each node is (use the predecessor's value + 1). Then your Nodes can stay generic. (2) "within" should be "beyond" (3) What is "it"? Shouldn't you be taking the elements out of the priority queue, q?
I believe that the expected value for the first test should be 85 instead of 86. since:
ReplyDeleteWeight between java.awt.Point[x=0,y=0] and java.awt.Point[x=1,y=0] is 85
I'll have to look into it. Your observation only shows that maxLoad should be AT LEAST 85. There could be another route which supports more weight. Have you checked for this?
ReplyDeleteThinking about this a little more, it is really a lot more likely that I made an off-by-one error in my reference code. So, probably all the test values are too large by one. If anyone can check this, I'd appreciate it.
ReplyDeleteI'll post a JAR with corrected values in the next couple of days.
I think that 86 should be a valid weight based on my tests on the WeightedGraph class so far. Here's the output that I got by printing out all the weights of the adjacent nodes to the start node:
ReplyDelete|INFO|
Start Point: java.awt.Point[x=0,y=0] End Point: java.awt.Point[x=1,y=0]
Adjacent: java.awt.Point[x=1,y=0] Weight between=85
Adjacent: java.awt.Point[x=-1,y=0] Weight between=42
Adjacent: java.awt.Point[x=0,y=1] Weight between=60
Adjacent: java.awt.Point[x=0,y=-1] Weight between=87
|INFO END|
So while that doesn't prove that 86 is the correct answer, it does provide the option that it COULD be the correct answer.
ReplyDeleteHi,
ReplyDeleteI've confirmed that my tester had an off-by-one error. There's a new JAR you can download in the Assignments section. It has updated unit tests, and also a little visualizer tool you can use to visually inspect WeightedGrid2D objects.
It was coded in a rush, so please excuse its mediocre quality.
I need some help with the StressTester interface. In StressTesterTester it looks like the Node arguments are Point(s). It seems like Point is what I want as the WeightedGrid2D methods take Point, but I need to implement the StressTester interface with Node(s). I don't know what Node is in the interface.
ReplyDeleteThanks kp
@kdpotter: Node is a Generic parameter. Your code should not care what it's actual implementation is.
ReplyDeleteIn Eclipse, when I implement StressTester like this:
ReplyDeletepublic class BridgeSearch implements StressTester {
I want to implement:
public int maxLoad( WeightedGraph g, Point s, Point t){
Eclipse wants me to implement:
public int maxLoad(WeightedGraph g, Node s, Node t) {
How do I resolve this?
kp
@kdpotter,
ReplyDeleteYour signature should look like this (verbatim):
@Override
public int maxLoad(WeightedGraph g, Node s, Node t) {
As spatel posted, your code here should work for any kind of Node. If it needs to use anything specific to Point, you're doing it wrong.
Note that the @Override annotation here should ensure that you get the signature line right (or get error messages).
Oops, seems this blogger thing doesn't like stuff in between less-than and greater-than signs. Here is the signature again.
ReplyDelete@Override
public lt Node gt int maxLoad ( WeightedGraph lt Node gt g, Node s, Node t ) {
lt means less-than, gt means gt.
So going over the requirements - are we returning highest load from the shortest path (which could be one of many shortest paths) or just the highest possible load path with no consideration of length (since longer paths could potentially yield higher load paths)?
ReplyDeleteSorry if this was answered already.
@kstolleis: The latter. We are willing to go farther in order to transport the heaviest load possible.
ReplyDeleteI believe test 7 may still have an error
ReplyDeleteTodd and myself both get:
seed = 7340032. maxLoad returned 50
Test 7 failed. Expected 49. Got 50
So if we are looking at all s->f paths, we should build a graph starting at s (or f) in all directions until reaching node limit (and other end hopefully) and then we should try to calculate the maximum load s.t. we can still travel s->f? Or do you expect something smarter?
ReplyDelete~ Alex
@Hera/Alex, The main drawback to your suggestion is that you are going to take a perfectly good implicit representation of the graph and convert it into an explicit representation of part of the graph.
ReplyDeleteIn more detail, this is (1) inelegant (2) it's always going to cost you MAX_VERTS steps at the beginning. But this is usually a waste, since the path you will ultimately find is usually not very long.
My advice: don't worry about the MAX_VERTS/infinite loop issue until you have come up with your plan for calculating the maximum load. It should be a fairly small fix at that point.
I've been thinking about to go about this, and I'm wondering if the following concept is a good one: Use a version of Dijkstra's that searches outward from both the start and finish vertices simultaneously, since it could be possible that one or both is in a small unreachable component at the given weight. Also, I'm considering examining the location of the start and target vertices and looking at the distance between them, and drawing a sort of "bounding box" that will not allow my search to go beyond a certain factor of that distance in a direction opposite that of the other vertex.
ReplyDeleteAnyone have thoughts on this?
Charlie,
ReplyDeleteI was thinking of something similar but the more we know about the end and its location the more this turns into A*, which is effectively Dijkstra's that uses a heuristic to keep you moving towards the end. Really efficient.
Trick is you have to use the max value, not the min.
I dont understand your "given weight" thinking though. Do we know anything about a specified minimum weight?
kstolleis,
ReplyDeleteWhat I meant by given weight was that when you're actually running the algorithm, you're going to be testing specific weights to determine what the max load is, so the given weight is the weight that is being tested at that particular moment.
I don't know anything about A*, so I can't comment on that.
@Charlie and kstolleis,
ReplyDeleteDijkstra's and A* are algorithms for Shortest Path, where Path Cost = sum of edge costs.
For this problem, Path Value = min of edge costs, and we are trying to maximize Path Value.
These are very different problems. We will be happy with a really long path in PA2, as long as the whole path can support a heavy load. Dijkstra's algorithm will essentially never choose a really long path, since the weights get summed up.
I agree with spatel. I just passed all of the tests except for test 7.
ReplyDeleteseed = 7340032. maxLoad returned 50
Test 7 failed. Expected 49. Got 50
It seems there's a path with a larger Load than the test was expecting.
Upon further investigation, it seems to be dependent on the limit you set. (How far out your search will go).
ReplyDeleteI obtained 50 with a depth limit of 500, however with a depth limit of 300, I've passed all the test provided, with the values specified.
Re test 7, the correct value for maxLoad is 50. My BFS starting at (0,0) had to search about 11500 nodes before finding the path that could support weight 50, which is why it was giving up.
ReplyDeleteI don't think it's worth reposting the JAR just to fix that one test. Feel free to edit your local copies to fix it. If your program is outputting 49, try upping your cutoff on how many nodes to search.
Oddly enough test 7 isn't the only one I'm having trouble with and they all seem to be centered around 50...
ReplyDeleteTest 7 failed. Expected 49. Got 50
Test 16 failed. Expected 48. Got 50
Test 18 failed. Expected 49. Got 50
Should I just not worry about this? I pass all other tests.
Todd - I got the expected answers for 16 and 18. Values around the midpoint are harder - you can travel a long way and not have the max min weight change (you can get to most places with a weight of ~50). I was running out of memory before finding a solution for several cases. Searching from both directions solves the problem. My worst case took less than 1700 iterations.
ReplyDeletekp
That totally makes sense, thank you. I now pass all of them. Much more efficiently as well :)
ReplyDeleteI was reading over the posts from kdpotter and Tom's response from 11/26/11. Could someone please clarify what Tom meant when he said "You're doing it wrong"? I understand we want to write our search in a generic way. I thought by having the signature correct as Tom mentions that the isVertex, isEdge, and neighbors methods would be available, but they are not(Eclipse doesn't prompt them) for the nodes. These are I believe should be prompting so I can create my search method. Could someone help me understand what is needed to make them available or why my thinking they would be available is incorrect?
ReplyDeleteNever mind...I think I figured out my issue.
ReplyDeleteI was wondering if we can assume that load values will all be set, atomically, between 0-99?
ReplyDeleteYes, you may assume the load values will always be from 0 to 99 inclusive.
ReplyDeleteAlthough, since actually binary search can pinpoint an int between 0 and MAXINT in at most 31 steps, you shouldn't need this assumption.
My worst run time, for one function call, is approx 100ms (depending on the comp I am using). Is this in the valid range? This is with all tests passing. (most are 3-20ms)
ReplyDeleteI'm having trouble coming up with an effective strategy for searching the graph quickly. I can perform the breadth first search and I believe eliminating some nodes from the search could have to do with the weights coming from the edges of the destination node as the max load would have to be <= to one of those. In the lab Justin mentioned that professor Hayes had provide hints regarding searching from both ends and using binary search. I'm not sure I quite understand how these might apply. Could someone possibly clarify?
ReplyDeleteI had a question about how the program was going to be graded as well. I'm able to pass 20/23 tests every time, but the 3 that I'm not passing are all 1 less than the expected output.
ReplyDeleteAre the outputs going to be pass/fail or is it going to account how close we are to the expected? For some reason my answers don't change even when I change how many nodes it's including in the search, which is probably due to my implementation.
Also, I was wondering about the speed constraints brought up by @kstolleis. I'm able to pass one more test if I do a search from s and from t individually, but it is significantly slower (about 1000 slower) to get an answer that is 1 away from the previous answer (which is wrong by 1 but about 1000 times faster).
So I guess my question is, are we going for speed or correctness?
@kstolleis, Lucas:
ReplyDelete> So I guess my question is, are we going for speed or correctness?
Correctness is the top priority. However, if your code is taking longer than ten seconds to pass the test suite, you should take it as an indication that you are doing something less efficiently than you could.
Yes, answers which are close will be worth more than answers that are way off.
@Lucas
ReplyDeleteI was having the same problem but instead of restricting the number of search nodes, I restricted the number of visited nodes and that seemed to get me out far enough to pass those tests. They might take a bit of time but its not really that bad.
@rtrujillo
The binary part is related to the loading - the hint is you can find the right load in log(99)base2... (hope that helps without giving too much away.)
@rtrujillo
ReplyDeleteI had Dr Hayes clarify that you dont need to search from both ends to pass. I am not and my runtime for the entire suite is around .5 seconds, with all correct answers.
.5? I must be doing something dumb . . .
ReplyDeleteI still fail the eleventh test. and it takes 3 seconds. GRrr
@spatel
ReplyDeleteDon't worry, 3 is Theta(0.5). Also, you are aware that kstolleis goes through a tank of liquid nitrogen every day, cooling his massively overclocked hardware?
But seriously, my code also takes a couple seconds of wall time. But I don't feel bad, because I know that a lot of that is due to good design decisions that will pay off in fewer bugs and more readable code. Also, the running time gap may narrow as the problem size scales up.
Anyone else having trouble with the 11th test? (Or is it test #11? They are numbered from 0.)
it's test 11, sorry. Actually that does make me feel slightly better. I'm running on a laptop :P
ReplyDeleteseed = 11534336. maxLoad returned 21
Test 11 failed. Expected 49. Got 21
This is consistent for me, no matter how many nodes I read in (1,000,000 is the highest I've tested with).
This comment has been removed by the author.
ReplyDelete@rtrujillo - the BFS strategy you describe is what I implemented, with the same .5s runtime as kstolleis. It may be more efficient than you think, give it a shot first and then add binary search in once you have it working =).
ReplyDelete-Mark
p.s. that was running on a moons machine.
ReplyDeletetest 11 is the first to fail if i drop my # of nodes searched, but anything above 5000 works fine for me.
-Mark
Test 11 fails below around 4450 nodes. Interesting thing is that using search with Integer.MAX_VALUE does not really increase search times despite the extra iterations. Below 4000 visited failures become frequent.
ReplyDeleteTest #1 seems to be the really slow one.
And I am not using my computer as a space heater, yet.
I got the all the test passed.
ReplyDeleteI did this using non-recursive BFS search for expanding and recursive function for corrections.
The thing with this approach is that some tests require 40 additional layers after finish node was found, while for others, this is needless overhead which causes performance issues.
I cannot come up with something more intuitive than "run for additional 40 BFS layers" as a stopping criteria. Not that I haven't tried.
I get 3,003 ms as the lowest run time.
@Hera, I don't understand anything you wrote, sorry. What "corrections"? Why would you want to keep running BFS after finding the finish node?
ReplyDeletewhen i'm trying to refer to Node from dependent jar (i.e. StressTester) I get the error message:
ReplyDeleteThe type Node cannot be resolved. It is indirectly referenced from required .class files
I did add external jar. Is there something else I am missing?
Thanks
Another question. I managed to compile MyStressTester using jar. Now I am trying to run the program using the following command and getting the following error. What shall I add to my command to run the thing? Thanks
ReplyDeletejava -cp CS361Project2-v2.jar edu.unm.cs.cs361.fall2011.hayes.tom.graphs.StressTesterTester
Exception in thread "main" java.lang.Error: Unresolved compilation problem:
MyStressTester cannot be resolved to a type
@Lucia, Hmm, that is a strange error message. It generally means the class loader is having trouble finding a class file.
ReplyDeleteThere is no class Node. Node is a generic type variable that can refer to any class. As such, the only place you should be referring to "Node" is within the body of your maxLoad function. Hope this helps.
Lucia, in this case Node is a generic and there is no Node class in the provided jar. I believe there are some posts from Prof. Hayes earlier in this discussion regarding this matter if you want to try and find them.
ReplyDeleteMake sure that your MyStressTester class is properly implementing the StressTester interface
@Lucia, re your second question, you will need to add an import statement to StressTesterTester.java, so the compiler knows which package you have put MyStressTester in. See the comment in the source file for StressTesterTester.
ReplyDeleteTom, about the Node type. I have a method-local inner class in maxLoad, which used Nodes. I do not use Nodes anywhere else.
ReplyDeleteHere are my failed cases, any comments?
ReplyDeleteseed = 7340032. maxLoad returned 17
Test 7 failed. Expected 49. Got 17
seed = 11534336. maxLoad returned 21
Test 11 failed. Expected 49. Got 21
seed = 4194304. maxLoad returned 15
Test 16 failed. Expected 48. Got 15
seed = 6291456. maxLoad returned -1
Test 18 failed. Expected 49. Got -1
My code return -1 when it can' find the terminal node.
Ollie
My eclipse complains about the strange Node maxLoad() method too.
ReplyDeleteWhat does the before the method name in the interface mean?
How is resolved by the compiler? Do we say something like
maxLoad(...) like C++ or it is type-inferred?
Ollie
@Lucia, why don't you email me your code? I'm curious to see now.
ReplyDelete@ollie, those numbers are way off. Are you using BFS? Also, I suggest you figure out what your code is doing on test 18. You can transport a load of weight 0 anywhere.
@ollie, This tutorial page might help: http://docs.oracle.com/javase/tutorial/extra/generics/methods.html
ReplyDeleteIt means that the maxLoad method is a generic method, and so can
effectively have lots of different method signatures. For instance, when the test code actually invokes it, it does so with calls to the method
MyStressTester.maxLoad(WeightedGraph < Point >,Point,Point).
But any other class could be used here instead of Point.
Also, annoyingly, it seems one has to put spaces around < and > symbols, so blogger doesn't think they are html markup, and delete them.
So far I have Dijkstra's algorithm successfully find the shortest path (in overall edge weight) in my graph. But how should we modify this so it finds the maximum load? My assumption was to have my priority queue extract the element with the longest distance from the source (rather than the shortest), but it still produces edges hat are smaller than all edges in other paths from s to t. Any suggestions?
ReplyDelete@Ryan, I don't think you can get anywhere using Dijkstra's algorithm. See my comment from 11/29, 10:22pm.
ReplyDeleteAlso note that the weights in the WeightedGraph object represent "load capacities" rather than "distances." So, summing them up doesn't make much sense.
@Tom,
ReplyDeleteI found out the problem with the generic method. I have to parametrize everything I used in the method.
I am using a modified version of Dijkstra Algorithm. The algorithm never visit the terminal node in case 18. In other error cases, the algorithm does reach the terminal nodes but can't figure out the correct weight for the node.
Ollie
@Tom,
ReplyDeleteI did come up with something that is based on the Dijkstra Algorithm. I modified the meaning of "distance", "shortest v.s. heaviest" and the way "shortest distance" is updated in the loop.
Ollie
@Tom
ReplyDeleteI apologize if this throws people of from the correct solution or is too revealing, but to address your question:
I expand in all directions from [S] and keep track of {[N], MaxWeight ([S]->[N])}.
Eventually [F] will be found. If I stop, I pass around 6 | 7 of your tests because if Layer[i] contains path/weight to [F], Layer[i+1] may reveal a better path/weight to [F].
Corrections are back tracking. Suppose you can reach any node in some cluster with weight 60, the maximum weight (so far) to reach (some of) that cluster is 10 from [S]. It may be the case than in the next layer a better path will be revealed to that cluster. Thus the whole cluster's maxWeight must be updated accordingly.
~Alex
So we are allowed/required to search for infinite number of paths from s to t and find the one that allows the heaviest load? The problem with this one is that it is too easy to get into an infinite loop. Is there a special purpose algorithm for this one?
ReplyDelete@Lucia, on the StressTester's javadoc, it says that we are only required to search out 10,000 nodes for the path with the heaviest load capacity.
ReplyDeleteIt seems like prof. Hayes has been hinting "BFS" throughout this discussion, and I would recommend starting there. If you can figure out how to successfully modify Dijkstra's as some people have, that's another method.
@Unknown,
ReplyDeleteIsn't Dijkstra's Algorithm a form of BFS too? The last paragraph on page 140 discussed about this aspect a little bit.
@Unknown, that what I did. I modified BFS and Dijkstra. However, Prof. Hayes seems doesn't like this idea.
ReplyDeleteRegarding "modified Dijkstra's algorithms", I deliberately gave an unfamiliar problem for this assignment, so people could come up with the algorithm on their own. So, I'm not telling you how to solve the problem.
ReplyDeleteThat being said, there are advantages to using the algorithms we've learned as "black boxes," rather than modifying them to solve different problems. Perhaps most important is that they provide a common language among computer scientists and programmers, for describing and discussing possible solutions to problems. Also, when you choose the most appropriate algorithm for the job, it is much easier to check that you are solving the right problem.
By the way, if you modify Dijkstra's algorithm enough, you get other named algorithms, such as Prim's algorithm.
@Hera, it would be good to try to find some more principled way to decide when you are done, rather than the ad-hoc method of going 40 levels beyond F.
I can say this - I went down the alternative path - Prim's to be exact - and although I think it works just fine I found the implementation to be complex in that you have to provide a comparator and store the entire path you find. The comparator turned out to be a real PITA so...
ReplyDeleteI am at a loss on how to determine when I am done. The only thing I can think of is to build BFS from both sides and see if the results are the same.
ReplyDelete~Alex
@Lucia: Your two problems sound almost identical to the first two problems I had. Here's what I did:
ReplyDeleteIn StressTester.java, there's a method signature for maxLoad() defined, so I copied and pasted it into my file, and I modified my helper functions to look like that signature.
I unzipped the jar file and have been running the class files from the unzipped directory. The trick is to go to the directory you unzipped in, and specify the complete path to each file you want to compile or execute. Unfortunately, you can't just go to the directory and run them there, or java will give you a bizzare error message. I have a directory ~/pa2/ that I unzipped in and under that is edu/unm/cs/cs361/fall2011/hayes/tom/graphs/, so I use the command "java edu/unm/cs/cs361/fall2011/hayes/tom/graphs/StressTesterTester" from ~/pa2/ to run the program.
@everyone: For my algorithm, tests 2, 16, and 18 are all hard in the forward direction, but easy going backwards. If you're having problems with specific tests, I'd try switching the direction you run your tests and see if it does better. Mine has a relatively hard time with 3 tests in the forward direction and 5 tests in the backwards direction, but *all of them are easy* in the opposite direction.
I don't know if switching directions will end up working for all algorithms, but it's something worth trying, and it's easy to implement.
I have my program “done”, but still don’t understand the generic parameter Node. My maxLoad function has signature:
ReplyDelete@Override
public < Node > int maxLoad(WeightedGraph< Node > g, Node s, Node t) {
Tom said it should be
@Override
public int maxLoad(WeightedGraph g, Node s, Node t) {
( this causes eclipse to suggest a list of things including implement class Node)
In my maxLoad method I have to cast Points to Nodes to call g.getWeight(u, v) (same with neighbors()), which seems odd because getWeight is implemented using Points. I am not sure how to propose a useful question, but if something jumps out at you, let me know.
@kdpotter, the professor corrected himself directly below the comment you are referencing, as the < > symbols didn't show up.
ReplyDelete"Oops, seems this blogger thing doesn't like stuff in between less-than and greater-than signs. Here is the signature again.
@Override
public lt Node gt int maxLoad ( WeightedGraph lt Node gt g, Node s, Node t ) {
lt means less-than, gt means gt."
@Unknown - ok, my method signature is correct - the other issues remain.
ReplyDeleteIn my maxLoad method I have to cast Points to Nodes to call g.getWeight(u, v) (same with neighbors()), which seems odd because getWeight is implemented using Points. I am not sure how to propose a useful question, but if something jumps out at you, let me know.
@kdpotter
ReplyDeletegetWeight is actually implemented with generics, so it could be anything:
int getWeight(T v, T w) throws NonEdgeException;
so, when your MyStressTester class, which implements the StressTester interface, implements the maxLoad method, your signature should look like:
public (Node) int maxLoad(WeightedGraph(Node) g, Node s, Node t)
note: the (Node) parameters should be the less-than and greater-than signs, not parentheses.
So, when you call g.getWeight(u,v), you will have to surround with a try/catch block because of the exception it is throwing, but you should not have to cast anything...it will know you're getting the weight between two nodes.
Hope this helps.
-TIM
@Michael:
ReplyDeleteDid you use jar in the library of your package to implement the interface?
I tried to use unjared files in the library and the class file seems doesn't find the StressTester interface to implement.
@Lucia,
ReplyDeleteDo you have a line
import edu.unm.cs.cs361.fall2011.hayes.tom.graphs.StressTester;
or
import edu.unm.cs.cs361.fall2011.hayes.tom.graphs.*;
Remember that you have to import any classes that aren't in the same package as yours.
@Tom,
ReplyDeleteYes, I do have this line, but if I use the jar, then I cannot run the program and, obviously, modify the jar. And when I unjar it, then the Eclipse doesn't see the graphs.*
It is my first time using Eclipse and I haven't been programming in Java for probably 5 years. :/
@Lucia,
ReplyDeleteOK, in Eclipse, I believe you want to select the "src" directory for your project, then choose File>Import>General>Archive File, Then choose the jar file you want.
If the Jar file gets imported into the wrong directory, then the compiler won't be able to find the classes. In that case, you may be able to fix it by dragging the package from wherever it ended up into your "src" directory.
Actually, I'm also a relative newbie to Eclipse, so if someone else has a better answer, feel free to chime in.
I got 500 ms as the lowest time to finish all the tests (1.6 Ghz CPU).
ReplyDeleteIssue is that this version will never reach 10,000 nodes with a grid-style graph provided, is this OK?
~Alex
@Lucia: I'm not using Eclipse, I'm doing all the compiling and running of the code from the command line.
ReplyDeleteThe command line I used to make a runnable jar file:
"jar cfvm project2.jar Manifest.txt edu/unm/cs/cs361/fall2011/hayes/tom/graphs/ edu/unm/cs/cs361/fall2011/mshaw02/project2/"
Manifest.txt is a one-line file with the following contents (things I found about this on the web mentioned the importance of ending this file with a newline):
"Main-Class: edu.unm.cs.cs361.fall2011.hayes.tom.graphs.StressTesterTester"
My compilation command line (all the other java files had .class files already, so no need to recompile those):
"javac edu/unm/cs/cs361/fall2011/hayes/tom/graphs/StressTesterTester.java edu/unm/cs/cs361/fall2011/mshaw02/project2/MyStressTester.java"
My command line to run the program:
"java edu/unm/cs/cs361/fall2011/hayes/tom/graphs/StressTesterTester"
This is all from the directory that I unzipped the jar in.
I don't know if Eclipse includes these command line utilities, but if it doesn't and you don't already have them installed, you shouldn't have to do anything other than download/install the JDK to get them. Other than flipping the direction of slashes on windows and changing mshaw02/project2/ to whatever directory you use, you should be able to use this as is. On Linux, pressing the up arrow gets you the previous command, saving tons of typing, and IIRC windows has the same thing.
I don't know if you'll want to do it that way or not, but that is what I did.
24 of 24 tests passed in 270 milliseconds, appoximately 11 milliseconds per test
ReplyDeletehurray!
Tom,
ReplyDeleteI had spoken to you today about my programming assignment and you mentioned that if I include a bound check and not enqueue any nodes beyond these bounds then my algorithm should work. But I have not passed any more tests. Is there something I'm missing? Here is my code:
while(it.hasNext()) {
v=it.next();
if(!visited.contains(v)) { //do not enqueue //any nodes that have already been visited
if(v.getX()<10000 && v.getY()<10000){ //do not //enqueue any nodes within 10000 nodes from origin
distance.put((Point) v, g.getWeight(u,(Node)v)); //store the distance from u to v
predecessors.put((Point) v, (Point)u); //mark u as the predecessor (or parent) of v
q.add((Point) v); //enqueu v into priority queue
}
}
}
@Hera, spatel, congrats on passing all the tests!
ReplyDelete@Ryan
(1) I know I spoke to you today as if Nodes and Points were interchangeable, but this casting back and forth between them totally undermines the generic nature of your code. I suggest, instead of checking the X and Y coordinates, you keep track of how many hops away from the start node each node is (use the predecessor's value + 1). Then your Nodes can stay generic.
(2) "within" should be "beyond"
(3) What is "it"? Shouldn't you be taking the elements out of the priority queue, q?
Wow @spatel that is pretty slow :p \troll
ReplyDelete@Tom: The solution was to not use Dijkstra's :P
ReplyDelete@Lucas: I see you trollin' . . . I hatin' . . .