none
How to count the Path between two points using IReadOnlyList<InterfaceSample>? RRS feed

  • Question

  • I have a two points called stations where I need to count the distance between two different ones in the same city with specific set of rules in three functions GetShortestPath(IStation from, IStation to) and GetFastestPath(IStation from, IStation to) in the class City.
    The rules for the functions of GetShortestPath & GetFastestPath:
    - from point (0,0)
    - none of the stations (point A from & point B to) cannot be null
    - the path has to be at one line
    - no path between stations without a line 
    ** based on following unit test

    public void T1_path_to_where_i_am()
    {
        ICity c = CityFactory.CreateCity("Paris");
        IStation s = c.AddStation("Opera", 0, 0);
        c.GetShortestPath(s, s).Single().Should().BeSameAs(s);
    }
    public void T2_cant_get_path_from_and_or_to_null()
    {
        ICity c = CityFactory.CreateCity("Paris");
        IStation s = c.AddStation("Opera", 0, 0);
        Action action = (() => c.GetShortestPath(s, null));
        action.ShouldThrow<ArgumentException>();
        action = (() => c.GetShortestPath(null, s));
        action.ShouldThrow<ArgumentException>();
        action = (() => c.GetShortestPath(null, null));
        action.ShouldThrow<ArgumentException>();
    }
    public void T3_get_path_to_station_on_same_line()
    {
        ICity c = CityFactory.CreateCity("Paris");
        IStation s1 = c.AddStation("Opera", 0, 0);
        IStation s2 = c.AddStation("Chatelet", 10, 10);
        IStation s3 = c.AddStation("Gare de Lyon", 20, 20);
        ILine l = c.AddLine("RER A");
        l.AddBefore(s1);
        l.AddBefore(s2);
        l.AddBefore(s3);
        var path = c.GetShortestPath(s1, s2);
        path.Count.Should().Be(2);
        (path[0] == s1 && path[1] == s2).Should().BeTrue();
        path = c.GetShortestPath(s2, s1);
        (path.Count == 2).Should().BeTrue();
        (path[0] == s2 && path[1] == s1).Should().BeTrue();
        path = c.GetShortestPath(s1, s3);
        (path.Count == 3).Should().BeTrue();
        (path[0] == s1 && path[1] == s2 && path[2] == s3).Should().BeTrue();
        path = c.GetShortestPath(s3, s1);
        (path.Count == 3).Should().BeTrue();
        (path[0] == s3 && path[1] == s2 && path[2] == s1).Should().BeTrue();
        path = c.GetShortestPath(s2, s3);
        (path.Count == 2).Should().BeTrue();
        (path[0] == s2 && path[1] == s3).Should().BeTrue();
    }
    public void T4_can_go_to_station_on_another_line()
    {
        ICity c = CityFactory.CreateCity("Paris");
        IStation s1 = c.AddStation("Opera", 0, 0);
        IStation s2 = c.AddStation("Chatelet", 10, 10);
        IStation s3 = c.AddStation("Gare du nord", 20, 20);
        ILine l1 = c.AddLine("RER A");
        ILine l2 = c.AddLine("RER B");
        l1.AddBefore(s1);
        l1.AddBefore(s2);
        l2.AddBefore(s2);
        l2.AddBefore(s3);
        var path = c.GetShortestPath(s1, s2);
        (path.Count == 2).Should().BeTrue();
        (path[0] == s1 && path[1] == s2).Should().BeTrue();
        path = c.GetShortestPath(s2, s1);
        (path.Count == 2).Should().BeTrue();
        (path[0] == s2 && path[1] == s1).Should().BeTrue();
        path = c.GetShortestPath(s1, s3);
        (path.Count == 3).Should().BeTrue();
        (path[0] == s1 && path[1] == s2 && path[2] == s3).Should().BeTrue();
        path = c.GetShortestPath(s3, s1);
        (path.Count == 3).Should().BeTrue();
        (path[0] == s3 && path[1] == s2 && path[2] == s1).Should().BeTrue();
        path = c.GetShortestPath(s2, s3);
        (path.Count == 2).Should().BeTrue();
        (path[0] == s2 && path[1] == s3).Should().BeTrue();
    }
    public void T5_no_path_between_stations_wih_no_line()
    {
        ICity c = CityFactory.CreateCity("Paris");
        IStation s = c.AddStation("Opera", 0, 0);
        IStation s1 = c.AddStation("Chatelet", 10, 10);
        var path = c.GetShortestPath(s, s1);
        (path.Count == 0).Should().BeTrue();
        ILine l = c.AddLine("RER A");
        l.AddBefore(s);
        path = c.GetShortestPath(s, s1);
        (path.Count == 0).Should().BeTrue();
        ILine l1 = c.AddLine("RER b");
        l1.AddBefore(s1);
        path = c.GetShortestPath(s, s1);
        (path.Count == 0).Should().BeTrue();
    }
    public void T6_shortest_path_complexe_map()
    {
        ICity city = CityFactory.CreateCity("Paris");
        IStation a = city.AddStation("A", 0, 0);
        IStation b = city.AddStation("B", 0, 10);
       
        ILine l1 = city.AddLine("ligne 1");
        l1.AddBefore(a);
        l1.AddBefore(b);
      
        var path = city.GetShortestPath(a, b);
        (path.Count == 2).Should().BeTrue();
        (path[0] == a && path[1] == b && path[2] == c && path[3] == d).Should().BeTrue();
        IStation e = city.AddStation("E", 5, 5);
        ILine l2 = city.AddLine("ligne 2");
        l2.AddBefore(a);
        l2.AddBefore(e);
        l2.AddBefore(d);
        path = city.GetShortestPath(a, b);
        (path.Count == 3).Should().BeTrue();
        (path[0] == a && path[1] == e && path[2] == d).Should().BeTrue();
        ILine l3 = city.AddLine("ligne 3");
        l3.AddBefore(a);
        l3.AddBefore(b);
        path = city.GetShortestPath(a, d);
        (path.Count == 2).Should().BeTrue();
        (path[0] == a && path[1] == b).Should().BeTrue();
    }

    My place to apply all those rules is in the class City in three functions:

    public IReadOnlyList<IStation> GetFastestPath(IStation from, IStation to)
    {
        throw new NotImplementedException();
    }
    public IReadOnlyList<IStation> GetShortestPath(IStation from, IStation to)
    {
        throw new NotImplementedException();
    }

    Friday, January 3, 2020 4:11 PM

