Работа с графами
В данном разделе собраны функции и команды работы с графами.
Внимание!
Графы в 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); // Удаляем исходный граф
