Six degrees of Kevin Bacon featuring Quickgraph

If you don't know what a Bacon Number is you can look it up here.

The basic idea is to calculate between how many movies there are between Kevin Bacon and another actor, the higher the number the further away. It is a very geeky calculation, in fact it so geeky that it is a part of google. Just google [actor name] bacon number and...

So how would you do this yourself?

First off we will need some data.

I used this to create a movie database. Basically you get an Actor table, a Dvd table and a Dvd_Actor table to link them.

Next we will just have to loop through all the records and create nodes(vertices) for each actor and movie in the database.

I used quickgraph and a sinple class to keep the nodes:

    public class MovieInformationNode
    {
        public int Id { get; set; }
        public NodeTypes NodeType { get; set; }
        public string Name { get; set; }
        public string PresentationName
        {
            get
            {

                if (NodeType == NodeTypes.Actor)
                    return "Actor: " + Name;
                else
                    return "Movie: " + Name;
            }
        }
    }

I declared the graph as:

private UndirectedGraph<MovieInformationNode, Edge<MovieInformationNode>> movieGraph                   = new UndirectedGraph<MovieInformationNode, Edge<MovieInformationNode>>();

For each Actor and Dvd I created a node and inserted it into the graph:

                MovieInformationNode node = new MovieInformationNode();
                node.NodeType = NodeTypes.Movie; //or actor if it is an actor, enum to keep track of type
                node.Id = dvd.Id;
                node.Name = dvd.DVD_Title.Trim();
                movieGraph.AddVertex(node);

For each link in Dvd_Actor I found the nodes in the graph and added an edge between them:

                //find actor

                MovieInformationNode actorNode = movieGraph.Vertices.Where(s => s.Id ==                                                               performance.Id && s.NodeType == NodeTypes.Actor).First();

                //find movie

                MovieInformationNode movieNode = movieGraph.Vertices.Where(s => s.Id ==                                                         performance.dvdid && s.NodeType == NodeTypes.Movie).First();

                Edge<MovieInformationNode> edge = new Edge<MovieInformationNode>(actorNode,                                                                               movieNode);

                movieGraph.AddEdge(edge);

Then you just need to get the shortest path:

            Func<Edge<MovieInformationNode>, double> edgeCost = (edge => 1.0D); //no weights

            var tryPath = movieGraph.ShortestPathsDijkstra(edgeCost, sourceNode);

            IEnumerable<Edge<MovieInformationNode>> path;

            if (tryPath(destinationNode, out path))

            {

                foreach (var item in path)

           {

                    listFrom.Items.Add(item.Source);

                    listFrom.Items.Add(item.Target);

           }

            }

To get this working you will need to get quickgraph here.

Converting from an adjacency list to hierarchyid in SQL Server

So many of us have worked with hierarchies in SQL Server, and for those not used to the HierarchyId the most common approach was to create a table with a parent relation to it self.

Consider a company structure where the main company has underlying companies, sections, divisions etc in a hierarcical manor. Something like this:

• Company
• SectionA
• Division1
• Division2
• SectionB
• Division1
• GroupA

The structure for representing this in a database using an adjacency list approach would be something like this:

CREATE TABLE [dbo].[Organization](

[Id] [int] IDENTITY(1,1) NOT NULL,

[Parent] [int] NULL,

[Name] [nvarchar](255) NOT NULL)

With this structure you can find the children of node 4 by a simple: 

SELECT * FROM Organization WHERE Parent = 4

The problem with this structure is when you need to search for all descendants to a node. Then you would need to first make a SELECT * FROM Organization WHERE Parent = 4 and then for each underlying node search for their children and then their children and so on. 

Recursion complicates things, but recursion coupled with database calls can make things go very slow as well.

So in SQL Server from 2008 (old technology, still so few uses it) there is a special datatype for handling hierarchies, the hierarchyid.

The new organizational structure would be something like:

CREATE TABLE [dbo].[NewOrganization](

[Id] [int] IDENTITY(1,1) NOT NULL,

[Hierarchy] [hierarchyid] NOT NULL,

[Name] [nvarchar](255) NOT NULL)

With this table you would be able to make queries such as:

DECLARE @ParentOrganization hierarchyid

SELECT @ParentOrganization = Hierarchy FROM NewOrganization

WHERE Id = 4

SELECT * FROM NewOrganization

WHERE Hierarchy .IsDescendantOf(@ParentOrganization ) = 1

Giving you the full subtree with only one call. Pretty neat.

So how do you get from the lousy adjacency list to the splendid hierachyid?

Well... given the two tables above (note that they are a bit pseudo-coded, no primary keys for example) a solution would be like this in c#.

To connect to the data base you would need a connection string to point out the correct type library:

    <add name="Organizations" connectionString="Type System Version=SQL Server 2012;Data Source=[database];Initial Catalog=[table];Integrated Security=True" /> see this for more info why and how.

Next up you need a mechanism for reading and writing the data to the database up to you if it's entity framework or something else. Note that you would need a reference to Microsoft.SqlServer.Types to use the hierarchyid from c#.

    public class NewOrganizationItem

    {

public Int32 Id { get; set; }

        public SqlHierarchyId Hierarchy { get; set; }

        public String Name { get; set; }

    }

    public class OrganizationItem

    {

        public Int32 Id { get; set; }

        public Nullable<Int32> Parent { get; set; }

        public String Name { get; set; }

    }

        private void ConvertTree()

        {

//Load all old organizationitems from the database

            List<OrganizationItem> items = OrganizationManager.SelectAll();

//Start the importing 

            InsertOrganizations(items, null, SqlHierarchyId.Null);

        }

We will need to keep track on three things when importing. The old organizations parentId and where it should be placed in the new hierarchy. For that we would need both the parent (new parent) and to keep track of the last child under it (lastSibling) so we can insert the new node after the last child node.

        private void InsertOrganizations(List<OrganizationItem> oldItems, int? parentId, 

                                                         SqlHierarchyId newParent)

        {

            SqlHierarchyId lastSibling = SqlHierarchyId.Null;

//loop through all children

            foreach (var item in oldItems.Where(s=>s.Parent == parentId))

            {

                NewOrganizationItem newItem = new NewOrganizationItem();

                newItem.Name = item.Name.Trim();

                if (parentId != null)

//if not a root item create it under its parent after the last sibling

                    newItem.Hierarchy = newParent.GetDescendant(lastSibling, SqlHierarchyId.Null);

                else

//create it under the root node

                    newItem.Hierarchy = SqlHierarchyId.GetRoot().GetDescendant(lastSibling, 

                                                                               SqlHierarchyId.Null);

//Insert it into the database and return the newly created item

                newItem = NewOrganizationManager.Insert(newItem);

                lastSibling = newItem.Hierarchy;

//recursively continue

                InsertOrganizations(oldItems, item.Id, newItem.Hierarchy);

            }

        }

Tricky stuff with Sql Server Spatial part 2

So you have this Sql Server 2012 with spatial datatypes and you want to read it with C#.

The first thing to do is to add a reference in your project to Microsoft.SqlServer.Types where SqlGeography and the likes reside.

The next step would be to make a query and read the results using a SqlDataReader. Something like this:

                result.Location  = (SqlGeography)reader["Location"];

The problem is that this will result in a System.InvalidCastException with the message:

{"[A]Microsoft.SqlServer.Types.SqlGeography cannot be cast to [B]Microsoft.SqlServer.Types.SqlGeography. Type A originates from 'Microsoft.SqlServer.Types, Version=10.0.0.0, Culture=neutral, PublicKeyToken=89845dcd8080cc91' in the context 'Default' at location 'C:\\windows\\assembly\\GAC_MSIL\\Microsoft.SqlServer.Types\\10.0.0.0__89845dcd8080cc91\\Microsoft.SqlServer.Types.dll'. Type B originates from 'Microsoft.SqlServer.Types, Version=11.0.0.0, Culture=neutral, PublicKeyToken=89845dcd8080cc91' in the context 'Default' at location 'C:\\windows\\assembly\\GAC_MSIL\\Microsoft.SqlServer.Types\\11.0.0.0__89845dcd8080cc91\\Microsoft.SqlServer.Types.dll'."}

