{"action":"created","issue":{"url":"https://api.github.com/repos/CanalTP/navitia/issues/1159","labels_url":"https://api.github.com/repos/CanalTP/navitia/issues/1159/labels{/name}","comments_url":"https://api.github.com/repos/CanalTP/navitia/issues/1159/comments","events_url":"https://api.github.com/repos/CanalTP/navitia/issues/1159/events","html_url":"https://github.com/CanalTP/navitia/issues/1159","id":104738496,"number":1159,"title":"Thermometer journey_patern order inconsistence ","user":{"login":"xavierraffin","id":1170030,"avatar_url":"https://avatars.githubusercontent.com/u/1170030?v=3","gravatar_id":"","url":"https://api.github.com/users/xavierraffin","html_url":"https://github.com/xavierraffin","followers_url":"https://api.github.com/users/xavierraffin/followers","following_url":"https://api.github.com/users/xavierraffin/following{/other_user}","gists_url":"https://api.github.com/users/xavierraffin/gists{/gist_id}","starred_url":"https://api.github.com/users/xavierraffin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/xavierraffin/subscriptions","organizations_url":"https://api.github.com/users/xavierraffin/orgs","repos_url":"https://api.github.com/users/xavierraffin/repos","events_url":"https://api.github.com/users/xavierraffin/events{/privacy}","received_events_url":"https://api.github.com/users/xavierraffin/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":6,"created_at":"2015-09-03T16:53:42Z","updated_at":"2015-09-04T15:37:06Z","closed_at":null,"body":"In thermometer of the following \r\n\r\n    {1,2},{3,2},{0,1,2},{0,3,2}\r\nis\r\n\r\n    {0,1,3,2}\r\n\r\nBut thermometer of  (two last are inverted)\r\n\r\n      {1,2},{3,2},{0,3,2},{0,1,2}\r\nis\r\n\r\n    {1,0,1,3,2}\r\n\r\nThe last one cause bad things in route_schedules (same stop displayed twice)\r\n\r\nThe thermometer algorithm looks touchy, so I would like to agree with you that this behaviour is wrong before doing something.\r\n\r\nMy proof, these tests pass :\r\n\r\n```\r\n\r\nBOOST_AUTO_TEST_CASE(t16) {\r\n    Thermometer t;\r\n    std::vector<vector_idx> req;\r\n    req.push_back({1,2});\r\n    req.push_back({3,2});\r\n    req.push_back({0,3,2});\r\n    req.push_back({0,1,2});\r\n\r\n    t.generate_thermometer(req);\r\n    auto result = t.get_thermometer();\r\n\r\n    BOOST_REQUIRE_EQUAL(result[0], 1);\r\n    BOOST_REQUIRE_EQUAL(result[1], 0);\r\n    BOOST_REQUIRE_EQUAL(result[2], 1);\r\n    BOOST_REQUIRE_EQUAL(result[3], 3);\r\n    BOOST_REQUIRE_EQUAL(result[4], 2);\r\n}\r\n\r\nBOOST_AUTO_TEST_CASE(t17) {\r\n    Thermometer t;\r\n    std::vector<vector_idx> req;\r\n    req.push_back({1,2});\r\n    req.push_back({3,2});\r\n    req.push_back({0,1,2});\r\n    req.push_back({0,3,2});\r\n\r\n    t.generate_thermometer(req);\r\n    auto result = t.get_thermometer();\r\n\r\n    BOOST_REQUIRE_EQUAL(result[0], 0);\r\n    BOOST_REQUIRE_EQUAL(result[1], 1);\r\n    BOOST_REQUIRE_EQUAL(result[2], 3);\r\n    BOOST_REQUIRE_EQUAL(result[3], 2);\r\n}\r\n\r\n```\r\n\r\n\r\n\r\n\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/CanalTP/navitia/issues/comments/137770730","html_url":"https://github.com/CanalTP/navitia/issues/1159#issuecomment-137770730","issue_url":"https://api.github.com/repos/CanalTP/navitia/issues/1159","id":137770730,"user":{"login":"xavierraffin","id":1170030,"avatar_url":"https://avatars.githubusercontent.com/u/1170030?v=3","gravatar_id":"","url":"https://api.github.com/users/xavierraffin","html_url":"https://github.com/xavierraffin","followers_url":"https://api.github.com/users/xavierraffin/followers","following_url":"https://api.github.com/users/xavierraffin/following{/other_user}","gists_url":"https://api.github.com/users/xavierraffin/gists{/gist_id}","starred_url":"https://api.github.com/users/xavierraffin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/xavierraffin/subscriptions","organizations_url":"https://api.github.com/users/xavierraffin/orgs","repos_url":"https://api.github.com/users/xavierraffin/repos","events_url":"https://api.github.com/users/xavierraffin/events{/privacy}","received_events_url":"https://api.github.com/users/xavierraffin/received_events","type":"User","site_admin":false},"created_at":"2015-09-04T15:37:06Z","updated_at":"2015-09-04T15:37:06Z","body":"Great.\nI don't know if I will have enough spare time to do it soon.\n\nI will tell you in Paris the 17th.\n\nKeep in touch ;-)\n\n2015-09-04 17:28 GMT+02:00 Guillaume P. <notifications@github.com>:\n\n> OK, I've found an algorithm that should be quite easy to implement, and\n> will be always better that the current algorithm. If there is a solution\n> when no stop point are repeated, the algorithm will find it. Else, the\n> algorithm fail, and we launch the old one.\n>\n>    1. Create a graph\n>    <http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/table_of_contents.html>\n>    with a node for each stop point. For each successive stop points in a JP,\n>    create an arc between the 2 corresponding nodes.\n>    2. Do a topological sort\n>    <http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/topological_sort.html>\n>    on this graph.\n>       - If the graph contains a cycle, the topological sort fail, and\n>       there is no solution possible to the thermometer without duplicating at\n>       least one stop point. In this case, we launch the current algorithm.\n>       - Else, the order of the topological sort is a correct order\n>       without duplication of stop point. Return it.\n>\n> For your example {1,2},{3,2},{0,3,2},{0,1,2}, you'll generate this graph:\n>\n> 0 --> 3\n> |     |\n> V     V\n> 1 --> 2\n>\n> And the topological sort gives 0 -> 1 -> 3 -> 2 (or 0 -> 3 -> 1 -> 2) as\n> wanted.\n>\n> If you want, you can code that, and I'll be happy to review it. Else, I'll\n> do that when I'll have the time.\n>\n> —\n> Reply to this email directly or view it on GitHub\n> <https://github.com/CanalTP/navitia/issues/1159#issuecomment-137767920>.\n>\n"}}