Views: 9319
Number of votes: 5
Average rating:

Welcome aboard EPiServer Find – We hope you’ll have a pleasant flight

Over the last few months EPiServer Find has become my new favorite weapon of choice for many, many coding challenges. It’s so easy – yet so powerful. And as a search geek I love this new way of juggling information around.

One of the latest projects I’ve been working on with Find was a demo site, in the shape of a fictional airline called Fly Find. This was originally @joelabrahamsson ‘s baby, but I’ve been so lucky as to adopt it add a few gimmicks and put it live.

I figured I’d take this chance to give introduce this demo site from a user perspective – as well as give a small peek behind the scenes. So, let’s being the tour…

 

Start of by going to http://flyfind.demo.episerver.com. First thing you should notice is that pretty much everything on this site is driven behind the scenes by Find – both used as a search engine – but more importantly as a tool to allow advanced navigation for users to get to business critical information. Since this is an airline the important stuff is mostly destinations you can fly to – and the actual flights themselves.

image

In the bottom of the result page you’ll find 3 Find-boxes. 2 location based searches, searching for destinations close to (and far away) from your current location – as well as a listing of latest news items. The logic that produces the list is really simple – like in the case of the “Destinations Nearby”:

Destinations = SearchClient.Instance.Search<DestinationPage>()
    .OrderBy(x => x.Coordinates.SearchableLocation)
    .DistanceFrom(UserLocation)
    .Skip(1)
    .Take(4)
    .GetPagesResult();

Note that we skip the first 1, since you probably don’t want to go where you already are Smile

If you go to the “Destinations” page, in the top menu, you’ll get to a page where you can see all destinations – both on a map and in a list. And on the side you have your facets and filters.

image

Try to narrow down into a facet – or slide the temperature bar and see how the list updates on the fly (you guessed right – AJAX). This time, we build up the query in a few more lines of code to get all the filters and facets included.

protected override void  OnLoad(System.EventArgs e)
 {
     base.OnLoad(e);
   
     var query = SearchClient.Instance.Search<DestinationPage>()
             .TermsFacetFor(x => x.Country.Continent)
             .CategoriesFacet()
             .GeoDistanceFacetFor(x => x.Coordinates.SearchableLocation, new GeoLocation(UserLocation.Latitude, UserLocation.Longitude),
             new NumericRange { From = 0, To = 1000 },
             new NumericRange { From = 0, To = 2500 },
             new NumericRange { From = 0, To = 5000 },
             new NumericRange { From = 0, To = 10000 },
             new NumericRange { From = 0, To = 25000 });
 
     query = ApplyFiltersToQuery(query);
     
     Destinations = query.OrderBy(x => x.PageName)
             .Take(500)
             .GetPagesResult();
 }
 
 private ITypeSearch<DestinationPage> ApplyFiltersToQuery(ITypeSearch<DestinationPage> query)
 {
     if (FilterTempRange.Any())
     {
         query = query.Filter(x => x.AvgTemp.InRange(FilterTempRange.First(), FilterTempRange.Last()));
     }
     if (FilterContinents.Any())
     {
         var continentsFilter = SearchClient.Instance.BuildFilter<DestinationPage>();
         foreach (var continent in FilterContinents)
         {
             continentsFilter = continentsFilter.Or(x => x.Country.Continent.Match(continent));
         }
         query = query.Filter(x => continentsFilter);
     }
     if (FilterTravelTypes.Any())
     {
         var travelTypesFilter = SearchClient.Instance.BuildFilter<DestinationPage>();
         foreach (var categoryName in FilterTravelTypes)
         {
             var category = Category.Find(categoryName);
             travelTypesFilter = travelTypesFilter.Or(x => x.InCategory(category));
         }
         query = query.Filter(x => travelTypesFilter);
     }
     if (FilterDistances.Any())
     {
         var distancesFilter = SearchClient.Instance.BuildFilter<DestinationPage>();
         foreach (var distance in FilterDistances)
         {
             distancesFilter =
                 distancesFilter.Or(
                     x =>
                     x.Coordinates.SearchableLocation.WithinDistanceFrom(
                         new GeoLocation(UserLocation.Latitude, UserLocation.Longitude),
                         ((int) distance.From.Value).Kilometers(), ((int) distance.To.Value).Kilometers()));
         }
         query = query.Filter(x => distancesFilter);
     }
     return query;
 }