If you read the message you actually can understand what's going on. Even though you put a specific reference to the types in Sql Server 2012, it still seems as if C# is trying to read with the old version of Sql Server (2008).

The easiest way to fix this is through the connection string and the Type System Version construct that appeared in .Net 4.5.

My first attempt on a connection string was like this (and yeah, my computer is named GAAH):


    <add name="Main" connectionString="data source=GAAH\SQLEXPRESS;initial catalog=SpatialSample;integrated security=True" />

By adding Type System Version we can tell it that we will use the 2012 version of Sql Server Types.

    <add name="Main" connectionString="Type System Version=SQL Server 2012;data source=GAAH\SQLEXPRESS;initial catalog=SpatialSample;integrated security=True" />

Now youre just a read away from your spatial objects.

Tricky stuff with Sql Server Spatial part 1

Dear reader(s),

Last week I held an internal lecture about SQL Server Spatial and the basics of GIS here at knowit.
I really like talking about GIS as it is about the world and big amounts of data and I do like the world and big  amounts of data.

Well... where I am? who am I?

Oh, yeah. While preparing I noticed a few things that can be a bit tricky with SQL Server Spatial.

This is the first one.

Preparations:

I use a table called test which basically holds one geography column named spatial and another varchar() called name.

Inserts:


INSERT INTO Test (Name, Spatial)
VALUES(
    'Polygon',
    geography::STGeomFromText(
         'POLYGON((-1 -1, 8 -1 , 8 8 ,-1 8, -1 -1))',4326));

So this basically inserts a polygon into the world. As you can see it is square and crosses the equator. The number 4326 is called the SRID and basically means that the coordinates are calculated according to the projection WGS84. (projections basically means that you get different sets of coordinates depending on how you try to put the round globe on to a square piece of paper (a map). Look here for more info.).

Well, besides the 4326 this is no sweat... now try doing it this way:


INSERT INTO Test (Name, Spatial)
VALUES(
    'Polygon',
    geography::STGeomFromText(
         'POLYGON((-1 -1, -1 8 , 8 8 ,8 -1, -1 -1))',4326))

Exactly the same call, but we put the coordinates the opposite way. Now it is no longer a square polygon crossing the equator but instead it is all but a square polygon crossing the equator. It is covering the rest of the world.

Depending on if you add point clockwise or counter clockwise gives you two totally different polygons.

Why?

Well the world IS actually round meaning that any set of points that makes up a polygon on the surface of the world has two meanings. An interior version and an exterior version. Counter clockwise gives the interior version, clockwise the exterior. Easy to forget...

More about it here.

A generic way to read data from an SqlDataReader

Through the years I have been struggling to find a really good way to read data from a datareader. If you know me, you also know that I prefer good old reliable methods that puts me in control to object relational mapping..

Consider the following code (didn't compile it so forgive me for eventual bugs):



    private static List<Book> ReadData(string connectionString)
    {
        List<Book> books = new List<Books>();
        string queryString =
            "SELECT Author, Title, Year FROM Books";

        using (SqlConnection connection =
                   new SqlConnection(connectionString))
        {
            SqlCommand command =
                new SqlCommand(queryString, connection);
            connection.Open();

            SqlDataReader reader = command.ExecuteReader();

            while (reader.Read())
            {
                Book book = new Book();
                book.Author = reader("Book");
                book.Title= reader("Title");
                book.Year= reader("Year");
                books.Add(book);
            }

            reader.Close();
            return books;
        }
    }
}

