function L = graph_arc_knight ( m, n )

%*****************************************************************************80
%
%% graph_arc_knight() returns the arc list for a knight's move chess board. 
%
%  Discussion:
%
%    There are MxN nodes.
%
%    The MxN board is numbered left to right, top to bottom, as in:
%
%     1  2  3  4  5
%     6  7  8  9 10
%    11 12 13 14 15
%    16 17 18 19 20
%
%    Each square of the chess board is regarded as a node of a graph.  Two
%    nodes are connected (have an arc between them) if a single knight move
%    will transition from one node to the other.
%
%    The arc list is simply a table of all nodes paired in this way.
%
%    For the 4x5 board above, the arc list begins:
%
%     1    12
%     1     8
%     2    11
%     2    13
%     2     9
%     3     6
%     3    12
%     3    14
%     3    10
%     4     7
%     4    13
%     4    15
%     5     8
%     5    14
%     .......
%    20     9
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    06 September 2005
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer m, n: the number of rows and columns of the chess board.
%
%  Output:
%
%    integer L(edge_num,2): the pairs of nodes connected by a knight move.
%
  L = zeros ( 0, 0 );

  node_id = 0;
  edge_num = 0;
%
%  Choose a vertical level.
%
  for y = 1 : m
%
%  Consider, from left to right, the nodes at this vertical level.
%
    for x = 1 : n
      node_id = node_id + 1;
%
%  Consider the four ways in which the x coordinate can be changed.
%
      for x_inc = [ -2, -1, +1, +2 ]
%
%  Consider the corresponding allowed change in y.
%
        y_up = 3 - abs ( x_inc );
        for y_inc = [ - y_up, y_up ]
%
%  For each possible change, does the target node remain in the board?
%  If so, pair it with the starting node and add it to the list.
%
          if ( ...
            1 <= x + x_inc      && ...
                 x + x_inc <= n && ...
            1 <= y + y_inc      && ...
                 y + y_inc <= m )
            node_jd = node_id + y_inc * n + x_inc;
            edge_num = edge_num + 1;
            L(edge_num,1) = node_id;
            L(edge_num,2) = node_jd;
          end

        end
      end
    end
  end

  return
end

