How to group flatten list

Question

My Flight class looks like:

public class Flight{     
     public string From {get;set;}
     public string To {get;set;}
}

I have flatten list of Flight which are composed n Flight (Note: Flight n may have n From - To)

var listOfFromTo = new List<Flight>{

new Flight{ From = "A", To="B"},
new Flight{ From="B", To="C"},

new Flight{ From="D", To="E"},
new Flight{ From="E", To="F"},
new Flight{ From="F", To="G"}   

//new Flight {From="...", To="..."}
};

What I want to achive is:

var listOfListOfFlights = new List<List<Flight>>(){flight1, flight2};

Where flight1 and flight2 are

var flight1 = new List<Flight>{
    new Flight{ From="A", To="B"},      
    new Flight{ From="B", To="C"}       
};


var flight2 = new List<Flight>{
    new Flight{ From="D", To="E"},
    new Flight{ From="E", To="F"},
    new Flight{ From="F", To="G"}   
};

I can not figure out about how to do it but I can guess I should use group by somehow

var result1 =
    from loft in listOfFromTo
    group loft by new { loft.From, loft.To }
        into r
        select new Flight {
            From = r.Key.From,
            To = r.Key.To
        };

EDIT I would like to share @bit's algorithm's result in linqpad:

So would you be specifying the *From* and *To* as inputs and obtaining the entire route, given a list of Flights? — bit, Apr 26 '16 at 08:39
Exactly, then end user can choose one option to go destination — asdf_enel_hak, Apr 26 '16 at 08:40
@asdf_enel_hak Then your projection to a `List>` would be too much work beforehand. You will be calculating a lot of paths that might never be used. Better think about projecting into a `Dictionary` and traverse the hierarchy to find all possible paths on demand. — Good Night Nerd Pride, Apr 26 '16 at 08:46
@Abbondanza Could be used aggregate or recursive. Maybe I should add a field to Flight Class which says which step it is... — asdf_enel_hak, Apr 26 '16 at 08:55
Actually what you want to do is a graph search to find all possible paths between two nodes in a directed graph. Try somethin like [Breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search). — Good Night Nerd Pride, Apr 26 '16 at 09:05
[This answer](http://stackoverflow.com/questions/713508/find-the-paths-between-two-given-nodes) might be helpful. — Good Night Nerd Pride, Apr 26 '16 at 09:06

bit · Answer 1 · 2016-04-26T09:24:24.810

As per the comments, you will need a little modifcation to your Flight class to accommodate the sub flights that indicate a new route. Here is the update Flight class

public class Flight
{
    public string From { get; set; }
    public string To { get; set; }

    // Sub routes
    public List<Flight> Flights { get; set; }
}

Here is a rough draft of the method which takes the inputs from and to and list of all the flights and the recursively computes the desired route

private List<Flight> GetRoute(string from, string to, IEnumerable<Flight> allFlights)
{
    // Check if the route already exists! 
    var desiredRoute = allFlights.FirstOrDefault(r => r.From == from && r.To == to);
    if (desiredRoute != null)
    {
        return desiredRoute.Flights ?? new List<Flight> { desiredRoute };
    }

    // use inner join to find possible matches with the from and to with the currently available flights/routes
    var routes = allFlights.Join(allFlights, f1 => f1.To, f2 => f2.From, (f1, f2) =>
                            new Flight
                            {
                                // New route found
                                From = f1.From,
                                To = f2.To,

                                // sub Flights for the new route
                                Flights = new List<Flight> { f1, f2 }
                            }).ToList();

    // start a new search with the newly found routes
    return GetRoute(from, to, allFlights.Concat(routes));
}

here is how you can call it:

var route = GetRoute("D", "G", listOfFromTo);

here is a snippet to display the results:

foreach (var flight in routes)
{
    Console.WriteLine(flight.From + "=>" + flight.To);
}

Note that you will have to handle the scenario where no route could be found, otherwise it will result in a stack overflow!

@bit, the GetRoute method you show seems to be only one direction A-Z, if you try a route that goes from E->B you would more likely run into an out of memory exception from the recursion. — Kixoka, Apr 26 '16 at 09:59
@bit Please check edit in quesiton to see result of algorithm — asdf_enel_hak, Apr 26 '16 at 10:52
@bit Thanks for the immense work +1, I think your algorithm is very close requirement, I think I should noodle on it sometimes. — asdf_enel_hak, Apr 26 '16 at 11:23

How to group flatten list

1 Answers1