How to impose coordinates to few graph nodes and reconstruct the missing ones

I am currently working with a graph and the coordinates of few of its nodes are known. Does matlab have native functions to extrapolate a possible position for the nodes with missing coordinates?

[Dyuman Joshi]

For extrapolation, see -

scatteredInterpolant

fittype (Curve fit toolbox)

[Marco Rossi]

Dear all, I think there is a misunderstanding.

I am working with the graph object and I need to reconstruct the coordinates of some points of it. For instance:

s = [1 1 3 4 1];    % starting point of edges
t = [2 3 4 5 5];    % terminal point of edges
G = graph(s,t);

x = [0 1 nan 2 1];    % x coordinate of nodes
y = [0 0 nan 2 1];    % y coordinate of nodes

% I need a function to guess the coordinates of node 3

Answer 1

[Hassaan]

Suppose x and y are your known coordinates and v are the values at those coordinates (which could be some metric related to the nodes):

% Example known data points (x, y coordinates)
x = [1 2 3 4 5];
y = [5 4 3 2 1];

% Define the interpolation method, such as 'linear', 'spline', 'nearest', etc.
interpMethod = 'linear'; % Change this according to your requirements

% Example query points where you want to estimate the values
xq = [1.5, 3.5];

% Extrapolate values at query points using 1D interpolation
vq = interp1(x, y, xq, interpMethod, 'extrap');

% Display extrapolated values
disp(vq);

Example using fittype for a 1D extrapolation:

% Example known data points
x = [1 2 3 4 5];
y = [5 4 3 2 1]; % y could be the known node positions

% Define a linear fit type
ft = fittype('poly1'); % 'poly1' means a linear polynomial a*x + b

% Fit the model to the data
[fitted_curve, gof] = fit(x', y', ft);

% Evaluate the fitted curve at a new point for extrapolation
xq = 6; % Query point outside the known range
yq = feval(fitted_curve, xq);

% Display extrapolated value
disp(yq);

To use these methods for node position estimation in a graph, you would need to adapt them to the specifics of your data, ensuring that the extrapolation method you choose is sensible for your particular application. Consider the nature of the graph and the relationship between nodes when choosing how to extrapolate.

------------------------------------------------------------------------------------------------------------------------------------------------

If you find the solution helpful and it resolves your issue, it would be greatly appreciated if you could accept the answer. Also, leaving an upvote and a comment are also wonderful ways to provide feedback.

Professional Interests

• Technical Services and Consulting
• Embedded Systems
• Electrical and Electronics Engineering

[Dyuman Joshi]

You are not doing extrapolation in the 1st example, that's interpolation and using interp1 whereas you have mentioned something else above.

And your answer is just same as my suggestion with added examples. I don't understand the point of restating the same as an answer.

[Hassaan]

@Dyuman Joshi My aim is to offer clear explanations and relevant examples with each answer. While I target for accuracy, I acknowledge the possibility of alternative solutions and welcome constructive feedback. I have no intention of restating anything nor do I claim perfection.

Answer 2

[Hassaan]

@Marco Rossi Try this and let me know. Thanks.

s = [1 1 3 4 1];    % starting point of edges
t = [2 3 4 5 5];    % terminal point of edges
G = graph(s,t);

x = [0 1 nan 2 1];  % x coordinate of nodes
y = [0 0 nan 2 1];  % y coordinate of nodes

[a, b] = guess_coordinates(G, x, y);

disp(a)
disp(b)


function [guessed_x, guessed_y] = guess_coordinates(G, x, y)
    % Identify the node for which we want to guess the coordinates
    node_to_guess = 3;
    
    % Get the indices of the neighbors of the specified node
    neighbor_indices = neighbors(G, node_to_guess);
    
    % Extract the coordinates of the neighbors
    neighbor_x = x(neighbor_indices);
    neighbor_y = y(neighbor_indices);
    
    % Filter out neighbors with unknown (NaN) coordinates
    known_neighbor_x = neighbor_x(~isnan(neighbor_x));
    known_neighbor_y = neighbor_y(~isnan(neighbor_y));
    
    % Check if there are enough neighbors with known coordinates
    if numel(known_neighbor_x) < 1 || numel(known_neighbor_y) < 1
        error('Not enough neighbors with known coordinates to estimate the position of node 3.');
    end
    
    % Calculate the average coordinates of the known neighbors
    guessed_x = mean(known_neighbor_x);
    guessed_y = mean(known_neighbor_y);
end

This will output the guessed x and y coordinates for node 3. Please note that if node 3 has less than one neighbor with known coordinates, the function will throw an error. You may adjust the condition to require more neighbors if needed for a better estimate.

------------------------------------------------------------------------------------------------------------------------------------------------

If you find the solution helpful and it resolves your issue, it would be greatly appreciated if you could accept the answer. Also, leaving an upvote and a comment are also wonderful ways to provide feedback.

Professional Interests

• Technical Services and Consulting
• Embedded Systems
• Electrical and Electronics Engineering

[Marco Rossi]

Thanks for the interesting solution. Indeed I need a function capable of returning coordinates of any node (even the ones with no neightbors).

• Temporarily I will use the more neighbor (using the function nearest) and making a weighted average of more known positions.

However it is a subobtimal solution. Matlab has functions to draw coordinate-less graphs, and the algorithms used by plot should be capable of drawing graphs with some missing nodes positions.