Even, if you drill down and look at an individual destination, it’s filled with Find navigation like destinations close-by, destinations on same continent and similar destinations (based on their textual contents).

image

In the bottom of the Destination description you’ll also find the Arrivals / Departure board of the relevant airport – but I’ll talk more about flights soon. For now, let’s have a look at the classic Quick Search in the upper right corner.

Start typing and you’ll soon be happily surprised as it searches as you type. Hit enter and it’ll take you to the result page.

image

The Search-as-you-type is made possible with some clever javascript and a nice little http-handler, called QuickSearch.ashx. It searches for any item where the Pagename contains what has been typed – and returns the object..And if it’s a destination it’ll use EPiImage to resize a nice little thumbnail for you (which of course is cached first time generated). We use the base class of all pages on site in the query, EditorialPageBase – to make sure we get them all.

public class Ajax : IHttpHandler
    {
 
        public void ProcessRequest(HttpContext context)
        {
            var query = context.Request.QueryString["q"];
            context.Response.ContentType = "application/json";
            context.Response.ContentEncoding = Encoding.UTF8;
            var result = SearchClient.Instance.Search<EditorialPageBase>()
                .For(query)
                .Include(x => x.PageName.AnyWordBeginsWith(query), null)
                .Take(6)
                .GetPagesResult()
                .Select(x => new
                    {
                        PageName = x.PageName.TruncateAtWord(60), 
                        x.LinkURL, 
                        Category = x.SearchHitType,
                        Text = x.SearchText.TruncateAtWord(110),
                        ImgUrl = x is DestinationPage ? new EPiImageEngine().ResizeImage(70, 55, EPiImageEngine.Transformation.ScaleToFill, ((DestinationPage)x).Image) : ""
                    });
            context.Response.Write(JsonConvert.SerializeObject(result));
        }
 
        public bool IsReusable
        {
            get
            {
                return false;
            }
        }
    }

On the result page we see some other classic features:

  • Autocomplete when typing (based on popular search terms + editorial list).
  • Best Bets – a in the back end an editor has decided that certain pages should come in the top for certain queries.
  • Facets based on the type of result (listed to the right)
  • Spelling corrections (based on popular search terms and an editorial list).
  • Related searches (again based on popular searches as well as a list managed by editors in the backend).
  • Paging
  • Highlighted search word in the results
  • Stemming (for English search terms)

image

Almost all of this stuff is done when the query is being built up:

private void ExecuteSearch()
{
    var result = SearchClient.Instance.Search<EditorialPageBase>(Language.English)
        .For(Query)
        .InFields(x => x.PageName, x => x.MainIntro, x => x.MainBody)
        .InAllField()
        .FilterHits(x => GetTypeFilter())
        .TermsFacetFor(x => x.SearchHitType, facet => facet.AllTerms = true)
        .Select(x => new SearchResult
        {
            Title = FirstNotEmpty(x.PageName.AsHighlighted(), x.PageName),
            Url = x.LinkURL,
            Text = Snippet(x.SearchText.AsCropped(250), //
                           x.SearchText.AsHighlighted(new HighlightSpec { NumberOfFragments = 2, FragmentSize = 120, Concatenation = strings => string.Join(" ... ", strings)})),
            Type = x.SearchHitType
        })
        .ApplyBestBets()
        .Take(Paging.PageSize)
        .Skip((Paging.ActivePageNumber-1)*Paging.PageSize)
        .GetResult();
    Results = result;
    Paging.ItemCount = result.TotalMatching;
}

 

And now lets look at the Flights

So…So far we haven’t done anything really out of the ordinary. It’s all based on a standard installation & index of Find for EPiServer CMS (in this case 6R2 with PageTypeBuilder), spiced up with some fancy querying around the site and made pretty by Twitter Bootstrap and Flickr images. In fact, I’m guessing most of the time spend on the site so far went into finding images with proper license rights and texts – and not really into the coding.

