Ориентирани графи

Описание на класовете

В записа " TInfo " се съдържа полезна информация, отнасяща се за отделен връх- координати, номер и дали е с фиксирано положение или програмата може да го определя.
Класът "TItem " е класът на върха. Той съдържа два списъка – на следващите (lNexts ) и предходните (lPreviouses ) върхове.

Описваме една структура – " TSelection ", отнасяща се до избирането на елементи от графа – върхове и ребра.
Считаме, че едно ребро е избрано, ако са избрани и двата му, последователни върха.
Последната, логическа променлива ни показва дали съществува значимо избиране въобще.
Указателят на избрания връх се разполага в променливата SecondVertex а при ребро са от значение и двата указателя.
Записът " TEdge " отразява един ръб на графа, чрез указатели на първия и втория му връх.
Записът " Маршрут (TRoot)" е един частично построен път от последователно – съседни върхове, със зададени начален и краен пункт, със списък от забранени ребра.

Класът на графа се състои от указател към текущ връх ( Current) , списък от върховете и променлива описваща направения избор.
Процедурите ще бъдат по подробно обяснени заедно с кода, но не е зле и тук да ги опишем накратко.
Повечето от тях съдържат формални параметри от информация за връх, най-важната от която е неговия номер.
Конструкторът на графа създава един изолиран връх с номер 1.
"Прибави между" (AddBetween) прибавя един нов връх C между върховете A и B , като свързва трите върха в реда: A -> C -> B.
Координатите на новия връх са донякъде произволни и се налага да бъде преместен с мишката.
Ако A и B съшествуват се добавят две нови ребра.
Ако A съшествува а B не се добавят едно ребро: A -> C.
Подобен е и случая при несъществуващо A.
Ако не съществуват и двата върха A и B, то новият връх е изолиран.
Логическите променливипоказват дали са съществуват указаните върхове.

Както можем да се досетим, процедурата " Joint " свързва два върха.
"DeleteVert" премахва съшествуващ връх
"DeleteEdge" - съшествуващо ребро, между съществуващи два върха.
"ReadGr" , "WriteGr" - четене и записване на граф.
" ContinueRoot " продължава маршрут.

Към формата, със заглавие (Caption) Graph добавете контрол за изображение (Image) , контрол за меню и панел (Group Box) за останалите контроли.
Техните имена , заглавия и текстовете в тях трябва да се променят с цел четивността на програмата.
Ето моите предложения:

    Memo1: TMemo;
    OpenDialog1: TOpenDialog;
    SaveDialog1: TSaveDialog;

    Image1: TImage;
    MainMenu1: TMainMenu;
    View1 , MIImageр New1 , MIRead , MIWrite , Close1 : TMenuItem;

    GrpBxTry: TGroupBox;
    BttnAddBetween , BttnJoint  ,  BtnDeleteVert ,  BtnDeleteEdge , BttnClrRt , BttnCntnRt: TButton;

    EdBeg , EdEnd: TEdit;

Чрез щракване на съответния бутон се появява текста на една празна процедура, коуто се премахва при изпълнението на програмата.
За да предотваратите това поставете един фиктивен коментар от вида:
//

Щракнете два пъти с левия бутон на мишката върху контрола на главното менюто и го допълнете със показаните възможности.