Answers

  • There isn't sufficient information here to help you. What is your algorithm for finding fastest/shortest path? We tend not to do the actual work for people but instead guide them in what they need to do. You also haven't provided any info on what an IStation is as to know whether station A is farther/slower than station B. Only you know those rules.

    As for farthest, if this is a node hoping thing then you can google for node traversal algorithms for finding shortest path. But this assumes all nodes are the same distance apart. For example if station A to station B requires going through either station C or stations D and E then it is shorter to use C only if the distance from station A to B through C is < station A + station D + station E + station B. That means you need a "cost" for each link as well. Again there are plenty of tree algorithms that can calculate cost that you can google. You'll need to decide which algorithm works best for you.


    Michael Taylor http://www.michaeltaylorp3.net

    • Marked as answer by BarbraFleg Friday, January 10, 2020 8:45 AM
    Friday, January 3, 2020 6:09 PM
    Moderator
  • You're missing some code.  In your T6 test, the code refers to "c" and "d", which are never created.

    Michael is right.  There are lots of examples of a "breadth-first search" to do solve these kinds of problems.  The basic problem is that there are no shortcuts.  You have to try EVERY combination of stations to find the shortest path.  In the general case, that means stepping out one step at a time to every station you can reach from the current location, remembering which paths you have to check next, and looping until you get to the end.

    But if all you have to worry about is at most 5 stations, it would be quicker just to TRY all possible combinations of the 5 stations.  Since you know where you're starting, that's only 4! or 24 combinations.  You can imagine how the code might look:

    foreach( var n1 in stations )
        if( n1 == from )
            continue;
        if( there is no line from "from" to "n1" )
            continue;
        dist = distance along the path;
        if( n1 == to && dist < shortest distance do far )
            save possible solution; path is (from, n1)
            continue
        foreach( var n2 in stations )
            if( n2 == from || n2 == n1 )
                continue
            if( there is no line from "n1" to "n2" )
                continue
            dist += distance along the path
            if( n2 == to && dist < shortest distance so far )
                save possible solution; path is (from, n1, n2)
                continue

    And so on.  Not terribly complicated.  You could even simplify it by writing a function that returns "all the lines from station X".  Then the inner loops become

        foreach( var n1 in lines_from(from) )
            ...
            foreach( var n2 in lines_from(n1) )


    Tim Roberts | Driver MVP Emeritus | Providenza &amp; Boekelheide, Inc.


    • Edited by Tim Roberts Monday, January 6, 2020 11:39 PM
    • Marked as answer by BarbraFleg Friday, January 10, 2020 8:45 AM
    Monday, January 6, 2020 11:38 PM
  • I responded in your other thread.  You are computing the minimum, but you aren't saving the result.  Plus, this solution does not remember the station that was the closest, which is what you really want to know.

    Tim Roberts | Driver MVP Emeritus | Providenza &amp; Boekelheide, Inc.

    • Marked as answer by BarbraFleg Thursday, January 9, 2020 9:56 AM
    Wednesday, January 8, 2020 7:46 PM

