CODEWITHSUNDEEP
delphigraph
NaN
NaN

Reputation: 9094

How to implement depth first search (DFS) on graphs in Delphi?

I have looked into the Internet and did not found any code example for DFS (Depth first search) nor BFS (Breadth First Search) in object pascal so I may implement them in Delphi.

For those who do not know Graph Theory, click here

I am having difficult to develop it on my own because of the way graph objects are. We have vertices and edges that are related between and I do not know if I use records, objects or arrays, nor how to structure those data. If I had some previews examples, I could choose a best approach and not start from scratch (I believe this site is here for it).

Does anyone know where to begin?

A graph with 6 edges and 7 vertices

In my project I will have to insert a new graph into it and then make a DFS search to catch all the edges and discover the closest path to highways.

Upvotes: 2

Views: 2234

Answers (2)

Sean B. Durkin
Sean B. Durkin

Reputation: 12729

The short answer is that you can implement DFS by keeping an associative array mapping visted nodes to a union of preceding node and neighbours visited.

Usage

Here is what a solution might look like at the surface. Let us say you define a node sic...

type
INode = interface
  ['{8D3C78A3-3561-4945-898D-19C5AD4EC35B}']
    {$REGION 'property accessors'}
      function GetNeighbour( idx: Integer): INode;
      function GetNeighbourCount: integer;
    {$ENDREGION}
    function  DisplayName: string;
    function  Link( const Neighbours: INode): boolean; // True iff succesful.
    procedure ShutDown; // Dereference all nodes recursively.
    property  Neighbours[ idx: Integer]: INode  read GetNeighbour;
    property  NeighbourCount: integer           read GetNeighbourCount;
  end;

I leave the implementation of INode up to the OP, because (A) it is trivial; and (B) because it is highly application specific.

You will be able to traverse the network of nodes Depth-first, sic...

procedure DFSTraversal( const Start: INode);
var
  X: INode;
begin
for X in TGraph.DepthFirstSearch( Start) do
  DoSomething( X);
end;

... with the aid of a few declarations sic...

INodeEnumerator = interface
  ['{1A8725EB-AE4B-474C-8052-E35852DCD5FC}']
    function  GetCurrent: INode;
    function  MoveNext: Boolean;
    procedure Reset;
    property  Current: INode read GetCurrent;
  end;

IEnumerableNode = interface
  ['{DA11A890-01C4-4FD0-85BB-AE9D65185364}']
    function GetEnumerator: INodeEnumerator;
  end;

TGraph = class
  public
    class function DepthFirstSearch( const StartingPoint: INode): IEnumerableNode;
  end;

Solution

Depth First Search can be easily implemented, using, as stated before, an associative array mapping visited nodes to preceding nodes and neighbours visited. This associative array is encapsulated into the type TDictionary. Here is how it might be implemented ...

type
TBaseEnumerableNode = class abstract( TInterfacedObject, IEnumerableNode)
  protected
    function GetEnumerator: INodeEnumerator; virtual; abstract;
  end;

TDepthFirstSearchEnumerable = class( TBaseEnumerableNode)
  private
    FRoot: INode;
  protected
    function GetEnumerator: INodeEnumerator; override;
  public
    constructor Create( const Root: INode);
  end;

TBaseNodeEnumerator = class abstract( TInterfacedObject, INodeEnumerator)
  private
    function  GetCurrent: INode;
    procedure Reset;
  protected
    FCurrent: INode;
    function  MoveNext: Boolean;  virtual; abstract;
  end;

RTraversalInfo = record
    FCurrIndex: integer;
    FPredecessor: INode;
  end;

TDepthFirstSearchEnumerator = class ( TBaseNodeEnumerator)
  private
    FVisitedNodes: TDictionary<INode,RTraversalInfo>;
  protected
    function  MoveNext: Boolean;  override;
  public
    constructor Create( const Root: INode);
    destructor Destroy; override;
  end;


class function TGraph.DepthFirstSearch(
  const StartingPoint: INode): IEnumerableNode;