So I figured – why not spice things up a bit and add the one concept that all airlines have: Flights….Lots of flights. That’ll show both indexing content outside EPiServer as well as great performance when doing complex queries against rather large data sets. However, since this is a fictional airline we’ll also need fictional flights. So the first thing I did was to define what a flight was – and wrote a little scheduled job that I can run manually to generate them and index them. Once generated they purely live in Find’s index – although in a real-world scenario they would probably also live in some other big database.

Although I’m a frequent flyer I have never owned my own airline – however it doesn’t take much imagination to come up with what a flight essentially consist of data wise. It’s an aircraft going from 1 place to another at a specific time. Based on the aircraft model it has a certain number of seats, some of them might have already been sold.

public class Flight
{
    public int FlightNo { get; set; }
    public string From { get; set; }
    public GeoLocation FromLocation { get; set; }
    public string To { get; set; }
    public GeoLocation ToLocation { get; set; }
    public DateTime Departure { get; set; }
    public DateTime Arrival { get; set; }
    public Plane Aircraft { get; set; }
    public double Distance { get; set; }
    public int SeatsLeft { get; set; }
    public int Duration { get; set; } //Minutes
    public int Price { get; set; } //USD
}
 
public class Plane
{
    public string Model { get; set; }
    public int Seats { get; set; }
    public int Speed { get; set; } //km/h
    public int Range { get; set; }
}

A few Google searches allowed me to build up a fleet of aircraft types for FlyFind and then it basically just boiled down to generating flights between random destinations at random times, with random number of seats sold, with a random aircraft – but where the distance was within the aircraft range. Arrival time can then be calculated with the speed of the aircraft and the random departure time. And based on the distance, seats left and some random discount I even managed to come up with a price. Then it’s basically just a question of bulk indexing them in Find using the .Index(…) method.

public override string Execute()
        {
            //Generate X flights and index them
            
            var cli = Client.CreateFromConfig();
            cli.Delete<Flight>(f => f.Arrival.LessThan(DateTime.Now));
 
            int cnt = cli.Search<Flight>().Take(0).GetResult().TotalMatching;
            bool hasFlights = (cnt > 0);
            var curday=DateTime.Now.Date;
            if (hasFlights)
            {
                var tres = cli.Search<Flight>().Take(1).OrderByDescending(f => f.Departure).GetResult();
                curday = tres.Hits.First().Document.Departure.Date;
            }
            //List of destinations
            var destlst =cli.Search<DestinationPage>().Take(100).GetPagesResult().Select(dp => new { Name = dp.PageName, Position = dp.Coordinates }).ToList();
            
            var r = new Random();
            
            int daycnt = 0;
 
            //Fetch appsettings, TotalFlights & FlightsPerDay
            var totalflights = int.Parse(System.Web.Configuration.WebConfigurationManager.AppSettings["TotalFlights"] ?? "50000");
            var flightsperday = int.Parse(System.Web.Configuration.WebConfigurationManager.AppSettings["FlightsPerDay"]?? "3000");
            List<Flight> flights = new List<Flight>(1000);
            while ((cnt < totalflights) && (!_stop))
            {
                var flt = new Flight();
 
                //Pick From & To
                var from=destlst[r.Next(destlst.Count)];
                flt.From = from.Name;
                flt.FromLocation = from.Position.SearchableLocation;
 
                var l = destlst.Where(a => a.Name != from.Name).Select(a => new { Name = a.Name, Position = a.Position, Distance = DistanceBetweenPlaces(flt.FromLocation.Longitude, flt.FromLocation.Latitude, a.Position.Longitude.Value, a.Position.Latitude.Value) }).ToList();
                //The closer, the more likely to get picked
                l = l.OrderBy(a => a.Distance).ToList();
                var to=l[r.Next(r.Next(l.Count))];
                flt.To = to.Name;
                flt.ToLocation = to.Position.SearchableLocation;
                flt.FlightNo = daycnt + 1;
                
 
                //Calculate distance
                var dist = DistanceBetweenPlaces(from.Position.Longitude.Value, from.Position.Latitude.Value, to.Position.Longitude.Value, to.Position.Latitude.Value);
                flt.Distance = dist;
 
                //Pick plane
                var pls = planes.Where(p => p.Range >= ((int)dist)).ToList();
                if (pls.Count == 0) continue;
                flt.Aircraft = pls[r.Next(pls.Count)];
                //return flt.From + " " + flt.To + " " + flt.Distance.ToString() + " " + flt.Aircraft.Model;
                
                //Pick timing & seats
                flt.SeatsLeft = r.Next(flt.Aircraft.Seats);
                flt.Duration = (((int)dist) / (flt.Aircraft.Speed / 60))+20; 
 
                //Timing: for now do it very simple
                flt.Departure = curday.AddMinutes(r.Next(24 * 60));
                flt.Arrival = flt.Departure.AddMinutes(flt.Duration);
 
                //Price: function of distance, seatsleft, Time to flight, random discount...
                flt.Price =
                    (int)(
                    (10 +         //base fee
                    (dist * 0.2))* //20 cents per km
                    (1.2-(flt.SeatsLeft/flt.Aircraft.Seats))*
                    ((r.Next(2)==1)?0.9:1.0) //Randomly decide whether a 10% discount is in order
                    );
 
                daycnt++;
                if (daycnt > flightsperday)
                {
                    curday = curday.AddDays(1).Date;
                    daycnt = 0;
                }
                cnt++;
                flights.Add(flt);
                if (flights.Count==1000)
                {
                    cli.Index(flights);
                    flights.Clear();
                    this.OnStatusChanged(string.Format("Indexed {0} flights. Date: {1}",cnt,curday.ToShortDateString()));
                }
                
            }
            if(!_stop) cli.Index(flights);
            return string.Format("Generated {0} flights", cnt);
        }

