c# finding appropriate list chain for known points [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

   var route1 = new List<int> { 1, 2, 3 };
   var route2 = new List<int> { 6, 7, 8 };
   var route3 = new List<int> { 3, 7, 13 };
   var route4 = new List<int> { 8, 9, 10 };

Question is that; my origin point is 2 and my target point is 9. My aim is to find appropriate route chain. For this situtation my route will be [route1 - route3 - route2 - route4]. But I don't know how to solve this problem, I cannot find an algorithm. Answer can be pseudo code or c# implemantation.

My way is that; my start point (2) in route1, and my target point (9) in route4. Then I need to find middle route(s) which connects route1 and route4. I need algorithm or technique..

Answer 1

This code will find the routes between any two points, should one exist. The route may not always be the shortest (for instance from 3 to 13 will give route1 to route3). It also uses recursion - which seems to be something you wanted (based on your tags). vistedRoutes contains the routes traversed.

   static void Main(string[] args)
    {
        var route1 = new List<int> { 1, 2, 3 };
        var route2 = new List<int> { 6, 7, 8 };
        var route3 = new List<int> { 3, 7, 13 };
        var route4 = new List<int> { 8, 9, 10 };

        List<List<int>> routeList = new List<List<int>>();
        routeList.Add(route1);
        routeList.Add(route2);
        routeList.Add(route3);
        routeList.Add(route4);

        int start = 3;
        int end = 9;

        var vistedRoutes = new List<List<int>>();

        foreach(var route in routeList.FindAll(r => r.Contains(start)))
        {
            vistedRoutes.Add(route);
            routeList.Remove(route);
            FindPath(vistedRoutes, routeList, start, end);

            if (vistedRoutes.Last().Contains(end))
            {
                break;
            }
        }

        Console.WriteLine("done");
    }

    static void FindPath(List<List<int>> visitedRoutes, List<List<int>> remainingRoutes, int start, int end)
    {
        if (visitedRoutes.Last().Contains(end))
        {
            return;
        }
        for (int i = 0; i < remainingRoutes.Count; i++ )
        {
            var route = remainingRoutes[i];

            foreach (var point in route)
            {
                if (visitedRoutes.Last().Contains(point))
                {
                    visitedRoutes.Add(route);
                    var newRemainingRoutes = new List<List<int>>(remainingRoutes);
                    newRemainingRoutes.Remove(route);
                    FindPath(visitedRoutes, newRemainingRoutes, start, end);
                    if (visitedRoutes.Last().Contains(end))
                    {
                        return;
                    }
                    else
                    {
                        visitedRoutes.Remove(route);
                    }
                }
            }
        }
    }

Answer 2

Here you go:

        var route1 = new List<int> { 1, 2, 3 };
        var route2 = new List<int> { 6, 7, 8 };
        var route3 = new List<int> { 3, 7, 13 };
        var route4 = new List<int> { 8, 9, 10 };

        List<List<int>> routeList = new List<List<int>>();
        routeList.Add(route1);
        routeList.Add(route2);
        routeList.Add(route3);
        routeList.Add(route4);

        int startPoint = 2;
        int endPoint = 9;


        List<List<int>> finalRouteOrder = new List<List<int>>();

        //  Find starting route.
        List<int> currentRoute = routeList.Find(a => a.Contains(startPoint));

        //  Don't need that route in the list anymore.
        routeList.Remove(currentRoute);

        //  Add it to our final list of routes.
        finalRouteOrder.Add(currentRoute);

        bool done = false;
        while (!done)
        {
            foreach (int x in currentRoute)
            {
                currentRoute = routeList.Find(a => a.Contains(x));
                if (currentRoute != null)
                {
                    finalRouteOrder.Add(currentRoute);  // add this route toi our final list of routes
                    routeList.Remove(currentRoute);  // remove that list since we are done with it.

                    if (currentRoute.Contains(endPoint))
                    {
                        done = true;
                    }
                    break;
                }
                if (done)
                    break;

            }
            if (done)
                break;
        }

        //  finalRouteOrder contains the routes in order.

        MessageBox.Show("Done.");