Tag Archives: c-sharp

Как да извлечем картинките от базата данни Northwind с помощта на C#, ADO.NET и SQL Server 2008 R2?

Какво представлява Northwind?

nortwind traders database logoБазата данни Northwind съдържа данните за продажбите на имагинерна фирма, която внася и изнася храни по целия свят. Тя е била създадена от Microsoft като проста база, която да се използва с техните продукти – Access и SQL Server. Известна е с това, че е построена много добре и е перфектна за учебни цели. Във w3schools например, сайт с онлайн туториали, базата на Northwind Traders се използва в SQL примерите. Можете да изтеглите скрипта на Northwind за SQL Server 2008 R2 от тук.

Какво е OLE?

През 1990 екипът в Microsoft, който разработва Access се нуждаел от начин не само да съхранява данни, но и да я предоставя на потребител, който е качил и друг софтуер на компютъра си. Тогава е нямало надежден начин да откриеш чрез операционната система кой софтуер с какви типове файлове работи. На тях им дошла идея, която била наречена Object Linking and Embedding(OLE).

Как се съхраняват файлове с OLE структура?

OLE структурата представлява следното:

  1. Пакетен header
  2. Ole header
  3. Datablock header
  4. Данни
  5. Metafilepict блок
  6. Ole footer

Когато се работи с картинки, има блок, който се нарича metafilepict. Едва ли ще откриете картинка, ако го прочетете. Стартовата позиция на картинката се изчислява след като се изпусне този блок.
Metafilepict стартова позиция = дължината на package header-а + дължината на ole header-а + 8 празни байта + 4 байта, указващи дължината на данните + дължината на байтовете + 45 (дължината на metafilepict header-а). При картинките в Northwind това число е точно 78.

Четене на images от таблица Categories в Northwind

След като вече знаем, че трябва да прескочим 78 байта, за да прочетем картинката, просто трябва да го напишем. Използвам код на C# и доста остарялата технология ADO.NET, но тя ще свърши перфектна работа за простия пример.
Кодът на C#:

int OLE_METAFILEPICT_START_POSITION = 78;

SqlConnection con = new SqlConnection(
    "Server=.\\SQLEXPRESS; " +
    "Database=Northwind; " +
    "Integrated Security=true");
con.Open();
using (con)
{
    SqlCommand command = new SqlCommand(
        "SELECT CategoryName, Picture " +
        "FROM Categories", con);
    SqlDataReader reader = command.ExecuteReader();
                
    using (reader)
    {
        while (reader.Read())
        {
            string categoryName = ((string)reader["CategoryName"]);
            if (categoryName.Contains('/') == true)
            {
                categoryName = categoryName.Replace('/', ' ');
            }
            byte[] pictureBytes = reader["Picture"] as byte[];
                        
            MemoryStream stream = new MemoryStream(
                pictureBytes, OLE_METAFILEPICT_START_POSITION,
                pictureBytes.Length - OLE_METAFILEPICT_START_POSITION);	
						
            Image image = Image.FromStream(stream);
            using (image)
            {
                image.Save(categoryName + ".jpg", ImageFormat.Jpeg);
            }
        }                    
    }                
}

Картинките:
northwind images from categories table

Алгоритъмът на Дейкстра, реализиран с приоритетна опашка и написан на C#

Кой е Дейкстра?

Едсхер Дейкстра е холандски учен със значителни постижения в компютърните науки:
dijkstra

  • Независимо, заедно с колегата си Фридрих Бауер, са преоткрили алгоритъма обратен полски запис. Целяли са да намалят ползваната компютърна памет като използват стека за правене на изчисления.
  • Създател на алгоритма Shunting yard, който се използва за преобразуване на нормален израз в обратен полски запис.
  • Създател на алгоритъмът на Дейкстра, който открива най-кратък път в граф с положителни ребра.
  • Създал концепцията за семафора, която цели координация на множество програми и процесори.
  • Създател на алгоритъма на Банкер.
  • Един от създателите на първия компилатор на ALGOL 60. Двамата с неговия колега Яп Зонфилд си обещали да не се бръснат, докато не приключат компилатора. Създаденият компилатор бил един от първите, поддържащи рекурсия.
  • Голям противник на GOTO, той пишел статии срещу тази конструкция и спомогнал много за всеобщото й неодобрение. Заедно с това той прокарал идеята си за структурно програмиране, което вместо GOTO използва WHILE и FOR в кратки програмни блокове и избягва спагети кода.
  • Създал концепцията самостоятелна стабилизация, чиято цел била да накара една система да завърши правилно работата си при каквито и да е входни данни. Благодарение на откриването на тази концепция, Дейкстра е награден след близо 30 години с една от най-престижните награди в компютърното общество 2002 ACM PODC Influential-Paper Award, която по-късно е преименувана на “награда на Дейкстра”.
  • Награден с А.М. Тюринг

