Библиотека за работа с графи

Въведение

Ще ви представя една библиотека за работа с графи. Библиотеката е лично творение и е изработена на C# 2.0. Ако се занимавате с Теория на графите, с нейна помощ много по-лесно ще можете да управлявате един граф. За сега библиотеката не е много голяма и има вероятност да срещнете различни проблеми при работата с нея. Все пак, една основна функционалност е постигната. Ако сте я пробвали и сте срещнали някакъв проблем, можете да се свържете с мен и да го отстраня.

Работа с библиотеката

Преди да започнете работа с библиотеката, трябва да в вградите във вашия проект. По-горе съм описал как става това. След това трябва да включите пространството от имена във вашия клас:

1. using OmegaGraph;

Ето и примерен код за работа с графи. Не мисля, че трябва да се обяснява много, тъй като всичко е направено максимално лесно за разбиране и работа. В този пример ще ви покажа как можете да си построите покриващо дърво (в ширина и дълбочина) от даден граф.

1. OGraph myGraph = new OGraph();
2. // добавяме върхове в графа
3. myGraph.Vertices.Add(new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
5. // добавяме и ребрата
6. myGraph.Edges.Add(new Edge(1, 2));
7. myGraph.Edges.Add(new Edge(1, 4));
8. myGraph.Edges.Add(new Edge(2, 4));
9. myGraph.Edges.Add(new Edge(2, 3));
10. myGraph.Edges.Add(new Edge(2, 5));
11. myGraph.Edges.Add(new Edge(2, 6));
12. myGraph.Edges.Add(new Edge(4, 5));
13. myGraph.Edges.Add(new Edge(4, 7));
14. myGraph.Edges.Add(new Edge(5, 6));
15. myGraph.Edges.Add(new Edge(6, 7));
16. myGraph.Edges.Add(new Edge(6, 8));
17. myGraph.Edges.Add(new Edge(7, 8));
19. // сега искаме да си построиме покриващо дърво в ширина и дълбочина
20. GraphAlgorithm algorithm = new GraphAlgorithm(myGraph);
22. OGraph spanningTreeInDepth = algorithm.CreateSpanningTree(GraphAlgorithm.TreeType.Deep);
24. foreach (Edge edge in spanningTreeInDepth.Edges)
25. {
26.  Console.WriteLine(edge);
27. }
29. OGraph spanningTreeInWidth = algorithm.CreateSpanningTree(GraphAlgorithm.TreeType.Wide);
31. foreach (Edge edge in spanningTreeInWidth.Edges)
32. {
33.  Console.WriteLine(edge);
34. }

Console.WriteLine(edge) ще изведе на екрана x->y : v, където x и y са върховете на реброто, а v е неговата стойност (ако е указана такава при добавянето на реброто). Ето как изглеждат и самите покриващи дървета:

В библиотеката са включени и алгоритмите на Прим и Крускал за построяване на оптимално покриващо дърво, както и алгоритъмът на Дейкстра за дърво на най-късите пътища в граф.

Нека си построиме следния граф, като този път ще укажем стойност (цена) на всяко ребро:

1. OGraph myGraph = new OGraph();
2. myGraph.Vertices.Add(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
4. myGraph.Edges.Add(new Edge(1, 2, 2));
5. myGraph.Edges.Add(new Edge(1, 4, 1));
6. myGraph.Edges.Add(new Edge(2, 3, 1));
7. myGraph.Edges.Add(new Edge(2, 4, 5));
8. myGraph.Edges.Add(new Edge(2, 5, 3));
9. myGraph.Edges.Add(new Edge(2, 6, 2));
10. myGraph.Edges.Add(new Edge(4, 5, 1));
11. myGraph.Edges.Add(new Edge(4, 7, 2));
12. myGraph.Edges.Add(new Edge(4, 8, 4));
13. myGraph.Edges.Add(new Edge(5, 6, 4));
14. myGraph.Edges.Add(new Edge(5, 8, 3));
15. myGraph.Edges.Add(new Edge(5, 9, 4));
16. myGraph.Edges.Add(new Edge(6, 9, 3));
17. myGraph.Edges.Add(new Edge(8, 9, 5));
19. GraphAlgorithm algorithm = new GraphAlgorithm(myGraph);
21. OGraph minSpanningTreeByPrim = algorithm.CreateOptimalSpanningTree(OGraph.OptimalType.Minimum, GraphAlgorithm.AlgorithmType.Prim);
23. Console.WriteLine("Algoritum na Prim");
25. foreach (Edge edge in minSpanningTreeByPrim.Edges) Console.WriteLine(edge);
27. Console.WriteLine();
28. Console.WriteLine("Algoritum na Kruskal");
30. OGraph minSpanningTreeByKruskal = algorithm.CreateOptimalSpanningTree(OGraph.OptimalType.Minimum, GraphAlgorithm.AlgorithmType.Kruskal);
32. foreach (Edge edge in minSpanningTreeByKruskal.Edges) Console.WriteLine(edge);
34. Console.WriteLine();
35. Console.WriteLine("Algoritum na Dejkstra");
37. OGraph minSpanningTreeByDejkstra = algorithm.CreateValueTree(OGraph.OptimalType.Minimum);
39. foreach (Edge edge in minSpanningTreeByDejkstra.Edges) Console.WriteLine(edge);

Заключение

Библиотеката е все още БЕТА версия и е много вероятно да срещнете проблеми. Въпреки това, една основа е покрита от нея. Ако открите някаква грешка, можете да се свържете с мен.

Файлове, към тази статия:

OmegaGraph.dll

Коментари

Към тази статия все още няма коментари. Бъдете първи и напишете вашия коментар.