Работа с графами
В данном разделе собраны функции и команды работы с графами. Графы в K3 могут быть только плоскими геометрическими. То есть, вершина графа характеризуется двумя координатами на плоскости, а ребро одним параметром - числом. Ребра в K3 ориентированные. Это значит, что порядок вершин у ребра имеет значение. Ребро идет от первой вершины ко второй. Если необходим неориентированный граф, то нужно в граф добавить два ребра с одинаковыми вершинами - «туда» и «обратно».
Инициализация и удаление графа
INT BeginGraph()
Функция BeginGraph инициализирует граф и присваиваем ему уникальный номер. Доступ к элементам графа осуществляется по этому номеру.
LOGCAL FreeGraph(INT <NGraph>)
Функция FreeGraph освобождает память из-под графа с номером <NGraph>
. Функция возвращает единицу в случае удачного завершения или ноль в случае ошибки. Память обязательно должна быть освобождена по окончании использования графа.
Добавление элементов в граф
INT AddVertGraph(INT <NGraph>, DOUBLE <x>, DOUBLE <y>)
INT AddVertGraph(INT <NGraph>, INT <UnObj>)
Функция AddVertGraph добавляет вершину, заданную координатами <x>
,<y>
или номером объекта <UnObj>
(см. Работа с универсальными плоскими объектами) в граф с номером <NGraph>
. Функция возвращает номер вершины, начиная с единицы или ноль в случае ошибки.
INT AddEdgeGraph(INT <NGraph>, INT <Type>, DOUBLE ARRAY <Arr>, DOUBLE <eQ>)
(до 18.02.2020)
INT AddEdgeGraph(INT <NGraph>, INT <Type>, DOUBLE ARRAY <Arr>, DOUBLE <eQ>[, INT <userinfo>])
(с 18.02.2020)
INT AddEdgeGraph(INT <NGraph>, INT <UnObj>, DOUBLE <eQ>)
Функция AddEdgeGraph добавляет ребро, заданной массивом <Arr>
или объектом <UnObj>
(см. Работа с универсальными плоскими объектами) в граф с номером <NGraph>
.
Параметр <Type>
задает тип добавляемого ребра (1 - отрезок, 2 - дуга).
<Arr>
— массив с координатами точек добавляемого ребра. Если добавляется отрезок, в массиве 4 параметра (x1, y1, x2, y2). Если дуга - 6 параметров (x1, y1, x2, y2, xm, ym). Координаты x1, y1 - координаты начала отрезка или дуги, x2, y2 - координаты конца отрезка или дуги, xm, ym - координаты точки на дуге.
Величина <eQ>
— числовой параметр ребра графа.
<userinfo>
— пользовательская метка ребра.
Функция возвращает номер ребра, начиная с единицы или ноль в случае ошибки.
Операции с графом
INT GetNumVerts(INT <NGraph>)
Функция GetNumVerts возвращает число вершин в графе с номером <NGraph>
.
INT GetNumEdges(INT <NGraph>)
Функция GetNumEdges возвращает число ребер в графе с номером <NGraph>
.
LOGICAL InterGraph(INT <NGraph>)
Функция InterGraph находит точки взаимного пересечения ребер графа с номером <NGraph>
и корректирует граф, чтобы не было пересекающихся ребер. Функция возвращает единицу, если граф скорректирован удачно и ноль в случае ошибки.
INT FindLoops(INT <NGraph>)
Функция FindLoops находит "циклы" в графе с номером <NGraph>
и записывает их в тот же граф. "Циклами" в данном случае считаются замкнутые на себя части графа,когда первая вершина совпадает с последней. Функция возвращает число найденных циклов или -1 в случае ошибки.
INT GetNumLoops(INT <NGraph>)
Функция GetNumLoops возвращает число "циклов" в графе с номером <NGraph>
.
INT EquidLoop(INT <NGraph>, INT <NLoop>)
Функция EquidLoop находит эквидистанту с разной высотой в цикле <NLoop>
графа с номером <NGraph>
. Высоты эквидистанты заданы четвертым параметром функции AddEdgeGraph
. При нахождении эквидистанты создается новый граф. Функция возвращает номер графа с эквидистантой или ноль в случае ошибки.
INT LoopByPoint(INT <NGraph>, DOUBLE <x>, DOUBLE <y>)
Функция LoopByPoint возвращает номер цикла в графе с номером <NGraph>
по точке, заданной своими координатами <x>
, <y>
. Функция возвращает номер цикла (начиная с единицы) или ноль в случае ошибки.
LOGICAL EquidGraph(INT <NGraphSource>, INT <NGraphDest>)
Функция EquidGraph строит эквидистантный граф с номером <NGraphDest>
к графу с номером <NGraphSource>
и помещает его в список графов.
Функция возвращает единицу в случае успешного завершения или ноль в случае ошибки.
INT FindObjParts(INT <NGraph>, INT <UnObj>, ARRAY <Arr>)
Функция FindObjParts находит части объекта <UnObj>
(см. Работа с универсальными плоскими объектами) , которые лежат внутри графа с номером <NGraph>
, и заполняет двумерный массив <Arr>
следующей структуры:
- Array[n,5],
где n - номер части при делении,
Array[n,1] — номер объекта в списке объектов;
Array[n,2] — код первой точки объекта (0 - нормальная вершина, 1 - проходит через вершину графа);
Array[n,3] — угол сопряжения первой точки объекта;
Array[n,4] — код второй точки объекта (0 - нормальная вершина, 1 - проходит через вершину графа);
Array[n,5] — угол сопряжения второй точки объекта.
Функция возвращает число частей n.
Получение информации о графе
LOGICAL GetVertGraph(INT <NGraph>, INT <NVert>, DOUBLE <x>, DOUBLE <y>)
Функция возвращает координаты вершины <NVert>
графа с номером <NGraph>
. Координаты записываются в переменные <x>
, <y>
. Функция возвращает единицу в случае удачного завершения и ноль в случае ошибки.
INT GetVertGraph(INT <GraphNum>, INT <VertNum>)
Функция GetVertGraph возвращает номер объекта <UnObj>
(см. Работа с универсальными плоскими объектами), содержащий координаты вершины с номером <NumVert>
графа с номером <GraphNum>
.
INT GetEdgeGraph(INT <GraphNum>, INT <EdgeNum>, DOUBLE ARRAY <Arr>)
(до 18.02.2020)
INT GetEdgeGraph(INT <GraphNum>, INT <EdgeNum>, DOUBLE ARRAY <Arr>[, INT <userinfo>])
INT GetEdgeGraph(INT <GraphNum>, INT <EdgeNum>)
Функция GetEdgeGraph находит ребро с номером <EdgeNum>
графа с номером <GraphNum>
и кладет его координаты в массив <Arr>
.
<userinfo>
— пользовательская метка ребра.
В массиве содержатся координаты:
- линии - 4 элемента (x1, y1, x2, y2)
- дуги - 6 элементов (x1, y1, x2, y2, xm, ym)
Функция возвращает число заполненных элементов массива.
INT GetEdgeGraph(INT <GraphNum>, INT <EdgeNum>)
Функция GetEdgeGraph возвращает номер объекта <UnObj>
(см. Работа с универсальными плоскими объектами) ребра с номером <EdgeNum>
графа с номером <GraphNum>
.
LOGICAL GetVertLoop(INT <GraphNum>, INT <LoopNum>, INT <VertNum>, DOUBLE <x>, DOUBLE <y>)
Функция GetVertLoop заполняет переменные <x>
, <y>
значениями координат вершины с номером <VertNum>
цикла с номером <LoopNum>
графа с номером <GraphNum>
.
Функция возвращает единицу в случае удачного завершения или ноль в случае ошибки (в частности, если вершины с номером <VertNum>
в цикле нет).
INT GetVertLoop(INT <GraphNum>, INT <LoopNum>, INT <VertNum>)
Функция GetVertLoop возвращает номер объекта <UnObj>
(см. Работа с универсальными плоскими объектами) вершины с номером <VertNum>
цикла с номером <LoopNum>
графа с номером <GraphNum>
.
INT GetEdgeLoop(INT <GraphNum>, INT <LoopNum>, INT <EdgeNum>, DOUBLE ARRAY <Arr>)
Функция GetEdgeLoop находит ребро с номером <EdgeNum>
цикла с номером <LoopNum>
графа с номером <GraphNum>
и кладет его координаты в массив <Arr>
В массиве содержатся координаты:
- линии - 4 элемента (x1, y1, x2, y2)
- дуги - 6 элементов (x1, y1, x2, y2, xm, ym)
Функция возвращает число заполненных элементов массива.
INT GetEdgeLoop(INT <GraphNum>, INT <LoopNum>, INT <EdgeNum>)
Функция GetEdgeLoop возвращает номер объекта <UnObj>
(см. Работа с универсальными плоскими объектами) ребра с номером <EdgeNum>
цикла с номером <LoopNum>
графа с номерм <GraphNum>
.
Пример работы с графом
В данном разделе представлен пример макропрограммы работы с графами.
defarr aaa[6]; defarr loo[100]; i=begingraph(); // Инициализируем граф aaa[1]=0; aaa[2]=0; aaa[3]=1400; aaa[4]=0; e1=addedgegraph(i,1,aaa,50); // Добавляем в граф ребро aaa[1]=1400; aaa[2]=0; aaa[3]=1400; aaa[4]=2000; e2=addedgegraph(i,1,aaa,50); // Добавляем в граф ребро aaa[1]=1400; aaa[2]=2000; aaa[3]=0; aaa[4]=2000; e3=addedgegraph(i,1,aaa,50); // Добавляем в граф ребро aaa[1]=0; aaa[2]=2000; aaa[3]=0; aaa[4]=0; e4=addedgegraph(i,1,aaa,50); // Добавляем в граф ребро aaa[1]=0; aaa[2]=500; aaa[3]=1400; aaa[4]=600; e5=addedgegraph(i,1,aaa,100); // Добавляем в граф ребро aaa[1]=1400; aaa[2]=600; aaa[3]=0; aaa[4]=500; e6=addedgegraph(i,1,aaa,100); // Добавляем в граф ребро aaa[1]=700; aaa[2]=0; aaa[3]=700; aaa[4]=2000; e7=addedgegraph(i,1,aaa,70); // Добавляем в граф ребро aaa[1]=700; aaa[2]=2000; aaa[3]=700; aaa[4]=0; e8=addedgegraph(i,1,aaa,80); // Добавляем в граф ребро aaa[1]=0; aaa[2]=1000; aaa[3]=1400; aaa[4]=1000; aaa[5]=700; aaa[6]=1200; e9=addedgegraph(i,2,aaa,80); // Добавляем в граф ребро aaa[1]=1400; aaa[2]=1000; aaa[3]=0; aaa[4]=1000; aaa[5]=700; aaa[6]=1200; e10=addedgegraph(i,2,aaa,80); // Добавляем в граф ребро NULLOUT=InterGraph(i); // Находим точки пересечения и корректируем граф NG=FindLoops(i); // Находим циклы в графе ii=0; loop: ii=ii+1; loo[ii]=EquidLoop(i,ii); // Строим эквидистанту к циклу if (ii<NG) { goto loop; } gri=0; loogri: gri=gri+1; looi=0; nedges=GetNumEdges(loo[gri]); // Получаем число ребер loolooi: looi=looi+1; nz=GetEdgeGraph(loo[gri],looi,aaa); // Получаем по очереди все ребра каждого цикла // Строим ребра if (nz==4) { line aaa[1],aaa[2],0 aaa[3],aaa[4],0 done; } if (nz==6) { arc aaa[1],aaa[2],0 aaa[3],aaa[4],0 aaa[5],aaa[6],0; } if (looi<nedges) { goto loolooi; } if (gri<NG) { goto loogri; } gri=0; llof: gri=gri+1; NULLOUT=FreeGraph(loo[gri]); // Удаляем графы с эквидистантами if (gri<NG) { goto llof; } NULLOUT=FreeGraph(i); // Удаляем исходный граф