Алгоритми за най-кратък път в граф

Има различни алгоритми за намиране на най-кратък път граф – това е сумата на теглата на ребрата, през които минаваме от стартовия връх до целта. Три от най-известните алгоритми за намираме на най-кратките разстояния от конкретен връх до всички останали са алгоритмите на Форд-Белман, Флойд и Дейкстра.

И трита алгоритъма се основават на неравенството на триъгълника. Т.е. сумата на дължините на кои да е две страни е по-голяма от дължината на третата му страна. Всеки от тези алгоритми се основава на последователна проверка на (някои от) неравенствата на триъгълника и, в случай на нарушение, установяване в равенство.

Алгоритъмът на Форд-Белман има сложност Θ(n3). При него получаваме пътищата от стартовия връх до всички останали. Алгоритъмът работи с произволни тегла на ребрата – отрицателни и положителни. Полезно свойство на алгоритъма на Форд-Белман е, че позволява да се открие отрицателен цикъл, ако съществува такъв.

Алгоритъмът на Флойд е подобен на този на Форд-Белман. Той отново има сложност Θ(n3). След приключване на работата му обаче, при него получаваме разстоянията между всяка двойка върхове в графа. Отново, както при алгоритъма на Флойд, отрицателните ребра не са проблем, стига да няма отрицателни цикли.

Алгоритъмът на Дейкстра за най-кратък път в граф

Най-ефективният метод за намиране на най-кратките пътища от един връх до всички останали е алгоритъмът на Дейкстра. За да работи алгоритъмът, теглата трябва да са положителни. Повече информация за това как точно работи алгоритъма, както и анимации – тук. Сложността на алгоритъма е Θ(n2), но при използване на приоритетна опашка, тя може да спадне до Θ(n.log2n).

Алгоритъм на Дейкстра с приоритетна опашка, написан на C#

Понеже в библиотеката на C# няма реализация на приоритетна опашка, ще използваме класа OrderedBag<T> от колекцията Power Collections на Wintellect, която представлява сортирано мултимножество.

Първото нещо, което трябва да направим е един клас, който ще представя връх в граф. В него ще имаме – име на върха, цена, дали е бил посетен, кой е предишния връх, през който сме стигнали, за да стигнем до него и списък с децата му и цената(теглото на реброто) до всяко дете. Сорс-код:

class Vertex : IComparable<Vertex>
{
    public string Name { get; set; }
    public Vertex Previous { get; set; }
    public uint Cost { get; set; }
    public bool Visited { get; set; }
    public Dictionary<Vertex, uint> Children { get; set; }

    public Vertex(string name)
    {
        this.Name = name;
        this.Previous = null;
        this.Cost = int.MaxValue;
        this.Visited = false;
        this.Children = new Dictionary<Vertex, uint>();
    }
 
    public override bool Equals(Object obj)
    {
        if (this == obj)
        {
            return true;
        }

        Vertex other = obj as Vertex;
 
        if (other == null)
        {
            return false;
        }
 
        if (!this.Name.Equals(other.Name))
        {
            return false;
        }
        return true;
    }
 
    public override int GetHashCode()
    {
        return this.Name.GetHashCode();
    }

    public int CompareTo(Vertex other)
    {
        return this.Cost.CompareTo(other.Cost);
    }
}

Конструктора задава по подразбиране за предишен връх – null. Това ще ние полезно по-нататък при изпечатването на пътя. Задава се цена на пътя максималното int число. Ако реалната цена на пътя надвиши това число, алгоритъма няма да работи коректно. При необходимост, може да се промени на друго число или да се реализира по друг начин с цел избягване на препълване. Отбелязваме, че не е бил посетен. Децата пазим в речник, който хешира по име и пази в една променлива теглото на реброто към съответното дете. Теглата могат да са само положителни, тъй като алгоритъмът на Дейкстра работи само с такива.

Следва сорс-код на алгоритъма на Дейкстра:

