Graph Implementation

В софтуерното инженерство графите са фундаментална структура от данни, която може да се използва за моделиране на много проблеми – намиране на най-кратък път между градове, най-евтин маршрут при ползване на транспорт, създаване на графици и интелигентни системи. За жалост в рамките на академията ни остана много малко време да се занимаваме с тях и затова реших през свободното си време да създам собствена имплементация на граф и претеглен граф. Заедно с най-често използваните алгоритми – Breadth First Search, Depth First Search, Minimal Spanning Tree, Topological Sort, Shortest Path(source – all, source – target) и съответните им аналози за претеглен граф.

Graph Repository: click, съдържание на проектите:

  • GraphImplementation – съдържа непретеглен граф, с възможност за добавяне на насочени и ненасочени ребра, BFS, DFS, MST и Topological Sort
  • WeightedGraph – наследява горните функционалности, като добавя възможност за тежест на ребро и съответните алгоритми – Minimum Spanning Tree, Shortest Path (source – all), Shortest Path (source – target), използвайки алгоритъмът на Дийкстра.
  • GraphTests – тестове за горните графи.
  • GraphProfiling – конзолно приложение за ръчно тестване, профайлинг и други издевателства.

What are graphs?

6n-graf.svg

Това е абстрактна структура от данни, която е съставена от върхове и ребра. Върховете капсулират някакви данни и са свързани помежду си с ребра. За разлика от дърветата(BST примерно) върховете нямат ключ и връзката им едни с други е много по-абстрактна. Връзките(ребрата) между тях могат да са насочени/ненасочени или да имат тежест, което оказва огромно значение върху използваните алгоритми. Има много начини по които могат да се представят тези зависимости в структурата, като най-често се използва матрица на adjecencyMatrixсъседство, чрез която разбираме кои върхове са свързани. Тя представлява двумерен  n*n масив, където n е броят върхове, а стойностите индикират свързаност. В моята имплементация използвам матрица на съседство. Съществуват и други видове, като матрица на инцидентност(редовете са върхове, а колоните ребра), списък на наследниците, списък на ребрата, компоненти на свързаност и т.н. и д.р. и т.н. всеки един от тях има своите предимства и недостатъци.

Graph.cs

List<Vertex<T>> vertices – съдържа списък със всички върхове в графа. int maxVerts е максималният брой върхове, int[,] adjacencyMatrix – матрицата на съседство, verticesVisits – масив с посетените върхове, използва се за следващите алгоритми. Методите AttachEdge и AttachDirectedEdge, създават съответно ненасочено и насочено ребро.

Първият алгоритъм на нашето внимание е DFS – bool DepthFirstSearch(int startIndex, int endIndex). Стъпките при него са следните:

  1. Избираме начален връх и го правим текущ.
  2. Пушваме го в стека и го маркираме като посетен – verticesVisits[currentVert] = 1;
  3. Ако сегашният връх е търсеният излизаме, ако не е продължаваме
  4. Посещаваме съседен връх, който не е маркиран като посетен и го правим текущ.
  5. Повтаряме стъпките 2 до 4, докато не можем да продължим по-напред.
  6. Ако не сме намерили таргета попваме от стека текущият връх и посещаваме следващият връх маркиран като непосетен.
  7. Повтаряме 2 до 6, докато не намерим търсеният връх или обходим всички.
verticesVisits[startIndex] = 1;
Stack<int> searchStack = new Stack<int>();
int currentVert = 0;
searchStack.Push(startIndex);

while (searchStack.Count != 0)
{
    currentVert = GetNextUnvisitedVertex(searchStack.Peek());

    if (currentVert == -1)
    {
        searchStack.Pop();
    }
    else
    {
        verticesVisits[currentVert] = 1;
        searchStack.Push(currentVert);
    }

    if (currentVert == endIndex)
    {
        ClearVerticesVisits();
        return true;
    }
}

ClearVerticesVisits();
return false;

Следващото търсене е BFS – bool BreadthFirstSearch(int startIndex, int endIndex)

  1. Слагаме началният връх в опашка, и започваме цикъл, който спира, когато опашката е празна.
  2. В цикъла поп-ваме първият връх от опашката и го правим текущ.
  3. Проверяваме дали текущият е търсеният, ако е – излизаме.
  4. Слагаме всички съседни върхове в опашката и ги маркираме като посетени –                          while ((nextForSearch = GetNextUnvisitedVertex(currentVert)) != -1)
  5. Повтаряме 2 до 4, докато не намерим търсеният или опашката се изпразни.
verticesVisits[startIndex] = 1;
Queue<int> searchQueue = new Queue<int>();
int currentVert = 0;
int nextForSearch = 0;