Note how this code also has some handling to ensure you can stop/restart it and it’ll keep adding on a certain number of flights per day until it reaches a designated maximum in the database. For the demo site we set it up to 1 million flights at 3500 flights / day. In the backend UI you can explore the index:

image

Now that we have a bunch of flights it seems like a good idea to make a way to navigate them. For starters I figured it would be nice to get the classical overview of all the flights in the air right now. On http://flyfind.demo.episerver.com/Travel-Information/Flights-Status/ I made an easy way to drill-down into the planes in the air right now. Nothing really fancy about it, but the fact that there’s always ~500+ flights in the air gives you an idea about how big the size of FlyFind’s international operation is Smile 

Again, if you looked at other Find query code, this will hold no surprises.

protected void Page_Load(object sender, EventArgs e)
{
    var q = SearchClient.Instance.Search<Flight>().Filter(f => f.Departure.Before(DateTime.Now) & f.Arrival.After(DateTime.Now));
    //Filter
    if (!string.IsNullOrEmpty(Request["Aircraft"]))
    {
        q = q.Filter(f => f.Aircraft.Model.Match(Request["Aircraft"]));
    }
    if (!string.IsNullOrEmpty(Request["Distance"]))
    {
        var r=Request["Distance"].Split('-');
        q = q.Filter(f => f.Distance.InRange((r[0] == "") ? 0 : double.Parse(r[0]), (r[1] == "") ? 100000 : double.Parse(r[1])));
    }
 
    if (!string.IsNullOrEmpty(Request["Landing"]))
    {
        q = q.Filter(f => f.Arrival.Before(DateTime.Now.AddMinutes(10)));
    }
    if (!string.IsNullOrEmpty(Request["Takeoff"]))
    {
        q=q.Filter(f => f.Departure.After(DateTime.Now.AddMinutes(-10)));
    }
    //Add facets
    q = q.TermsFacetFor(f => f.Aircraft.Model)
        .FilterFacet("About to land", f => f.Arrival.Before(DateTime.Now.AddMinutes(10)))
        .FilterFacet("Just took off",f => f.Departure.After(DateTime.Now.AddMinutes(-10)))
        .RangeFacetFor(f => f.Distance, new NumericRange { To = 500 }, new NumericRange { From = 501, To = 1000 }, new NumericRange { From = 1001, To = 3000 }, new NumericRange { From = 3001, To = 6000 }, new NumericRange { From = 6001 });
    Results = q.OrderBy(f => f.Arrival).Take(500).GetResult();
}

