Работа с графами

Материал из GEOS_WIKI
Перейти к: навигация, поиск

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

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> - числовой параметр ребра графа.

Функция возвращает номер ребра, начиная с единицы или ноль в случае ошибки.

Операции с графом

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>)

INT GetEdgeGraph(INT <GraphNum>, INT <EdgeNum>)

Функция GetEdgeGraph находит ребро с номером <EdgeNum> графа с номером <GraphNum> и кладет его координаты в массив <Arr>. В массиве содержатся координаты:

  • линии - 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);  // Удаляем исходный граф