This code should work pretty well, the problem comes when you start using nullables. If year were int? instead of int this code this would throw an exception as soon as a null value appears in the reader.

Null in Sql Server and in c# are two different things.
From the database points of view a field has three values:

1. A value. For example 1993.
2. A null value. We left the year empty because we didn't know the year.
3. Empty, the book does not exist.

Now you might argue that if the row was empty a try would anyway give you an error and the pragmatical side of me totally agrees, but still, the issue stems from the fact that null in C# is the absence of a reference to an object, while null in a database is an uninitialized or empty value. It exists and we have to deal with it.

I like solving this with extension methods (actually I am generally pretty hooked on extension methods).

The standard approach is to use something like this:

public static int? ToNullableInt(this int value)

{

    return value.IsNull ? (int?) null : value.Value;

}

And then call the reader like:

book.Year= reader("Year").ToNullableInt();

It is a reasonable solution. But you would have to write those extension methods for every nullable data type.

A single function version that handles all data types plus basic conversion but also is slightly slower looks something like this:

           private static T Get<T>(this SqlDataReader reader, string index, T defaultValue = default(T))

          {

                    var t = reader[index];

                    if (t == DBNull.Value)

                                return defaultValue;

                   Type type = typeof(T);

                   if (type.IsGenericType && type.GetGenericTypeDefinition() == typeof(Nullable<>))

                   {

                               var subType = Nullable.GetUnderlyingType(type);

                               return (T)Convert.ChangeType(t, subType);

                   }

                   return (T)System.Convert.ChangeType(t, typeof(T));

           }

This would be called like this:

book.Year= reader.Get<int?>("Year");

When microseconds are not the issue, I prefer that solution, but I am always looking for something even better. Ideas? :)

Spatiality Part 4, Fiddling with SQL Server Spatial SQL

SQL Server is quite potent when it comes to spatial queries. It follows the Open Geospatial Consortium Simple Features for SQL, Version 1.1 and implements about 70 functions covering areas such as intersects, unions and the like. Basic GIS-stuff.

It is a bit different syntax from what most people are used to, but once you get past that it's a breeze.

SQL Server 2008 supports two kinds of spatial data.

Geometry, that means flat.
Geography, that means spherical.

I still believe that the world is spherical even though I read a lot of hard evidence suggesting otherwise here. 


So I would choose the geography style. However, all my data is flat so...


