В ходе написания одного из курсовиков, мной был создан визуальный редактор графов, исходниками которого я и хочу поделиться.
До начала работы я провел допрос гугла, с целью найти нечто подобное в уже готовом виде. Но, к сожалению, ничего приемлемого на .Net не нашел. И это притом, что на C++ или Java таких вещей множество. Своим приложением я, надеюсь, смогу устранить данный пробел.
Итак, моя библиотека состоит из двух частей: GraphModel и VisualGraphModel.
GraphModel представляет собой простейшую реализацию графа. Позволяет добавлять и удалять вершины и дуги, а также выполнять такие операции, как поиск вершины по имени, нахождение минимального пути между 2 вершинами и т.д. Полностью все доступные операции вы сможете найти в интерфейсе IGraph. Думаю, там все будет понятно.
VisualGraphModel - библиотека, включающая 2 компонента для Windows Forms: VisualGraphComponent и EditGraph. Я рекомендую пользоваться вторым, т.к. это уже готовое решение. VisualGraphComponent - заготовка, представляющее поле для отрисовки фигур.
Сама библиотека реализует все возможности предыдущей + добавляет ряд функций для рисования фигур и взаимодействием с пользователем.
Вот общая схема классов:
Реакция на действия пользователя реализована через механизм посредника и состояний. (Состояния устанавливаются как посредником, так и другими состояниями).
Сама отрисовка происходит через GDI+.
Для использования компонента в своем приложении следует сделать так:
Подключите библиотеки GraphModel.dll и VisualGraphModel.dll
Подключите след. пространства имен:
using org.zavyalov.VisualGraphModel.Abstract; using org.zavyalov.VisualGraphModel.Concrete; using org.zavyalov.VisualGraphModel.Coordinates; using org.zavyalov.GraphModel.Concrete;
Добавьте компонент EditGraph в свой проект.
Далее в классе формы советую определить два объекта
VisualGraph vg ; Mediator mediator;
В конструкторе формы пропишите след. код:
vg = this.editGraph1.vg; mediator = this.editGraph1.mediator;
Где editGraph1 - имя компонента.
Все, компонент может использоваться.
В частности можно получить матрицу смежности:
ConnectivityMatrix connectMatrix = vg.GetConnectivityMatrix();
Сам объект класс ConnectivityMatrix включает 2 поля: int[,] matrix - саму матрицу и Vertex[] vertexs - массив вершин, с помощью которого можно определить индекс той или иной вершины в матрице смежности.
Редактировать граф можно также и из кода:
VisualVertex a1 = VisualVertex.Create(); a1.name = "V1"; CoordinatesVertex c = new CoordinatesVertex(); c.from = new PointF(100, 100); a1.setCoordinates(c); vg.AddVertex(a1); VisualVertex a2 = VisualVertex.Create(); a2.name = "V2"; CoordinatesVertex c2 = new CoordinatesVertex(); c2.from = new PointF(130, 30); a2.setCoordinates(c2); vg.AddVertex(a2); VisualPair p1 = VisualPair.Create(a1, a2); p1.value = 13; vg.AddPair(p1);
Результат будет таким:
Надеюсь, что мое приложение поможет вам сэкономить приличное количество времени.
А вот и сама библиотека, вместе с примером.
В сам код еще по нормальному не вникал, но пока есть два вопроса:
ОтветитьУдалить1) Рефакторинг еще не проводил? Всё вроде красиво написано, но матрица смежности это Adjacency Matrix, а Short в Shot не сокращается
2) Я пока немного не вкурил, кратчайшее расстояние между двумя точками каким методом находится?
>1) Рефакторинг еще не проводил? Всё вроде красиво написано, но матрица смежности это Adjacency Matrix, а Short в Shot не сокращается
ОтветитьУдалитьНет, рефакторинга пока не было. Планирую сделать в ближайшие выходные. Тогда же в коде появится больше комментариев, но кардинально ничего не изменится. Возможно, неправильно опубликовывать проект до подчистки всех хвостов, но я это сделал.
>2) Я пока немного не вкурил, кратчайшее расстояние между двумя точками каким методом находится?
Алгоритм следующий:
1) Находим длину минимального пути алгоритмом фронта волны. А именно, берем вершину a(начальную), находим множество вершин, для которых выполняется: существует дуга, начало которой - a , а конец - данная вершина. Удаляем из этого множества все вершины, принадлежащие другому фронту волны. Затем данный алгоритм повторяется для всех вершины из предыдущего фронта волны. И так до тех пор, пока не найдем конечную вершину.
2)Двигаясь из конечной вершины, составляем путь.
Его длина и все фронты волны нам уже известны.
Алгоритм взят из книги В.Н. Нефедов, В.А. Осипова "Курс дискретной математики".
А почему именно метод фронта волны? Если найду ошибки, тебе куда писать, сюда или на почту?
ОтветитьУдалить>А почему именно метод фронта волны?
ОтветитьУдалитьА чем он тебя не устраивает?
>Если найду ошибки, тебе куда писать, сюда или на почту?
Не сомневаюсь, что они есть. Пиши на почту, на выходных исправлю.
Щас буду использовать, мне надо для задания. Если баги найду, сообщу.
ОтветитьУдалитьОчень помог. А можешь подсказать какой-то алгоритм плоской укладки графа? Их полно, но не знаю какой реально реализовать на компьютере.
ОтветитьУдалитьТакой вот вопрос, можно ли менять цвет дуг и вершин графа?
ОтветитьУдалитьнепонятно на писано про GraphEdit, как его подключить к проекту? В примере не понял где(или как) определяется компонента editGraph1..
ОтветитьУдалитьИ как можно отрисовать граф по матрице смежности?
Спасибо, очень помогло.
ОтветитьУдалитьЧто-то ссылка нерабочая ((((
ОтветитьУдалитьА где пример?
ОтветитьУдалить