So far, so good. Now we’re almost there. All that’s left to do is to build a booking engine – piece of cake Smile

Now, for this demo I don’t really care about the e-commerce aspect of completing a booking, but I figured that allowing visitors to find flight connections that takes them where they want to go would be a fun challenge – and at the same time it would be a nice demo of the great performance Find can produce when searching in large datasets (such as flights). Personally I’ve always been fascinated by AI and AI-like technologies so this seemed like the perfect time to dip into the magic hat and pull out the good old A* algorithm for shortest path finding – and modify it slightly to use Find for querying and return multiple paths to choose from. But before we dive into the details, try it out: http://flyfind.demo.episerver.com/Find-Flights/.

Once again, note how this page uses Find for everything – even the contents of the drop-down lists are based on Find queries, the “From” ordering destinations based on your current location and the “To” presenting an alphabetical list of destinations.

image

 

Once you find some flight connections you’ll in the top see exactly how many Find Queries happened behind the scenes in order to find those flights – and how long time the server used on each query (in average). Now, you can read all about the A* algorithm in detail here, but essentially you work with an “open” and “closed” list, start with your origin in the open list and then do a breath-first search, adding destinations to the “closed” list as you reach them and stop when you’ve reached the desired destination – after which you backtrack to get the path. All paths prioritized by a heuristics algorithm that in this case just considers the geographical distance between current destination and the end goal (and the distance already traveled).

In other words – in the example above it starts by having Copenhagen on the open list, doing a query on all flights from Copenhagen from the start time (and 8 hours ahead – I don’t want to wait longer for a connecting flight). Of course it ensures all flights have seats available and that there is at least 30 min connection time between connections. Then, all possible destinations from those flights are added to the open list (while Copenhagen goes to the Closed list) and they are prioritized based on the heuristics mentioned above. This continues until a certain threshold (not implemented) – or the end-goal is reached – after which we’ll track back and see which flights that path is comprised of.

The code might not be the prettiest I’ve ever written – but it gets the job done.

public class AStar
{
 
    public int Searches { get; set; }
    public int SumTime { get; set; }
    public int AvgTime
    {
        get
        {
            if (Searches == 0) return 0;
            return SumTime / Searches;
        }
    }
 
    public AStar()
    {
        Searches = 0;
        SumTime = 0;
    }
 
    private IEnumerable<APath> DoSearch(APath cur, GeoLocation Goal)
    {
        var res = SearchClient.Instance.Search<Flight>()
            .Filter(f => f.From.Match(cur.LocationName))
            .Filter(f => f.SeatsLeft.GreaterThan(0))
            .Filter(f => f.Departure.InRange(cur.ReadyTime, cur.ReadyTime.AddHours(8)))
            .Take(1000)
            .GetResult();
        Searches++;
        SumTime += res.ProcessingInfo.ServerDuration;
        
        //Flights from the right place, at the right time (interval), with seats available...Order by geo-distance(? can be done?)
        return res.Hits.Select(sh => new APath() { ArrivingFlight = sh.Document, Parent = cur, G = cur.G+sh.Document.Duration, LocationName = sh.Document.To, ReadyTime = sh.Document.Arrival.AddMinutes(30), H = ((int)DistanceBetweenPlaces(sh.Document.ToLocation, Goal)) + 5000 });
    }
 
