• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Jeanne Boyarsky
  • Junilu Lacar
  • Henry Wong
Sheriffs:
  • Ron McLeod
  • Devaka Cooray
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Frits Walraven
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • salvin francis
  • fred rosenberger

junit test with a stream

 
Master Rancher
Posts: 300
16
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone, can you kindly help me out to write tests with streaming input? I try to do it the right way, writing tests first. For once.

The problem I am trying to solve is this one: Eulerian path, and as you see, the tests are streaming in, as long as not interrupted by double zero.

"4 4
0 1
1 2
1 3
2 3
2 2
0 1
1 0
2 1
0 1
0 0"
 
Saloon Keeper
Posts: 12008
257
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is roughly the order of doing things:

  • Figure out roughly what interfaces, classes and members you need to model the problem and how they relate to each other.
  • Declare your visible types and their members, but don't implement them yet.
  • Document the behavior of your types and members very diligently. For instance, think about edge-cases and document when exceptions are thrown.
  • Write unit tests based on the documentation you wrote. Write separate tests for all edge-cases.
  • Mock services if necessary. Validate that they are called when necessary.
  • Ensure that all tests run and fail.
  • Implement your methods so that after each increment, another test succeeds.

  • If you can't make a test succeed by implementing the design you already made, think about whether the design is wrong or whether the test makes the wrong assumptions. If the test is wrong, change it. If the design is wrong, rewrite your types and members and their documentation. Update your tests so they make the correct assumptions about the new design, and add new tests if necessary. Continue implementing your design until all tests succeed.

    Let's do this one step at a time. What types will you need to model this problem? Don't write any code. Explain it to us in plain English.
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Hi Stefan,
    This one is not focused on documenting or writing complicated classes, it is just a competitive programming problem. My only issue is just to have working tests. Can we go to the last part, have a test that validates inputs of graphs of unknown length ?
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12008
    257
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    You can't write tests if you don't have a design to test. Even if you want to solve your problem with a single monolithic procedure (bad idea) and you don't want to worry about edge-cases, you still need to declare that method before you can test it.

    Let's model the problem like this (although it's really not a good design):

    You can now write a test like this:

    This requires that your project has a dependency on JUnit 5.

    JUnit Jupiter will repeatedly call testSolveEulerianPathProblem(), incrementing the repetition count. The test uses the repetition count to read a sample input and sample output from the project's resources.

    If you want to add another sample input and output, add files sample-input-2.txt and sample-output-2.txt to the source code package that EulerianPathProblemTest is also in, and increment the value of the test method annotation so it reads @RepeatedTest(2).
     
    Marshal
    Posts: 15630
    264
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I'm seeing a familiar pattern here. When I facilitate the Global Day of CodeRetreat, people always seem to get stuck on the input/output functionality. I'm not sure why but it seems to me it's the path of least resistance and it fits with a certain mental model they have of the program they want to create. In that mental model, input/output is tightly coupled to the design. You can only break free of this constraint if you throw out that idea and think of input/output as a separate concern, one that can be replaced for the purpose of testing.

    Here's what I mean by all that.

    When I read this problem, I immediately separate the input/output concern from the "solve the problem" concern. To me, input/output is not part of the solution. It's an infrastructure detail. Therefore, in my test infrastructure, I will use something that can stand in for the actual input. How? Well, that separation of concerns design might be expressed with something like this:

    This rough design now allows me to concentrate on one test case at a time which means the logic for breaking down a stream of input that contains multiple test cases will be separate from the logic of actually looking for an Eulerian Path. I may find out later on that this is still not a good enough separation of concerns and refactor further but at least now I don't have to worry about "testing with a stream of input" and can focus on the real meat of the problem.
     
    Junilu Lacar
    Marshal
    Posts: 15630
    264
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Junilu Lacar wrote:I may find out later on that this is still not a good enough separation of concerns and refactor further


    Of course, I immediately find it so (Caveat: I'm not actually working the problem on the computer, just in my head). I can imagine trying to implement solutionFor(String) and finding out I need to use a Scanner to break the string up into vertices and edges. That might drive me to change the design/tests to something like this instead:

    and production code might be something like this:
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Hi guys!
    I am sorry, I need to get back to you tomorrow, another impending deadline. Thank you for your replies 😀😀
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thank you for all the help.
    I agree with you Junilu and Stefan, of course there should be a structured solution with several methods to tests and not a single blog.

    The problem I was describing was, how to write a "stream test"? So I can design a streaming of different graphs in the test-methods (and at the same time, use streams). Like the lambda streams we talked about last year(?).

    But maybe, if I understand you well Junilu, I do not need that and write tests that will run "in cascade"?
     
    Junilu Lacar
    Marshal
    Posts: 15630
    264
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    You seem to have made up your mind that your input is a Stream. It's not. It's a String. You could certainly turn that String into a Stream but I see no point in doing so. In fact, I think that will just complicate things for you. I'd stick with String and Scanner.
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Well, that's true.  i guess I love the idea of Java streams.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12008
    257
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I guess if you REALLY wanted to, you could do something like this:
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12008
    257
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    And here is UndirectedMultigraph:
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thank you Stefan and Junilu.
    I managed to build the algorithm with crap tests but now it's way too slow. And I cannot figure out where since it's O(n)
     
    Junilu Lacar
    Marshal
    Posts: 15630
    264
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    @Stephan Why an undirected graph? If you look at the first test with 4 vertices and 4 edges, 0-1, 1-2, 1-3, and 2-3, and the expected result of "Impossible," then it has to be directed graph because an undirected would have at least a couple of Eulerian paths.
     
    Junilu Lacar
    Marshal
    Posts: 15630
    264
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    D.J. Quavern wrote:I managed to build the algorithm with crap tests but now it's way too slow. And I cannot figure out where since it's O(n)


    Would you care to share what you've done?
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12008
    257
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    You're correct Junilu. I didn't look at the assignment closely enough.

    The updated graph:
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    @Junilu: absolutely. I will post my graph, and the eulerian graphs I tested it against. It passes the first test and the eulerian graphs I use as example, but on the secret tests it is caught either in an infinite loop or is too slow.
    Please remember that it is ugly code as usual!!

    @Stephan: thank you for your beautiful graph. This is beautiful flow, especially in your toString() method!! I noted that it was undirected last time but I was looking at your way to do the streams so it was of no consequence.
    Also, I mispelled your name last time because in my language Stephan is usually with an f! My bad!!
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12008
    257
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    It's wrong though. The last .map(Object::toString) operation should instead be .map(origin -> origin + " -> "). This is probably a cleaner implementation:

    The irony is that I would have found it out before I posted the code, had I written tests first.
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thank you, I did not have time to notice it was wrong, I was at one of those extra relaxing week-ends without computer  
    Here is the kattio class (for input output): https://github.com/Kattis/kattio/blob/master/Kattio.java?fbclid=IwAR0sR7yghgHpkrJhJLmJOOsMD4qyCKdXa4jqouaf2uaFsEvyoLhiSM9AE58


    Here is the code:

     
    Bartender
    Posts: 3959
    155
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    hi DJ,

    I gave your latest code a look, and don't worry: it is easy to follow code!

    I haven't tested it yet, but there are three things that I wonder if you took these into consideration:

    1) even when every node has a zero in-out difference, it does not mean there is a path. For instance, if we have the edges 0-1, 1-0, 2-3, 3-2, then the graph is not connected and so has no solution.

    2) And in dfs, if at has an outgoing = 0, that does not mean the dfs is over! For instance: if we have the edges 0-1, 1-0. 1-2, 2-1 and we go from 0 to 1 and from 1 to 0, then 0 has no more outgoings. However, the solution is: 1-0-1-2-1. There is an algo, O(N), that says if your loop gets stuck, and not all edges have been used, then look for a vertex in that loop that has still some outgoings, then go on with that vertex, and merge the loops.

    3) As I recall, the constraints may be 50.000 edges. That means in the worst case a recursion depth of 50.000. And that may fail.
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Hi Piet!
    Thank you for those bugs I am testing and considerating throughly    
    And thanks for saying it's easy to follow, does not happen often I can say :p

    Piet Souris wrote:hi DJ,

    I gave your latest code a look, and don't worry: it is easy to follow code!

    I haven't tested it yet, but there are three things that I wonder if you took these into consideration:

    1) even when every node has a zero in-out difference, it does not mean there is a path. For instance, if we have the edges 0-1, 1-0, 2-3, 3-2, then the graph is not connected and so has no solution.

    2) And in dfs, if at has an outgoing = 0, that does not mean the dfs is over! For instance: if we have the edges 0-1, 1-0. 1-2, 2-1 and we go from 0 to 1 and from 1 to 0, then 0 has no more outgoings. However, the solution is: 1-0-1-2-1. There is an algo, O(N), that says if your loop gets stuck, and not all edges have been used, then look for a vertex in that loop that has still some outgoings, then go on with that vertex, and merge the loops.


    3) As I recall, the constraints may be 50.000 edges. That means in the worst case a recursion depth of 50.000. And that may fail.



    1: this should be tested in line 53, the eulerian path should be one arc longer than the number of edges + 1 (since a path of n edges goes between n+1 nodes). I tested the below path you proposed and it gives "Impossible".


    2: I tested this one as well and it works, it seems to pluck the latest possibility from the possible departures array. I add a picture of dry-testing. Aka on paper (picture attached)

    3. that's probably the problem. I don't know how to manage those recursions, any advice? I can't do stack increase injection    (if such procedure exists!)


    _20200622_094027.JPG
    [Thumbnail for _20200622_094027.JPG]
     
    Piet Souris
    Bartender
    Posts: 3959
    155
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    hi DJ,

    these drawings of yours are always of the highest quality! It would make Picasso very jealous, if you ask me.    

    For your points:

    1) yes, your routine will discover that, but maybe only after a while, while you could test for it in the inputstage. But it is fine as it is.

    2) If you look at your drawing, you see that 1 has neighbors 0 and 2. Since you pick the last one, you go from 1 to 2, and your dfs succeeds. However, if in the input the edges 1-0 and 1-2 were switched, then 1's neighbors would have been 2 and 0, and then you would get the sequence 0-1-0.

    3) suppose you have a status, say an enum {FINISHED, STILL_BUSY}, and that you add two parameters to your dfs method: currentDepth and maxDepth. The dfs can then return for two reasons: either it is finished, and before returning, it changes the status to FINISHED, or it has reached maxDepth, and it returns with the status unchanged (i.e. STILL_BUSY).
    From your main, you can have something like;
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Piet Souris wrote:hi DJ,

    these drawings of yours are always of the highest quality! It would make Picasso very jealous, if you ask me.    

    For your points:

    1) yes, your routine will discover that, but maybe only after a while, while you could test for it in the inputstage. But it is fine as it is.

    2) If you look at your drawing, you see that 1 has neighbors 0 and 2. Since you pick the last one, you go from 1 to 2, and your dfs succeeds. However, if in the input the edges 1-0 and 1-2 were switched, then 1's neighbors would have been 2 and 0, and then you would get the sequence 0-1-0.

    3) suppose you have a status, say an enum {FINISHED, STILL_BUSY}, and that you add two parameters to your dfs method: currentDepth and maxDepth. The dfs can then return for two reasons: either it is finished, and before returning, it changes the status to FINISHED, or it has reached maxDepth, and it returns with the status unchanged (i.e. STILL_BUSY).
    From your main, you can have something like;



    1. Please explain how I can do it?

    2. I tested it (not on paper sorry), it skips 0 it seems between line 14 and 15, since "0" has no outgoing paths left.


    3. I am not sure I know how to do that (== I have no clue!!). But what if the solution is at max_depth + 1?
     
    Piet Souris
    Bartender
    Posts: 3959
    155
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    hi DJ,

    I gave your dfs another look, and I noticed I misunderstood the exact workings. So, forget my remarks, they are nonsense. Well done for coming up with that recursion!

    But that means that my way of splitting up the recursion into manageble groups fails, for your dfs requires the full history in order to work.

    So I devised a way where that history is not needed, by writing a vertex directly to the ouputpath before going into the recursion. The code is now:

    and my dfs looks like:

    Have tested it for the vertices 0-1, 1-0, 1-2, 2-1 and for 0-1, 1-0, 2-3, 3-2.

    I am stting up a test where we have 20.000 vertices with edges i - (i + 1) for i = 0... 20.000 and a recursion depth of 1000. But that input can't be read from a txt-file, so must break into my code. I let you know!

    O ja: my test for connectedness has the same order as the dfs itself, so that is not very useful, it would only double the run time.
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Oh Piet   , I wish I came up with it but I listen to a course by William Fiset and reproduced his algorithm. And then it took some time to understand the routine.  

    Do you think that if max depth is reached then it can be a sign that the problem has no solution?

     
    Piet Souris
    Bartender
    Posts: 3959
    155
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    good afternoon, DJ,

    no, reaching maxDepth says nothing about there being a solution or not. If the number of edges is larger than maxDepth, then the rourine simply isn't over yet when reaching maxDepth. And if the number of edges is smaller than maxDepth, then maxDepth will never be reached.

    Have you thought about a non-recursive solution, that does not suffer from a too deep recursion level?

    Still have to perform my test, I'm in a pretty lazy mood these days (months)
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Piet Souris wrote:good afternoon, DJ,

    no, reaching maxDepth says nothing about there being a solution or not. If the number of edges is larger than maxDepth, then the rourine simply isn't over yet when reaching maxDepth. And if the number of edges is smaller than maxDepth, then maxDepth will never be reached.

    Have you thought about a non-recursive solution, that does not suffer from a too deep recursion level?

    Still have to perform my test, I'm in a pretty lazy mood these days (months)



    I know the feeling, difficult to stay motivated with the state of the world... :/

    So an iterative dfs?
     
    Piet Souris
    Bartender
    Posts: 3959
    155
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Yes, something like:

    with getNextVertex delivering the next vertex, setting the status to FINISHED when that vertex is the last one.
     
    Piet Souris
    Bartender
    Posts: 3959
    155
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Well, I did my test with 20_001 vertices and with edges  (i -> i + 1) for i = 0...19_999.

    it ran for maxDepth = 4_000, but gave a StackOverflow for maxDepth = 5_000.

    And finally: you can do that stepwise recursion also in your original recursion, with some adaptions.
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    It's really weird I did not get a notification for your reply!

    I will try to use the graph created by Fiset, it is basically the same since I followed his lecture and reimplemented it.
     
    Creator of Enthuware JWS+ V6
    Posts: 3341
    303
    Android Eclipse IDE Chrome
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Congratulations D.J. Quavern,

    Your question has made it to our Journal

    Have a Cow!
     
    D.J. Quavern
    Master Rancher
    Posts: 300
    16
    IntelliJ IDE Firefox Browser Java
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Haha now I feel intense pressure to solve it! Thanks for the cow, I will call her Pepa 😀.
     
    Why fit in when you were born to stand out? - Seuss. Tiny ad:
    Devious Experiments for a Truly Passive Greenhouse!
    https://www.kickstarter.com/projects/paulwheaton/greenhouse-1
      Bookmark Topic Watch Topic
    • New Topic