function path = helperBLEMeshPath(sourceNode, destinationNode, meshNodes, totTuples)
%helperBLEMeshPath Returns path from source to destination within mesh
%network
%   PATH = helperBLEMeshPath(SOURCENODE, DESTINATIONNODE, MESHNODES,
%   TOTTUPLES) returns the path from source node, SOURCENODE, to
%   destination node, DESTINATIONNODE, within the Bluetooth mesh network
%   having MESHNODES, nodes with the given transactions, TOTTUPLES.
%
%   PATH (vector) containing path from source to destination within the
%   mesh network derived using DFS (Depth First Search) algorithm. If there
%   is no path exist between source and destination, "-1" will be returned.
%
%   SOURCENODE and DESTINATIONNODE are unique identifiers (positive
%   integer) given to the respective nodes within the Bluetooth mesh
%   network.
%
%   MESHNODES is a vector of objects of type helperBLEMeshNetworkNode or
%   helperBLEMeshNode. It represents nodes within the Bluetooth mesh
%   network.
%
%   TOTTUPLES (n-by-2 array) having message exchanges within the Bluetooth
%   mesh network.

%   Copyright 2019 The MathWorks, Inc.

% Number of nodes within the Bluetooth mesh network
totalNodes = numel(meshNodes);

% Initialize
path = zeros(1, totalNodes);
nodeIDs = zeros(1, totalNodes);
pathIndex = 1;
hasPath = false;

% Initialize visited flag for each node
isVisited = zeros(1, totalNodes);

% Identifiers for the nodes within the Bluetooth mesh network
for idx = 1:totalNodes
    nodeIDs(idx) = meshNodes(idx).Identifier;
end

% Push source node "sourceNode" into path
path(pathIndex) = sourceNode;
pathIndex = pathIndex + 1;

% Mark source node "sourceNode" as visited
isVisited(nodeIDs == sourceNode) = 1;

while (~hasPath)
    % Fetch top node from the path
    topNode = path(pathIndex-1);
    
    % Fetch next node to be visited
    nextUnvisitedNode = getNextUnvisitedNode(...
        topNode, isVisited, totTuples, nodeIDs);

    % All nodes are visited from "topNode"
    if nextUnvisitedNode == -1
        % Pop "topNode" node from the path
        path(pathIndex-1) = 0;
        pathIndex = pathIndex - 1;
        % Path doesn't exist
        if pathIndex <= 1
            path = -1;
            break;
        end
        continue;
    % Path found from "sourceNode" to "destinationNode"
    elseif nextUnvisitedNode == destinationNode
        hasPath = true;
    end
    
    % Mark next unvisited node as visited
    isVisited(nodeIDs == nextUnvisitedNode) = 1;
    
    % Push next unvisited node into path
    path(pathIndex) = nextUnvisitedNode;
    pathIndex = pathIndex + 1;
end

% Return identified path between source and destination within the
% Bluetooth mesh network
if hasPath
    path = path(1:pathIndex-1);
end
end

function unvisitedNode = getNextUnvisitedNode(curNode, isVisited, totTuples, nodeIDs)
% Initialize
unvisitedNode = -1;

% Traverse over all the tuples (each tuple defines a message exchange
% between the nodes within the Bluetooth mesh network)
for idx = 1:numel(totTuples)/2
    % Fetch the next unvisited node from the given node "curNode"
    if (totTuples(idx, 1) == curNode) && ~(isVisited(nodeIDs == totTuples(idx, 2)))
        unvisitedNode = totTuples(idx, 2);
    end
end
end
