7 kyu

Find Center of Star Graph

327 of 373monkey_on_a_keyboard_1
Description
Loading description...
Graph Theory
View
AllIssues3QuestionsSuggestions1Show Resolved
  • Please sign in or sign up to leave a comment.
  • Kees de Vreugd Avatar

    I liked this one. Kind of a tutorial on graph theory for beginners. Since all issues seem to be resolved (a month ago!) I approved.

  • Blind4Basics Avatar

    I was about to approve the kata when I noticed the random graph creation uses O(n²) opeartions, removing in a list. Even if not a problem for a kata not involving performances, it's better to use a more qualitative approach, since the tests of this kata could inspire some other kata authors later.

    Since I don't do C, I cannot update it an resort to opening another issue.

    Solution:

    • build a list of values
    • shuffle the list (in linear time)
    • iterate over the list
    • you can skip the c value from wthin the loop instead of removing it from the list

    Cheers

    • monkey_on_a_keyboard_1 Avatar

      hello Blind4Basics!, thank you for taking the time to look over this and noticing that for me, i made the change to the creating graph function that i wrote (in python) :). I think the translation in C looks ok, it doesn't use list removals to create a graph

    • Blind4Basics Avatar

      'never saw your answer, sorry...

      Issue marked resolved by Blind4Basics 2 years ago
  • Voile Avatar

    Additionally, the graph is given as a star graph, guaranteeing there is one and only one node in the graph which is a center node. The center node is defined as the node with an edge to all other nodes.

    This definition of star graph is insufficient: it establishes that there exists a node that has an edge to all other nodes, but does not tell about the existence of other possible edges in the graph (which is actually ruled out by definition). This does have big implications on how the kata is approached: see the top 2 Python solutions.

  • rowcased Avatar
  • mauro-1 Avatar

    • There should be tests where the center is always first/always second

    • There should be more tests (at least 50-100)

    You can use a loop:

    for _ in range(num_tests):
    graph, expected = ...
    test.assert_equals(center(graph), expected)
    • monkey_on_a_keyboard_1 Avatar

      Thank you, I've added 10 tests each for center always first/always second and also 100 more random tests. I also fixed a small error in a few of the test cases which may have made it possible for a correct solution to fail. Should I add more tests? Thanks for your help! :)

    • Blind4Basics Avatar

      the different batches of random tests should be merged into one, running each kind of test (and not only each kind of group/batch) in random order. Otherwise, the answer to some groups can be hardcoded.

      Simplest way to do this:

      • transform each batch of random tests to a function doing one single test of that kind
      • create a new @test.it block for the random tests
      • build a list of all the random functions ([func1] * n_tests_func1 + [func2] * n_tests_func2 + ...]
      • shuffle that list
      • iterate on the shuffled list and run each function
    • monkey_on_a_keyboard_1 Avatar

      I see, thank you very much I will go fix that now :)

      Edit: Thanks again for your helpful feedback, I've made the changes, and I also added some comments and rewrote the description for clarity.

    • Blind4Basics Avatar
      Issue marked resolved by Blind4Basics 2 years ago