All replies

  • There isn't sufficient information here to help you. What is your algorithm for finding fastest/shortest path? We tend not to do the actual work for people but instead guide them in what they need to do. You also haven't provided any info on what an IStation is as to know whether station A is farther/slower than station B. Only you know those rules.

    As for farthest, if this is a node hoping thing then you can google for node traversal algorithms for finding shortest path. But this assumes all nodes are the same distance apart. For example if station A to station B requires going through either station C or stations D and E then it is shorter to use C only if the distance from station A to B through C is < station A + station D + station E + station B. That means you need a "cost" for each link as well. Again there are plenty of tree algorithms that can calculate cost that you can google. You'll need to decide which algorithm works best for you.


    Michael Taylor http://www.michaeltaylorp3.net

    • Marked as answer by BarbraFleg Friday, January 10, 2020 8:45 AM
    Friday, January 3, 2020 6:09 PM
    Moderator
  • Thank you for suggestions. I was looking to get some guidance not a solution. There is no other rules about the distance then I shared. The outcome of this exercise is to pass the unit test.
    Monday, January 6, 2020 11:51 AM
  • You're missing some code.  In your T6 test, the code refers to "c" and "d", which are never created.

    Michael is right.  There are lots of examples of a "breadth-first search" to do solve these kinds of problems.  The basic problem is that there are no shortcuts.  You have to try EVERY combination of stations to find the shortest path.  In the general case, that means stepping out one step at a time to every station you can reach from the current location, remembering which paths you have to check next, and looping until you get to the end.

    But if all you have to worry about is at most 5 stations, it would be quicker just to TRY all possible combinations of the 5 stations.  Since you know where you're starting, that's only 4! or 24 combinations.  You can imagine how the code might look:

    foreach( var n1 in stations )
        if( n1 == from )
            continue;
        if( there is no line from "from" to "n1" )
            continue;
        dist = distance along the path;
        if( n1 == to && dist < shortest distance do far )
            save possible solution; path is (from, n1)
            continue
        foreach( var n2 in stations )
            if( n2 == from || n2 == n1 )
                continue
            if( there is no line from "n1" to "n2" )
                continue
            dist += distance along the path
            if( n2 == to && dist < shortest distance so far )
                save possible solution; path is (from, n1, n2)
                continue

    And so on.  Not terribly complicated.  You could even simplify it by writing a function that returns "all the lines from station X".  Then the inner loops become

        foreach( var n1 in lines_from(from) )
            ...
            foreach( var n2 in lines_from(n1) )


    Tim Roberts | Driver MVP Emeritus | Providenza &amp; Boekelheide, Inc.


    • Edited by Tim Roberts Monday, January 6, 2020 11:39 PM
    • Marked as answer by BarbraFleg Friday, January 10, 2020 8:45 AM
    Monday, January 6, 2020 11:38 PM
  • I responded in your other thread.  You are computing the minimum, but you aren't saving the result.  Plus, this solution does not remember the station that was the closest, which is what you really want to know.

    Tim Roberts | Driver MVP Emeritus | Providenza &amp; Boekelheide, Inc.

    • Marked as answer by BarbraFleg Thursday, January 9, 2020 9:56 AM
    Wednesday, January 8, 2020 7:46 PM