In my spatial database I have lots and lots of areas. And it would be nice to get all areas within say 20 km from my position. (I can't believe some third world countries still hang on to miles)


You can probably do this the hard way and use a lot of math to get an answer, or you can do it the GIS way.


GIS (Geographical Information Systems) is a neat science. One of its strengths is to get new information by making calculations on thematic layers on a map. For me it started with reading the book Map Algebra by Dana Tomlin and I was hooked. If you are interested read more here.


Spatial SQL is a bit different but you can achieve a lot by using similar techniques.

Back to the task.


My plan is as follows:

1. Create a geographical area covering a 20 km circle with it's center in the middle of stockholm.
2. Use that circle to overlay my data and by SQL return all the objects that intersects my buffer.
3. Show it in my blog.

Let's start with number one in the list.

DECLARE @stockholm geometry = geometry::STPointFromText('POINT (18.06861 59.32944)', 4326)

So... what do we do here? We (or actually I) create a point geometry by using the geometry::STPointFromText function. As parameter we have the coordinates as a string followed by the mystical 4326 which simply points out that we are using the reference system WGS84. The same reference system as my own data.

This will give us a one dimensional point.


To make it into a circle we use:

DECLARE @stockholmbuffer geometry = @stockholm.STBuffer(0.2)

We simply tell SQL Server to make a buffer around our point with the distance 0.2. 

The distance on my map is in degrees. Lats and longs. 

And a degree is around 110 km and 20% of that is just close enough 20 km to make me happy. 

I'm not picky.

So now we have declared a 20ish km radius circle with its center in Stockholm.

Next step is to overlay it with the existing data.

This is how we do it:

SELECT *

FROM areas

WHERE ogr_geometry.STIntersects(@stockholmbuffer) = 1

Just a simple call to the intersect function that returns 1 on an overlap.


So to summarize:


DECLARE @stockholm geometry = geometry::STPointFromText('POINT (18.06861 59.32944)', 4326)


DECLARE @stockholmbuffer geometry = @stockholm.STBuffer(0.2)

SELECT *

FROM areas

WHERE ogr_geometry.STIntersects(@stockholmbuffer) = 1

And the result is this:

Spatiality (a short interlude with a hint of bitterness)

Importing data to SQL Server needs its own entry in this blog. Especially when it comes to international characters. You know: 'Ö', 'Ü', 'Ñ', 语 and the likes. I am talking about UTF-8, UTF-16 and other ways to map a character to bits and bytes.

Character encoding.

The problems started in 1963 with ASCII (and probably earlier in the analog world with Morse codes, viking runes and smoke signals). ASCII and IBM's ECBDIC managed to fit a character into seven and eight bits respectively. Memory space was a very limited resource those days so all was good until someone realized that there actually exists other languages than English and they tried to hack it into ASCII using ISO 8859.

This time they forgot small regions such as the Arabic world, Japan, India and China...

1988 they finally started working on UNICODE and nowadays we only have one way to save international characters: UTF-8, UTF-16 and UTF-32...

Most stuff you find on Internet is UTF-8, SQL Server handles UTF-16 and when you import stuff into the database without spending an hour of googling ahead of the task everything ends up in the non UTF fields called varchar...

Some people probably love code pages and character encodings. I don't. For me it is one of those totally uninteresting side issues that distracts my creativity from really achieving something. It is fully in the line with issues such as coordinate transformations, spending time fixing web stuff to make it readable in any browser and trying to access web services not made for Microsoftians as myself.

I hate it.

Give me one type of coordinate, browser, service and one type of string!

I want to use my brain for content and functionality, not details.

So... this long rambling obviously cooks down to the fact that I goofed up and managed to import all that data in spatiality 3 to a varchar field instead of an nvarchar field. And as I have a blog I have the opportunity to channel my bitterness...

Getting the stuff all the way to Azure made it even less interesting to go through the whole process again and try to import the data 'the right way'.

So I googled.

Ye who google shall find.


I found this. A function that fixed my mistakes and saved a good day of work for me. I just added an nvarchar to the table, updated it with the function and dropped the old one. Worked like a charm.

I love google and I love people like Jason that cleans up after my mistakes. Thank you!

Spatiality Part 3

Finally, after a barrage of work, I have the possibility to do some own coding and make one more step toward finishing my next app.

So... were are we?

In part 2 I finally managed to export a shape file to Sql Server 2008, this time I plan to export that spatial data to my Azure SQL.

So what to do when you start with something you never done before?

Google!

My first finding was this link. Since I enjoy simplicity the Import and Export Wizard sounded perfect. I've used it countless times before and it has never failed me.

I follow the steps, opens up an ip address to azure and everything works brilliant until I get to the Review Data Type Mapping phase, when the wizard gives me something like this:

Reason? The Import and Export Wizard can't export spatial datatypes...

So time to google again!

This time I found the SQL Azure Migration Wizard.

This tool has a bit of crappy GUI (I use the 125% size on text and it doesn't handle it). But i transfers data using Bcp so I had least hope of getting it to work.

My first attempt crashed, another googling and I realized that I needed to upgrade my SQL Server to service pack 1.

I tried again and this time:

I ran  a query agains the table in SQL Server Management Studio and lo and behold, all is there!

Next up: exposing the data through an azure web service.

PS. If you like sharepoint follow this!

Another don't in SQL Server...

Found out the hard way that it's not a good idea to rename your default data base in SQL Server 2005 (yeah, some of us still work with ancient technology).

If you do, you will be stuck for some time googling and guessing sqlcmd commands. More info here.