searchQueue.Enqueue(startIndex);

while (searchQueue.Count != 0)
{
    currentVert = searchQueue.Dequeue();

    if (currentVert == endIndex)
    {
        ClearVerticesVisits();
        return true;
    }

    while ((nextForSearch = GetNextUnvisitedVertex(currentVert)) != -1)
    {
        verticesVisits[nextForSearch] = 1;
        searchQueue.Enqueue(nextForSearch);
    }
}

ClearVerticesVisits();
return false;

Третият е Minimum Spanning Tree – намира минималният брой свързани ребра, които са нужни, за да се посети всеки връх. Възможно е да има повече от едно такова, в непретеглен граф се търси минималният брой свързващи ребра, а при претеглен ще видим по-късно. Алгоритъмът е досущ като този на DFS, затова няма да го разглеждаме в статията.

learningTrack

Топологично сортиране е алгоритъм, който се използва при насочени графи. Върховете са подредени по определен ред от насочените ребра. Пример за това може да бъдат траковете за професия в Telerik Academy. На картинката ги виждаме в сортиран вид. Не можем да вземем ООП, преди C# I и C# II. Или пък да прескочим някой от курсовете и да продължим напред. Възможно е да се сортират и операции – първо чупим яйцата, после ги слагаме в тигана. Може и обратното, но няма да се получи вкусен омлет, та топологичното сортиране е отличен инструмент при следване на готварски рецепти. Важно условие е да нямаме цикъл и затова се допускат само насочени графи.

  1. Копираме всички върхове.
  2. Вземаме и матрицата за съседство.
  3. В главният цикъл взимаме върхът, който няма наследници – int v = GetVertNoSuccessor(tempAdjMatrix, tempSize);
  4. Ако не намерим такъв най-вероятно има цикъл и излизаме, при наличие изтриваме върха от копираната матрица.
  5. Добавяме изтритият връх в лист.
  6. Повтаряме 3 до 5, докато не изчерпим всички върхове.
  7. В листа са останали елементите в топологично сортиран вид.
bool hasCycles = false;
List<Vertex<T>> tempVerts = new List<Vertex<T>>(vertices);
int tempSize = tempVerts.Count;

int[,] tempAdjMatrix = new int[maxVerts, maxVerts];

for (int i = 0; i < maxVerts; i++)
{
    for (int j = 0; j < maxVerts; j++)
    {
        tempAdjMatrix[i, j] = adjacencyMatrix[i, j];
    }
 }

while (tempSize > 0)
{
    int v = GetVertNoSuccessor(tempAdjMatrix, tempSize);
    if (v == -1)
    {
        hasCycles = true;
        break;
    }

    output.Add(tempVerts[v].Node);

    if(v != tempSize -1)
    {
        tempVerts.RemoveAt(v);

        for (int row = v; row < tempSize - 1; row++)
        {
            for (int col = 0; col < tempSize; col++)
            {
                tempAdjMatrix[row, col] = tempAdjMatrix[row + 1, col];
            }
        }

        for (int col = v; col < tempSize - 1; col++)
        {
            for (int row = 0; row < tempSize; row++)
            {
                tempAdjMatrix[row, col] = tempAdjMatrix[row, col + 1];
            }
        }
     }

tempSize--;
}

return !hasCycles;

WeightedGraph.cs

При претеглен граф ребрата имат тежест(или цена). В матрицата за съседство вече можем да записваме цифри по-големи от 1, което показва каква е тежестта на даденото ребро.

Minimum Spanning Tree за претеглен граф е малко по-различно. Тук не само трябва да намерим минималният брой общи ребра за всички върхове, но и ребрата трябва да са така подбрани, за да са с най-малка стойност. Този алгоритъм може да ни покаже, кои авиолинии трябва да използваме, за да стигнем най-евтино до някоя важна точка на земята, като Луковит или Париж. За целта обаче ни е нужен и още един клас EdgeInfo. Той представя ребро и съдържа индексите на върховете от двата му края, както и тегло. Има си всички оператори за сравнение, понеже е важно да знаем, кое ребро е по-леко.

  1.  Маркираме първият връх като текущ и посетен.
  2. Въртим цикъл, който спира като посетим всички върхове.
  3. Обхождаме всички съседни върхове и добавяме ребрата им в лист.
  4. Ако листа с ребра е празен, графът не е свързан или има цикъл.
  5. Сортираме листа и махаме най-лекото ребро, като го слагаме при крайният резултат на MST.
  6. Повтаряме 3 и 5.

Алгоритъмът може да се подобри, като се използва приоритетна опашка, за да се спести сортирането, но тогава пък няма FindIndex и затова реших да не майсторя алтернатива засега.