Свързаните с формата процедури, в повечето случаи, извикват член-процедурите на класа " TGraph ".
Така е с процедурете, активирани от бутоните:.
BttnAddBetweenClick , BttnJointClick BtnDeleteVertClick BtnDeleteEdgeClick.
BttnCntnRtClick , BttnClrRtClick продължават и нулират един, частично създаден маршрут.
Тези две записват и прочитат граф
MIWriteClick MIReadClick
Това са процедури , свързани със селекцията:
Image1MouseDown(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
Image1MouseUp(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
GraphG:TGraph; // Нашата глобална променлива за граф.
LastDir:string; // Последната, използвана от нас директория.

Създаване и унищожаване на обектите от описаните класовете

constructor TItem.CreateItem;
begin 
// Нулиране на информацията. Върхът не е избран.
  m_Inf.X:=0;m_Inf.Y:=0;m_Inf.Number:=0; m_Inf.Fixed:=False; 
// Създаване на списъците от следходни и предходни върхове, 
// по точно от указатели към тях. В началото те са празни, което прави върха изолиран. 
  lNexts:=TList.Create;
  lPreviouses:=TList.Create;
end;

destructor TItem.DeleteItem;
begin
  lNexts.Clear;lNexts.Free(); // Изчиства списъка и освобождава заеманата от него памет. 
  lPreviouses.Clear;lPreviouses.Free();
end;

constructor TGraph.CreateGraph(InfoF:TInfo);
begin
  Current:=TItem.CreateItem();  // Създава засега единственият връх на графа. 
  Current.m_Inf.Number:=InfoF.Number;
  Vertices:=TList.Create; // Създава празен списък от указатели към върховете на графа. 
  Vertices.Add(Current); // Прибавя в него новосъздадения върх. 
  Selection.FirstVertex:=nil; // Нулира избора. Новосъздадения връх не е избран. 
  Selection.SecondVertex:=nil;
  Selection.HasSelection:=false;
  Root.FirstVertex:=nil; Root.LastVertex:=nil;
  Root.lForbidden:=TList.Create();
  Root.lRoot:=TList.Create();
end;

Радостин ми каза, че при името на един клас е и указател към него, 
така, че няма никакъв смисъл от  глупостите в първото издание.

destructor TGraph.DeleteGraph();
var i:integer; IL:TItem;
begin
  for i:=1 to Vertices.Count do begin
    IL:=Vertices.Items[i-1];
    IL.DeleteItem();  // Задейства унищожителя (деструктура ) на върха. 
  end;
  Vertices.Clear(); Vertices.Free;
end;

Действия върху графа

Да вдъхнем живот на Графа

procedure TForm1.MIImageClick(Sender: TObject);
В началото изчистваме изображението 
  rct.Left:=0;rct.Top:=0;rct.Right:=Image1.Width;rct.Bottom:=Image1.Height;
  Image1.Canvas.FillRect(rct);
След това обхождаме върховете и ги разполагаме по  една окръжност, ако не са фиксирани.
  for i:=1 to GraphG.Vertices.Count do begin
    Item:=GraphG.Vertices.Items[i-1];
    if Item.m_Inf.Fixed then continue;
    Item.m_Inf.X:=round(Image1.Width/2+(Image1.Width/2-10)*cos((i-1)*2*3.1416/GraphG.Vertices.Count));
    Item.m_Inf.Y:=round(Image1.Height/2+(Image1.Height/2-10)*sin((i-1)*2*3.1416/GraphG.Vertices.Count));
  end;
	
За изобразяване на ребрата обхождаме всички върхове на графа и ги изобразяваме с малко кръгче 
около точката с вече изчислените координати. 
    Image1.Canvas.Ellipse(Item.m_Inf.X-3,Item.m_Inf.Y-3,Item.m_Inf.X+3,Item.m_Inf.Y+3);
    Image1.Canvas.TextOut(Item.m_Inf.X,Item.m_Inf.Y,IntToStr(Item.m_Inf.Number)); 
След това обхождаме неговите следваши съседи 
    for j:=1 to Item.lNexts.Count do begin
      Item1:=Item.lNexts.Items[j-1]; 
и начертаваме самото  реброто. 
      Image1.Canvas.MoveTo(Item.m_Inf.X,Item.m_Inf.Y);
      Image1.Canvas.LineTo(Item1.m_Inf.X,Item1.m_Inf.Y);
			

 
procedure TForm1.BttnAddBetweenClick(Sender: TObject);
var bFoundBegL,bFoundEndL:Boolean; InfBegL,InfEndL:Tinfo;
begin
  bFoundBegL:=false;bFoundEndL:=false;
  InfBegL.Number:=StrToInt(EdBeg.Text);
  InfEndL.Number:=StrToInt(EdEnd.Text);
  GraphG.AddBetween(InfBegL,InfEndL,bFoundBegL,bFoundEndL);
// Чертае променения граф. 
  MIImageClick(Sender); 
// Отпечатва това, което сме избрали. 
  PrintMemo(Sender); 
end; 

 
procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);	
При това събитие X и Y са локалните координати на " мишката".
Определяме кой е най-близкият връх до мястото на натискане.
Това става чрез растоянието на Хеминг. 
  L:=GraphG.Vertices.Items[0];
  MinInd:=1;
  Min:=abs(L.m_Inf.X-X)+abs(L.m_Inf.Y-Y);
  for i:=2 to GraphG.Vertices.Count do begin
    L:=GraphG.Vertices.Items[i-1];
    if Min>abs(L.m_Inf.X-X)+abs(L.m_Inf.Y-Y) then begin
      Min:=abs(L.m_Inf.X-X)+abs(L.m_Inf.Y-Y);MinInd:=i;
    end;
  end; 

 Ако сме далеч от всичките връхове -  напускаме: 
  if Min>20 then begin GraphG.Selection.HasSelection:=false;  PrintMemo(Sender); exit; end; 
Но ако сме близо -  втория от стария избор става първи в новия,  
  GraphG.Selection.FirstVertex:=GraphG.Selection.SecondVertex; 
а втория става новоизбрания с "мишката"  
  GraphG.Selection.SecondVertex:=GraphG.Vertices.Items[MinInd-1]; 
  и накрая се фиксира.
  GraphG.Current.m_Inf.Fixed:=true;
Появяват се закратко текущите координати.	
  Image1.Hint:=IntToStr(X)+'  '+IntToStr(Y);
  Image1.ShowHint:=True;
  PrintMemo(Sender);

procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
begin	
// Ако няма избор – нищо, 
  if not(GraphG.Selection.HasSelection) then exit; 
// ако има се променят координатите на втория връх от избора  
  GraphG.Selection.SecondVertex.m_Inf.X:=X; GraphG.Selection.SecondVertex.m_Inf.Y:=Y; 
// и се отразяват промените.  
  MIImageClick(Sender);
end; 

 
  if (LastInRootL.lNexts.Count=0) and (Root.lRoot.count>=1) then begin //we reached an isolated vertex
    new(pEdge);
    pEdge.FirstVertex:=Root.lRoot[Root.lRoot.count-2];
    pEdge.SecondVertex:=Root.lRoot[Root.lRoot.count-1];
    Root.lForbidden.Add(pEdge);
    Root.lRoot.Delete(Root.lRoot.count-1);
    Exit;
  end; 

 
  bAllForbidden:=true;
  for i:=1 to LastInRootL.lNexts.Count do begin
    IL:=LastInRootL.lNexts.Items[i-1];
    if IsForbidden(LastInRootL.m_Inf,IL.m_Inf) then continue
    else begin
      bAllForbidden:=false; break;
    end;
  end;
  if bAllForbidden then begin
    if Root.lRoot.count=1 then begin self.ClearRoot(); exit;end;
    new(pEdge);
    pEdge.FirstVertex:=Root.lRoot[Root.lRoot.count-2];
    pEdge.SecondVertex:=Root.lRoot[Root.lRoot.count-1];
    Root.lForbidden.Add(pEdge);
    Root.lRoot.Delete(Root.lRoot.count-1);
    Exit;
  end;