begin
result := TDepthFirstSearchEnumerable.Create( StartingPoint)
end;


constructor TDepthFirstSearchEnumerable.Create( const Root: INode);
begin
FRoot := Root
end;

function TDepthFirstSearchEnumerable.GetEnumerator: INodeEnumerator;
begin
result := TDepthFirstSearchEnumerator.Create( FRoot)
end;


function TBaseNodeEnumerator.GetCurrent: INode;
begin
result := FCurrent
end;

procedure TBaseNodeEnumerator.Reset;
begin  // Not used.
end;

constructor TDepthFirstSearchEnumerator.Create( const Root: INode);
var
  TravInfo: RTraversalInfo;
begin
FCurrent := Root;
FVisitedNodes := TDictionary<INode,integer>.Create;
TravInfo.FCurrIndex   := -1;
TravInfo.FPredecessor := nil;
FVisitedNodes.Add( FCurrent, TravInfo)
end;

destructor TDepthFirstSearchEnumerator.Destroy;
begin
FVisitedNodes.Free;
inherited
end;

function TDepthFirstSearchEnumerator.MoveNext: boolean;
var
  ChildIdx: integer;
  LastIdx : integer;
  TravInfo: RTraversalInfo;
  Next    : INode;
  Child   : INode;
  GoDown  : boolean;
begin
result := assigned( FCurrent);
if not result then exit;
result := False;
Next := FCurrent;
FCurrent := nil;
repeat
  TravInfo := FVisitedNodes[ Next];
  ChildIdx := TravInfo.FCurrIndex;
  LastIdx  := Next.NeighbourCount - 1;
  GoDown := ChildIdx <= LastIdx;
  if GoDown then
    begin
    Inc( ChildIdx);
    TravInfo.FCurrIndex := ChildIdx;
    FVisitedNodes[ Next] := TravInfo;
    GoDown := ChildIdx <= LastIdx
    end;
  if GoDown then
      begin
      Child := FCurrent.Neighbours[ ChildIdx];
      result := not FVisitedNodes.ContainsKey( Child);
      if result then
          begin
          FCurrent := Child;
          TravInfo.FPredecessor := Next;
          TravInfo.FCurrIndex   := -1;
          FVisitedNodes.Add( FCurrent, TravInfo)
          end
        else
          Next := Child
      end
    else
      Next := TravInfo.FPredecessor
until result or (not assigned( Next))
end;

Upvotes: 3

LU RD
LU RD

Reputation: 34889

I suggest to look at DelphiForFun Graph Searching, where you can find examples and a tutorial implementing both depth first search (DFS) and breadth first search (BFS).

Data for the DFS is contained in a TStringList descendant, where nodes are identified with a text string which is also used as a key for sorting. Sorting is done with a binary search algorithm.

Node data containing a list of pointers to adjecent nodes (adjecency list), are stored in the string list as objects to each item string.

Quote from the tutorial about the DFS algorithm:

Here is the pseudocode for depth first search: 

SearchGoalDF(nodenbr, goalkey, maxdepth) - search depth first for all solutions from nodenbr node to goalkey node with depth of maxdepth or less.
    Set visited array to false, visited has an boolean entry for each node.
    clear stack
    push nodenbr node onto stack
    call dfs
    end.
dfs

pop (retrieve and delete)  most current stack entry, temp.
    mark temp as visited.  {to avoid looping back here as we search on down}
    if  temp.key=goalkey then notify caller of solution found
    else if stack.count<maxdepth then for each  node in temp's adjacency list, 
    push adjacent[i] onto stack
    call dfs
     mark temp as unvisited {there might be another path through this node to a solution}
    end.

Hope this will get you started and some insight how to handle node data.

Note that finding the shortest path, a BFS algorithm seems to do a better job:

See Shortest path: DFS, BFS or both? and Why can't DFS be used to find shortest paths in unweighted graphs?.

Upvotes: 1

Related Questions