udiagramautolayout.pas

DelphiDoc is a program for automatic generation of documentation on a Delphi-Project. At the momen

 inherited Destroy;                    //free the object
end;


{Lay-outs the diagram.
~param Boxes the boxes in the diagram }
procedure TSugiyamaLayouter.Execute(Boxes: TBoxList);
begin
 //extract the boxes and their associations to nodes in a graph
 ExtractNodes(Boxes);

 //execute the different phases of the layout-algorithm

 LayeringPhase;            //place nodes in layers
 OrderingPhase;            //sort nodes within each layer

 SetYPositions;            //decide final positions for nodes
 SetXPositions;

 //apply the positions of the nodes to the boxes
 ApplyNodes;
end;






























{Extracts the boxes of the diagram to nodes in a graph to sort it.
~param Boxes the boxes in the diagram to transform to nodes in a graph }
procedure TSugiyamaLayouter.ExtractNodes(Boxes: TBoxList);

 {Searches the node of the specified box.
 ~param Box the box to search the node from
 ~result the node of the box }
 function GetNode(Box: TBox): PSortNode;
 var      i      :Integer;            //counter through the list of nodes
 begin
  i := FNodes.Count - 1;              //search the list until found
  while (i >= 0) and (PSortNode(FNodes[i]).Box <> Box) do
   dec(i);
  assert(i >= 0);                     //has to be in the list
  Result := PSortNode(FNodes[i]);     //return the node
 end;

var       i              :Integer;   //counter through each node
          j              :Integer;   //counter through each edge
          Node           :PSortNode; //each new node of a box
          OtherNode      :PSortNode; //other node of an edge
begin
 for i := 0 To Boxes.Count - 1 do    //for each box in the diagram
  begin
   Node := CreateNewNode;              //create a node for it
   try
     Node.Box := Boxes[i];             //save reference to the box
     Node.Id := FNodes.Count;          //use an unique ID

     FNodes.Add(Node);                 //add it to the graph
   except
     Node.FreeNode;
     raise;
   end;
  end;

 for i := 0 To FNodes.Count - 1 do   //for each box in the diagram
  begin
   Node := FNodes[i];                  //get it
   for j := 0 to Node.Box.AssociationCount - 1 do //for each its associations
    with Node.Box.Associations[j] do     //get it
     //not filtered and this box is the source?
     if not IsFiltered and
        ((Node.Box = Source) <> (Kind in [akInheriting, akImplementing])) then
      begin
       if Node.Box = Source then           //get the other node
        OtherNode := GetNode(Destination)
       else
        OtherNode := GetNode(Source);
       if Node.OutEdges.IndexOf(OtherNode) = -1 then //edge not defined yet?
        begin
         Node.OutEdges.Add(OtherNode);       //add edge to the other node
         OtherNode.InEdges.Add(Node);        //and edge from this node to other
        end;
      end;
  end;
end;