    public List<List<Flight>> FindFlights(DestinationPage src, DestinationPage dest, DateTime departure)
    {
        //Min change time: 30 min
        //Max change time: 8h
        //Order by Price, Earliest arrival
        GeoLocation Goal = dest.Coordinates.SearchableLocation;
        string GoalName = dest.PageName;
 
 
        List<APath> Open = new List<APath>(100);
        List<APath> Closed = new List<APath>(100);
        Open.Add(new APath() { LocationName = src.PageName, G = 0, H = (int)DistanceBetweenPlaces(src.Coordinates.SearchableLocation, Goal), Parent = null, ArrivingFlight = null, ReadyTime = departure });
        List<List<Flight>> FoundPaths = new List<List<Flight>>();
        while ((Open.Count > 0) && (FoundPaths.Count < 10))
        {
            //a) Look for the lowest F cost square on the open list. We refer to this as the current square.
            var current = Open.OrderBy(ap => ap.F).First();
            //b) Switch it to the closed list.
 
            if (current.LocationName == GoalName)
            {
                List<Flight> ll = new List<Flight>();
                var c = current;
                while ((c.Parent != null))
                {
                    ll.Add(c.ArrivingFlight);
                    c = c.Parent;
                }
                ll.Reverse();
                FoundPaths.Add(ll);
                Open.Remove(current);
                continue;
            }
            Open.Remove(current);
            Closed.Add(current);
            //Console.WriteLine("Open: {0}, Closed: {1}", Open.Count, Closed.Count);
            var lst = DoSearch(current, Goal);
            foreach (var i in lst)
            {
                //On closed list?
                if (Closed.Where(ap => ap.LocationName == i.LocationName).Count() > 0) continue;
 
                if (Open.Where(ap => ap.LocationName == i.LocationName).Count() > 0)
                {
                    var existing = Open.Where(ap => ap.LocationName == i.LocationName).First();
                    if (existing.G > i.G)
                    {
                        //Consider storing multiple parents (Ways of getting to this node)
                        Open.Remove(existing);
                        Open.Add(i);
                    }
                }
                else
                {
                    Open.Add(i);
                }
            }
        }
 
        return FoundPaths;
 
 
    }
 
 
    public static double Radians(double x)
    {
        return x * Math.PI / 180;
    }
 
    public static double DistanceBetweenPlaces(GeoLocation a, GeoLocation b)
    {
        return DistanceBetweenPlaces(a.Longitude, a.Latitude, b.Longitude, b.Latitude);
    }
    public static double DistanceBetweenPlaces(double lon1, double lat1, double lon2, double lat2)
    {
        double R = 6371; // km
 
        double sLat1 = Math.Sin(Radians(lat1));
        double sLat2 = Math.Sin(Radians(lat2));
        double cLat1 = Math.Cos(Radians(lat1));
        double cLat2 = Math.Cos(Radians(lat2));
        double cLon = Math.Cos(Radians(lon1) - Radians(lon2));
 
        double cosD = sLat1 * sLat2 + cLat1 * cLat2 * cLon;
 
        double d = Math.Acos(cosD);
 
        double dist = R * d;
 
        return dist;
    }
 
}
 
public class APath : IComparable<APath>
{
    public string LocationName { get; set; }
 
    public APath Parent { get; set; }
 
    public Flight ArrivingFlight { get; set; }
 
    public int G { get; set; }
 
    public int H { get; set; }
 
    public int F { get { return G + H; } }
 
    public DateTime ReadyTime { get; set; }
 
 
 
    public int CompareTo(APath other)
    {
        return LocationName.CompareTo(other.LocationName);
    }
}

Clever observers might point out that there are a lot of performance improvements to be done – like running queries in parallel – or doing bulk queries. However this works and is somewhat understandable so this is what I have now.

 

I hope you found this post enjoyable and perhaps even slightly educational. Feel free to drop comments or questions below.

 

Want to try out building your own search using Find? It’s easy, just go to find.episerver.com and create an account and a developer index to get started!

Oct 24, 2012

( 10/24/2012 12:09:57 PM)

Much needed. Thanks, Allan.

coma
( By coma, 10/31/2012 9:18:00 AM)

Nice work Allan!

Trond Klakken
( By Trond Klakken, 5/22/2013 10:10:35 AM)

Will the code ever be released like the Alloy project?

Raju Dasa
( By Raju Dasa, 3/10/2015 6:55:59 AM)

Nice if project can be downloadable.
Above demo link is not working, it throws error: "An invalid IP address was specified."

Please login to comment.