How to sort collection based on next property?

Question

I am trying to calculate the best route to take between all stops w/ GeoCoordinates in C#.

I have some methods which get the next closest location in a list, but I need to be able to sort my original list by:

start -> next stop -> next stop -> next stop -> finish

---

This is what I'm currently working with:

Models

public class DispatchStopModel
{
    public long OrderDispatchID { get; set; }
    public long? NextDispatchID { get; set; }
    public PhysicalAddress PhysicalAddress { get; set; }
    public double Distance { get; set; }
}

Methods

    private static double DistanceTo(double lat1, double lon1, double lat2, double lon2, char unit = 'M')
    {
        double rlat1 = Math.PI * lat1 / 180;
        double rlat2 = Math.PI * lat2 / 180;
        double theta = lon1 - lon2;
        double rtheta = Math.PI * theta / 180;
        double dist =
            Math.Sin(rlat1) * Math.Sin(rlat2) + Math.Cos(rlat1) *
            Math.Cos(rlat2) * Math.Cos(rtheta);
        dist = Math.Acos(dist);
        dist = dist * 180 / Math.PI;
        dist = dist * 60 * 1.1515;

        switch (unit)
        {
            case 'K': //Kilometers -> default
                return dist * 1.609344;
            case 'N': //Nautical Miles 
                return dist * 0.8684;
            case 'M': //Miles
                return dist;
        }

        return dist;
    }

    private void FindClosestStop(DispatchStopModel start, ICollection<DispatchStopModel> stops)
    {
        if(start.PhysicalAddress?.HasGeocode ?? false)
        {
            foreach(var stop in stops.Where(s => s.OrderDispatchID != start.OrderDispatchID))
            {
                if(stop.PhysicalAddress?.HasGeocode ?? false)
                {
                    double distanceTo = DistanceTo((double)start.PhysicalAddress.Latitude, (double)start.PhysicalAddress.Longitude, (double)stop.PhysicalAddress.Latitude, (double)stop.PhysicalAddress.Longitude);

                    if (distanceTo < start.Distance)
                    {
                        start.Distance = distanceTo;
                        start.NextDispatchID = stop.OrderDispatchID;
                    }
                }
            }
        }
    }

---

Now here is my controller action:

public IActionResult GetDeliveries()
{
    var deliveries = deliveryService.GetYourDeliveries();

    var Stops = Deliveries.Select(d => new DispatchStopModel
    {
        OrderDispatchID = d.OrderDispatchID,
        NextDispatchID = null,
        PhysicalAddress = d.Order.OrderAddress?.PhysicalAddress,
        Distance = double.MaxValue
    })
    .ToArray();


    foreach(var stop in Stops)
    {
        FindClosestStop(stop, Stops);
    }

    //How can I sort on deliveries using the "NextDispatchID" from the collection I just generated?
}

---

What I was thinking is that I could setup a new list, and manually insert each delivery where the OrderDispatchID equals the OrderDispatchID of the stop. I feel like this would be inefficient though.

Thoughts on the proper way to do this?

Thanks in advance,

Answer 1

Looking at your question from a high level, it seems to me you're really dealing with a linked list, where each item points to a next item.

If this is the case, one way to set the "next" item for each item is: make a copy of all the stops, loop through the original list of stops, assign the closest one in the list copy on each iteration, and then remove that item from the list copy so it doesn't get assigned again:

List<DispatchStopModel> deliveries = deliveryService.GetYourDeliveries();
List<DispatchStopModel> temp = deliveries.ToList();

// Assuming you have a start location
DispatchStopModel start = GetStartingPoint();

// Assign the closest stop to it
FindClosestStop(start, deliveries);

// Now assign the closest delivery for each of the rest
// of the items, removing the closest item on each
// iteration, so it doesn't get assigned more than once.
foreach (var delivery in deliveries)
{
    var closest = FindClosestStop(delivery, temp);
    temp.Remove(closest);
}

After this, all the items should be assigned with a NextDispatchID that points to the next closest delivery point. If you still want to "sort" the list, there are many answers on this site on how to sort a linked list (like this, for example).

Note that I made a slight change to FindClosestStop so that it returns the closest stop found:

private DispatchStopModel FindClosestStop(DispatchStopModel start, 
    ICollection<DispatchStopModel> stops)
{
    DispatchStopModel closest = null;

    // other code ommitted for brevity

    if (distanceTo < start.Distance)
    {
        start.Distance = distanceTo;
        start.NextDispatchID = stop.OrderDispatchID;
        closest = stop;
    }

    // other code ommitted for brevity

    return closest;
}

Also note that Equals and GetHashCode should be overridden on the DispatchStopModel class for the Remove method to work. If you don't want to do that, then you'd need to search for the item with a matching OrderDispatchID and remove it that way.