Data Structures in the C programming language for labeled Ugraph

 
 All labels are natural numbers.  If a graph has exactly N nodes that are not isolated, then all the first N natural numbers
(1,2,...,N) are assigned to those nodes, so that each node receives a different label. In this discussion the symbol Nnodes replaces that N. Then Nnodes is the number of all the non-isolated nodes. Also it is the largest assigned label. 
Isolated nodes receive no labels and are ignored. In most discussions in this volume  Nnodes < 13.

In this volume the words  node H  will mean that H is any integer satisfying 1<= H <= Nnodes.

Space in memory must be allocated for arrays. Symbol MM will denote the amount of space in integers allocated for all arrays that relate integers to each label.   MM is assigned a natural number through the #define MM    statement. It means that 
                  each assigned label is less than MM. This means that  Nnodes < MM.
In all programs in this volume, MM = 51. Therefore, the largest label  Nnodes  cannot be larger than 50. 

Let  Nlinks  denote the number of links in a Ugraph. Each link has two equivalent pairs  X - Y  and its reverse  Y - X for nodes X and Y. Both pairs for every pair of linked nodes will be needed in some programs. Then the total number of linked pairs will be  Npairs = 2 x Nlinks. Npairs is always even.

The number of links in a Ugraph with less than MM nodes is itself less than MM x (MM-1)/2 (see discussion about complete graphs). Therefore, Npairs < MM x (MM - 1).  To allocate space,  NN   for all double representations of links, 
                                        NN = MMx(MM-1).
This forces NN > 2 x Nlinks = Npairs.  In this volume, NN=2550.
 

 The pair   A[NN], B[NN]  of integer arrays are the computer representation of a U graph.
    For each integer K, 1 <= K <= Npairs,  A[K] is a node and B[K] is a neighbor.
    (Therefore, A[K] - B[K] is a link in the graph. Although not used is the fact that K is a number assigned to that link.      Each link actually receives two such numbers from indices of A and B.)
   Just outside this range of K,   A[0] = Npairs, B[0] = Nnodes,       A[Npairs+1] = B[Npairs+1] = 0, end of data markers. 
   The number of links = A[0]/2.

      Graph data in both consist of pairs A[K],B[K] of natural nlumbers for each integer K, 1 <= K <= Npairs, 
          Npairs locates the end of the data. A[Npairs] = Nnodes (last node) and B[Npairs] = largest neighbor of A[Npairs]

    
     A[ ] is non-decreasing: A[K]<=A[K+1], for any integer K, 0 < K < Npairs
     B[ ] is partially increasing, if A[K[=A[K+1] then B[K]<B[K+1], for any integer K, 0 < K<Npairs
 
     A[K] is not equal to B[K] for any integer K, 1 <= K <= Npairs.

      for each K, 1 <= K <= Npairs, B[K] is a neighbor of A[K] , that is, there is a link between node A[K] and node B[K],         Note: the index K is actually a natural number assigned to each link, (there are two numbers for each link)
     for any distinct natural numbers X and Y <= Nnodes, 
        if there is a link between node X and node Y, then there exist unique natural numbers K,K' <= Npairs such that
        X=A[K] and Y=B[K], and  such that Y=A[K'] and X=A[K'].     (each undirected link requires a reverse link)

 
Two more integer arrays LOC[MM]  and DEG[MM]  accompany the main arrays A and B
  LOC[0] and DEG[0] are not used.    LOC[Nnodes+1] = Npairs+1;   DEG[Nnodes+1] is not used.

  For every node H (1 <= H <= Nnodes),
     LOC[H] = index location of node H,   DEG[H] = degree of node H (number of links contacting node H) 
 For every node H <= Nnodes, LOC[H+1] = LOC[H] + DEG[H]         (node H cannot be isolated)

 For editing purposes a square array C[MM][MM] is created.  The first dimension involves all the integers 0,1,2,...,Nnodes. The top array C[0][J] is not used, nor are any arrays after C[Nnodes][J].
 Each node I corresponds to an array C[I][J]. For J>0 all neighbors of node I are listed. 
                    C[I][0] = the number of neighbors of node I = DEG[I].
Therefore C[1,1] = the first neighbor of the first node 1  and C[N][L] = the last neighbor of the last node, where   N=Nnodes, L= C[N][0].