{Makes the graph acyclic to be used by this algorithm.~[br]
 The graph must not include cycles to be lay-outed by this algorithm, so these
 must be removed. A cycle is removed by reversing an edge in the cycle by
 Depth First Search. "Strongly connected components" are nodes, that have two
 edges between them in both directions, this is the smallest possible cycle.
 ~[preformatted
   calculate set of strongly connected components
     for each of these components
       if there are more nodes than one in it
         reverse the edge with best score
 loop until each component includes only one node
 ]
 For more info see
 ~[linkExtern http://www.ics.uci.edu/~~eppstein/161/960215.html] and
 ~[linkExtern http://www.ics.uci.edu/~~eppstein/161/960220.html]. }
procedure TSugiyamaLayouter.RemoveCycles;


 {Reverses the direction of an edge between two nodes in the graph.
 ~param Node      the node the edge is emerging from
 ~param EdgeIndex index of the edge in the list of the node }
 procedure ReverseEdge(Node: PSortNode; EdgeIndex: Integer);
 var       ToNode   :PSortNode;        //destination node of the edge
           i        :Integer;          //index of the edge on the other node
 begin
  assert(EdgeIndex < Node.OutEdges.Count);
  ToNode := Node.OutEdges[EdgeIndex];  //get destination node
  i := ToNode.InEdges.IndexOf(Node);   //and index of the edge in it
  assert(i <> -1);

  ToNode.InEdges.Delete(i);            //delete the edge
  Node.OutEdges.Delete(EdgeIndex);

  if ToNode.OutEdges.IndexOf(Node) = -1 then //other direction not defined yet?
   begin
    ToNode.OutEdges.Add(Node);           //add the edge in the other direction
    Node.InEdges.Add(ToNode);
   end;
 end;


 {Called to adjust the score of edges (associations).
 ~param Score    the score that may be changed
 ~param FromNode the node the edge emerges from
 ~param ToNode   the node the edge points to }
 procedure ReScore(var Score: Integer; FromNode, ToNode: PSortNode);
 var       Ass    :TAssociation;       //the association of the edge
 begin
  //search the association of the edge
  if FDiagram.IsFileDiagram then
   Ass := FromNode.Box.FirstAssociationTo(ToNode.Box)
  else
   //in class diagrams the direction of the edges are reversed for the
   //"interesting" associations
   Ass := ToNode.Box.FirstAssociationTo(FromNode.Box);

  //if it is a "main" association (for which no cycles are possible)
  if assigned(Ass) and
     ((Ass.Kind in [akInheriting, akImplementing, akUsingInterface]) or
      ((Ass.Kind = akUsingFile) and
       (TFileReference(FromNode.Box).TheFile.FileType <> sftUnit))) then
   //never reverse this edge
   Score := -1;
 end;


 {Removes an association to break the cycle.
 ~param Cycle nodes in the path of a cycle }
 procedure BreakTheCycle(Cycle: TList);
 var       i            :Integer;   //counter through the nodes of the cycle
           j            :Integer;   //counter through the assciations
           CycNode      :PSortNode; //each node in the cycle
           //each node, a node in the cycle has an edge to
           CycDestNode  :PSortNode;
           Score        :Integer;   //score of an edge to be reversed
           BestScore    :Integer;   //the best score of an edge to be reversed
           RevNode      :PSortNode; //node of the best edge to be reversed
           RevEdge      :Integer;   //index of the best edge to be reversed
 begin
  //find edge in the cycle to remove to break the cycle
  BestScore := -1;               //use edge with highest score
  RevNode := Cycle[0];           //init with last node in cycle
  RevEdge := 0;                  //and its first edge
  for i := 0 to Cycle.Count - 1 do //for each node in the cycle
   begin
    CycNode := Cycle[i];             //get the node
    //for each of its out-going edges
    for j := 0 to CycNode.OutEdges.Count - 1 do
     begin
      CycDestNode := CycNode.OutEdges[j];  //get node the edge points to
      //is an edge within the cycle?
      if Cycle.IndexOf(CycDestNode) <> -1 then
       begin

        //get score of the edge based on the edges of both nodes
        Score := CycNode.InEdges.Count + CycDestNode.InEdges.Count -
                 CycNode.OutEdges.Count;
        if CycNode.OutEdges.Count = 1 then
         Inc(Score, 50);
        //and based on the kind of the association
        ReScore(Score, CycNode, CycDestNode);

        if Score > BestScore then            //new highest score?
         begin
          BestScore := Score;                  //set new highest score
          RevNode := CycNode;                  //save this edge to remove
          RevEdge := j;
         end; //if Score > BestScore
       end; //if Cycle.IndexOf(CycDestNode) <> -1    //edge within cycle?
     end; //for j := 0 to CycNode.OutEdges.Count - 1
   end; //for i := 0 to Cycle.Count - 1

  //reverse the edge; this will keep the association between the nodes,
  //but reverse its meaning (level, dependance, etc.)
  ReverseEdge(RevNode, RevEdge);
 end;

          //structure for each node to mark it in the "Depth First Search"
type      TDFSStruct = record
            Visited: Boolean;      //if it has already been visited
            Removed: Boolean;      //if it has been removed from the cycle
            DFSNum: Integer;   //number in the path of the "Depth First Search"
            //lowest node in DFSList it has an edge to (that means a cycle);
            DFSLow: Integer;       //even indirect
          end;
          //list/variable array of the structure; length equals number of nodes
          TDFSStructArray = array[0..High(Integer) div SizeOf(TDfsStruct) - 1]
                            of TDfsStruct;

          //data for each node for the "Depth First Search"
          //(length is equal the number of nodes in the graph)
var       DFSList        :^TDFSStructArray;
          CycleFound     :Boolean;    //if a cycle has been found
          CurDFS         :Integer;    //current free index in DFSList
          Path           :TList;      //currently visited nodes, unless removed


 {Called recursively to recurse into the graph after the "Depth First Search"
  algorithm.
 ~param Node the node to visit }
 procedure InVisit(Node: PSortNode);
 var       i           :Integer;   //general counters
           DestNode    :PSortNode; //each node this node has an edge to
           Cycle       :TList;     //nodes in the path of a cycle
           CycNode     :PSortNode; //each node in the cycle
 begin
  Path.Add(Node);                  //add current node to the visited part

  with DFSList[Node.Id] do         //initialize the data of the node
   begin                           //in the path
    DFSNum := CurDFS;               //save index in the path
    DFSLow := CurDFS;               //lowest node so far is itself
    Visited := True;                //node has been visited
   end;
  Inc(CurDFS);                     //next index in the path


  //walk all out-edges recursively

  //for each node this node has an edge to
  for i := 0 to Node.OutEdges.Count - 1 do
   begin
    DestNode := Node.OutEdges[i];            //get it
    if not DFSList[DestNode.Id].Removed then //node hasn't been removed?
     if not DFSList[DestNode.Id].Visited then //node not visited yet?
      begin
       InVisit(DestNode);                       //visit it
       //get number of first node in the current path this node has an edge to
       //(even indirect)
       DFSList[Node.Id].DFSLow := Min(DFSList[Node.Id].DFSLow,
                                      DFSList[DestNode.Id].DFSLow);
      end
     else
      //this is a cycle!
      //get number of first node in the current path this node has an edge to,
      //i.e. the number of the already visited node this edge points to
      DFSList[Node.Id].DFSLow := Min(DFSList[Node.Id].DFSLow,
                                     DFSList[DestNode.Id].DFSNum);
   end; //for i := 0 to Node.OutEdges.Count - 1


  //check if there was a cycle, i.e. one of the nodes, this node has an edge
  //to, also has an edge to _exact_ this node, or indirect over other nodes,
  //OR there are no cycles in any nodes this node points to (f.i. it points to
  //no other node)
  if DFSList[Node.Id].DFSLow = DFSList[Node.Id].DFSNum then
   begin
    if Path.Last = Node then         //no cycle?
     begin
      //just remove the node, it contains no cycles, so it's not interesting
      DFSList[Node.Id].Removed := True;              //anymore
      Path.Delete(Path.Count - 1);
     end
    else
     begin
      //a cycle has been found (can't layout diagram so far, need another pass)
      CycleFound := True;

      Cycle := TList.Create;           //create list for the nodes in the cycle
      try

        //move all nodex of the cycle to the list "Cycle"
        repeat                         //each node in the cycle including this
          CycNode := Path.Last;          //remove the node from the path
          Path.Delete(Path.Count - 1);
          Cycle.Add(CycNode);            //add it to the list of the cycle
          DFSList[CycNode.Id].Removed := True;   //it is visited and removed
        until CycNode = Node;          //until this (cycled-to) node is reached

        //remove an association to break the cycle
        BreakTheCycle(Cycle);

        assert(Cycle.Count > 1);
      finally
       Cycle.Free;                     //free list for the nodes in the cycle
      end;
     end; //else Path.Last = Node
   end; //if DFSList[Node.Id].DFSLow = DFSList[Node.Id].DFSNum
 end;

var       i              :Integer;    //counter through each node
          Passes         :Integer;    //counter of passes to make acyclic
          Bytes          :Integer;    //size of data of "Depth First Search"
begin
 Path := TList.Create;                //create list for currently visited nodes
 try

   //calculate size of the array for the "Depth First Search",
   Bytes := FNodes.Count * SizeOf(DFSList[0]);   //an entry for each node
   GetMem(DFSList, Bytes);            //create the array
   try

     Passes := 0;                     //no passes so far

     repeat                           //until acyclic

       CycleFound := False;              //no cycle found so far in this test
       //clear the list (not visited/not removed)
       FillChar(DFSList^, Bytes, 0);

       for i := 0 to FNodes.Count - 1 do //for each node in the diagram
        begin
         Path.Clear;                       //no nodes visited so far
         FillChar(DFSList^, Bytes, 0);     //clear the data
         CurDFS := 0;                      //this node is the start

         //check diagram starting at this node
         InVisit(FNodes[i]);
        end;

       inc(Passes);                      //another pass


       //it's not guaranteed, that this algorithm can make any diagram acyclic;
       if Passes > 50 then    //it depends (also) on the used scoring-method
        raise ELayOutException.Create('Diagram (associations) too complex, layout failed. If possible try filtering some of the associations between the boxes and try again.');

     until not CycleFound;               //until the diagram contains no cycles

   finally
    FreeMem(DFSList);                  //free data for the "Depth First Search"
   end;
 finally
  Path.Free;                          //free list for currently visited nodes
 end;
end;