static void ExecuteDijkstra(Vertex start)
{
    OrderedBag<Vertex> pQueue = new OrderedBag<Vertex>();
    start.Cost = 0;
    pQueue.Add(start);

    while (pQueue.Count > 0)
    {
        Vertex current = pQueue.RemoveFirst();
        current.Visited = true;
        foreach (Vertex child in current.Children.Keys)
        {
            if (child.Visited == false)
            {
                if (child.Cost > current.Cost + current.Children[child])
                {
                    child.Previous = current;
                    child.Cost = current.Cost + current.Children[child];
                    pQueue.Add(child);
                }
            }
        }
    }
}

За да намерим разстоянието от стартовия до текущия връх, се опитваме да оптимизираме с децата на текущия. За всяко дете, което е по-близко, го добавяме в приоритетната опашка. Докато не свършат върховете повтаряме процедурата като всеки път се обработва елементът, който е най-близо до стартовия връх.

Нека тестваме алгоритъма. Ще въведем неориентиран граф, но алгоритъмът работи също толкова успешно и с ориентиран:
dijkstra-algorithm-example-graph
Ще пуснем алгоритъма на Дейкстра от върха “A”. След това ще изпечатаме резултатите. Имаме разнообразни сценарии – има по няколко пътя до някои върхове, а до други – нямаме въобще. Можем да хард-коуд-нем графа по следния начин:

static void Main(string[] args)
{
    List<Vertex> graph = new List<Vertex>();
    graph.Add(new Vertex("A")); //0            
    graph.Add(new Vertex("B")); //1
    graph.Add(new Vertex("C")); //2
    graph.Add(new Vertex("D")); //3
    graph.Add(new Vertex("E")); //4
    graph.Add(new Vertex("F")); //5
    graph.Add(new Vertex("G")); //6
    graph.Add(new Vertex("H")); //7
    graph.Add(new Vertex("I")); //8
    graph.Add(new Vertex("J")); //9

    graph[0].Children.Add(graph[1], 23);
    graph[0].Children.Add(graph[7], 8);

    graph[1].Children.Add(graph[0], 23);
    graph[1].Children.Add(graph[3], 3);
    graph[1].Children.Add(graph[6], 34);

    graph[2].Children.Add(graph[7], 25);
    graph[2].Children.Add(graph[3], 6);
    graph[2].Children.Add(graph[9], 7);

    graph[3].Children.Add(graph[1], 3);
    graph[3].Children.Add(graph[2], 6);

    graph[4].Children.Add(graph[5], 10);

    graph[5].Children.Add(graph[4], 10);

    graph[6].Children.Add(graph[1], 34);

    graph[7].Children.Add(graph[0], 8);
    graph[7].Children.Add(graph[9], 30);
    graph[7].Children.Add(graph[2], 25);

    graph[9].Children.Add(graph[7], 30);
    graph[9].Children.Add(graph[2], 7);

    Vertex start = graph[0]; //"A"

    ExecuteDijkstra(start);
    PrintPaths(graph, start);
}

Функциите за отпечатване:

static void PrintPaths(List<Vertex> graph, Vertex start)
{
    foreach (Vertex vertex in graph)
    {
        if (vertex.Name != start.Name)
        {
            if (vertex.Cost == int.MaxValue)
            {
                Console.WriteLine("No path between " 
                    + start.Name + " and " + vertex.Name + ".");
            }
            else
            {
                Console.Write("The path between "
                    + start.Name + " and " + vertex.Name + " is: ");
                PrintPath(vertex);
                Console.WriteLine("and has a length of " + 
                    vertex.Cost + ".");
            }
        }
    }
}

static void PrintPath(Vertex v)
{
    if (v.Previous != null)
    {
        PrintPath(v.Previous);
    }
    Console.Write(v.Name + " ");
}

Как разпечатваме? Преминаваме през всеки връх на графа, с изключение на стартовия, и ако цената му е максималният int, значи не сме стигнали до него и той е в друга компонента на свързаност. Ако цената не е максималният int, значи сме стигнали до него по някакъв начин . Как да открием пътя? Помните ли, че записвахме в една променлива от кой връх сме дошли, за да стигнем до текущия. Остава да пуснем една изключителна проста рекурсия и да отпечатаме върха. Цялостната цена пазим в променливата Cost. Печатаме и нея. Резултата от изпълнението на всичкия код:
priority queue dijkstra algorithm graph example result