int currentVert = 0, totalChecked = 0;
int size = vertices.Count;

List<EdgeInfo> edges = new List<EdgeInfo>();

while (totalChecked < size - 1)
{
    verticesVisits[currentVert] = 1;
    totalChecked++;

    for (int i = 0; i < size; i++)
    {
        if (i == currentVert || verticesVisits[i] == 1 ||
        adjacencyMatrix[currentVert, i] == 0)
       {
           continue;
       }

       EdgeInfo edge = new EdgeInfo(currentVert, i, adjacencyMatrix[currentVert, i       ]);

       int foundIndex = edges.FindIndex((x) => x.Weight == edge.Weight);
       EdgeInfo foundEdge = new EdgeInfo(0,0,0);
       if(foundIndex >= 0)
       {
           foundEdge = edges[foundIndex];
       }

       if (edges.Count == 0 || foundIndex < 0)
       {
           edges.Add(edge);
       }
       else
       {
           if (edge.Weight <= foundEdge.Weight)
           {
               foundEdge.Vertex1 = edge.Vertex1;
               foundEdge.Vertex2 = edge.Vertex2;
               foundEdge.Weight = edge.Weight;
           }
       }
   }

   if (edges.Count == 0)
   {
       return "Graph not connected";
   }

   edges.Sort((x, y) => x.CompareTo(y));

   int lastIndex = edges.Count - 1;
   int ver1 = edges[lastIndex].Vertex1;
   currentVert = edges[lastIndex].Vertex2;

   searchResult.AppendFormat("{0}:{1} ", vertices[ver1].Node, vertices[currentVert].Node);

   edges.RemoveAt(lastIndex);
 }

ClearVerticesVisits();

string result = searchResult.ToString();
 searchResult.Clear();

return result;

Shortest Path

Дойде и според мен най-интересната част – алгоритъм на Дийкстра за най-лек път в претеглен граф. В имплементацията съм добавил търсене от един към всички и от един към друг. Ще разгледаме само първият, понеже се различават само с един if, който прекъсва алгоритъма, когато сме намерили целта си. В wikipedia има доста добра статия и я препоръчвам, ако за първи път се сблъсквате с проблема за най-кратък(лек) път в граф, друг добър източник е Програмиране == ++Алгоритми;.

int n = vertices.Count;
int[] current = new int[n];
int[] previous = new int[n];
int[] passed = new int[n];

n е броят върхове в графа. Индексът на current сочи индекс на връх, а стойността е текущата тежест на изминалия път. В previous събираме индексите на изминатия досега път. passed се използва, за да маркираме връх като посетен.

  1. Инициализираме масивите current, previous и passed. Current тогава има теглата на всички свързани ребра, а всичко останало е intMax. В previous са маркирани с 0 съседните върхове и всичко друго е -1. Passed е с 1-ци, освен индекса на стартиращият връх.
  2. Намираме индексът и дистанцията(тежестта) на съседният връх с най-леко ребро.
  3. Маркираме го като посетено.
  4. Проверяваме дали няма по-лек път от миналата позиция, спрямо сегашната – ако има отиваме на нея – и продължаваме.
  5. Цикълът се прекъсва, когато обходим всички върхове (или достигнем целта -if (distance == targetValue)
    {
    break;
    }).
  6. Изкарването на резултата става чрез рекурсия по индексите на обходените върхове.
int n = vertices.Count;
int[] current = new int[n];
int[] previous = new int[n];
int[] passed = new int[n];

InitializeVariablesForSearch(sourceVertex, n, current, previous, passed);

while (true)
{
    int j = -1; //index of smallest distance
    int distance = int.MaxValue;

    FindSmallestDistance(n, current, passed, ref j, ref distance);

    if(j == -1)
    {
        break;
    }

    passed[j] = 0;

    for (int i = 0; i < n; i++)
    {
        if (passed[i] != 0 && adjacencyMatrix[j, i] != 0)
        {
            if (current[i] > current[j] + adjacencyMatrix[j, i])
            {
                current[i] = current[j] + adjacencyMatrix[j, i];
                previous[i] = j;
            }
       }
    }
 }

return GetResult(sourceVertex, current, previous);

Заключение

Графите са наистина необятна материя за изучаване и с времето, което разполагах успях да вникна в основите. С моята имплементация целя да покажа алгоритмите в действие и примерна реализация. За други цели ще се наложи методите малко да се преработят, за да изпълняват желаните функции, понеже в реални условия резултат string не би бил много полезен.

Posted in C#, Programming Tagged with: , , , , , , , , , , , ,

Leave a Reply

Your email address will not be published.