// given a sequence of edges from a graph on n vertices,
// where an edge is a sequence [x,y],
// compute the connected components of the graph
components := function(n, edges)
  comp := [ [i] : i in [1..n] ];
  for e in edges do
    for i in [1..#comp] do
      if e[1] in comp[i] then
        for j in [1..#comp] do
          if e[2] in comp[j] and j ne i then
            comp[i] := Sort(comp[i] cat comp[j]);
            comp := Remove(comp, j);
            break i;
          end if;
        end for;
      end if;
    end for;
  end for;
  return comp;
end function;

// example matrices to test Kruskal's algorithm on
n := 16;
A1 := MatrixRing(Integers(), n) ! 0;
for i in [1..n] do
  for j in [1..n] do
    A1[i,j] := (i^2 - j^2)^2 mod 199;
  end for;
end for;

n := 32;
A2 := MatrixRing(Integers(), n) ! 0;
for i in [1..n] do
  for j in [1..n] do
    A2[i,j] := (i^2 - j^2)^2 mod 199;
  end for;
end for;

n := 64;
A3 := MatrixRing(Integers(), n) ! 0;
for i in [1..n] do
  for j in [1..n] do
    A3[i,j] := (i^2 - j^2)^2 mod 199;
  end for;
end for;


// distance matrix for 25 Dutch cities
D := MatrixRing(Integers(), 25) ! [ 
  0,  47,  47,  46, 139, 123,  86, 111, 114,  81, 164,  67, 126,  73,  18, 147, 190, 176,  63, 141,  78,  20, 109,  65,  70, 
 47,   0,  89,  92, 162, 134, 100, 125, 156,  57, 184,  20,  79,  87,  30, 132, 207, 175, 109, 168,  77,  40, 151, 107, 103, 
 47,  89,   0,  25, 108, 167, 130, 103,  71, 128, 133, 109, 154,  88,  65, 129, 176, 222,  42, 127, 125,  67,  66,  22,  41, 
 46,  92,  25,   0, 132, 145, 108,  78,  85, 116, 157, 112, 171,  63,  64, 154, 151, 200,  17, 102, 113,  59,  64,  31,  66, 
139, 162, 108, 132,   0, 262, 225, 210, 110, 214,  25, 182, 149, 195, 156,  68, 283, 315, 149, 234, 217, 159, 143, 108,  69, 
123, 134, 167, 145, 262,   0,  37,  94, 230,  83, 187, 124, 197,  82, 119, 265, 183,  59, 128, 144,  57, 103, 209, 176, 193, 
 86, 100, 130, 108, 225,  37,   0,  57, 193,  75, 250, 111, 179,  45,  82, 228, 147,  96,  91, 107,  49,  66, 172, 139, 156, 
111, 125, 103,  78, 210,  94,  57,   0, 163, 127, 235, 141, 204,  38, 107, 232, 125, 153,  61,  50, 101,  91, 142, 109, 144, 
114, 156,  71,  85, 110, 230, 193, 163,   0, 195, 135, 176, 215, 148, 132, 155, 237, 285, 102, 187, 192, 134,  40,  54,  71, 
 81,  57, 128, 116, 214,  83,  75, 127, 195,   0, 236,  41, 214, 104,  72, 182, 217, 124, 133, 177,  26,  61, 180, 146, 151, 
164, 184, 133, 157,  25, 187, 250, 235, 135, 236,   0, 199, 147, 220, 178,  58, 309, 340, 174, 259, 242, 184, 168, 133,  94, 
 67,  20, 109, 112, 182, 124, 111, 141, 176,  41, 199,   0,  73, 103,  49, 141, 226, 165, 130, 184,  67,  56, 171, 127, 123, 
126,  79, 154, 171, 149, 197, 179, 204, 215, 214, 147,  73,   0, 166, 109,  89, 289, 238, 188, 247, 140, 119, 220, 176, 144, 
 73,  87,  88,  63, 195,  82,  45,  38, 148, 104, 220, 103, 166,   0,  69, 215, 123, 141,  46,  81,  79,  53, 127,  94, 129, 
 18,  30,  65,  64, 156, 119,  82, 107, 132,  72, 178,  49, 109,  69,   0, 146, 192, 172,  81, 150,  74,  16, 127,  83,  88, 
147, 132, 129, 154,  68, 265, 228, 232, 155, 182,  58, 141,  89, 215, 146,   0, 306, 306, 171, 256, 208, 162, 183, 139,  91, 
190, 207, 176, 151, 283, 183, 147, 125, 237, 217, 309, 226, 289, 123, 192, 306,   0, 243, 135,  50, 191, 176, 213, 183, 218, 
176, 175, 222, 200, 315,  59,  96, 153, 285, 124, 340, 165, 238, 141, 172, 306, 243,   0, 187, 203,  98, 156, 264, 231, 246, 
 63, 109,  42,  17, 149, 128,  91,  61, 102, 133, 174, 130, 188,  46,  81, 171, 135, 187,   0,  85, 111,  76,  81,  48,  83, 
141, 168, 127, 102, 234, 144, 107,  50, 187, 177, 259, 184, 247,  81, 150, 256,  50, 203,  85,   0, 151, 134, 166, 133, 168, 
 78,  77, 125, 113, 217,  57,  49, 101, 192,  26, 242,  67, 140,  79,  74, 208, 191,  98, 111, 151,   0,  58, 177, 143, 148,  
 20,  40,  67,  59, 159, 103,  66,  91, 134,  61, 184,  56, 119,  53,  16, 162, 176, 156,  76, 134,  58,   0, 123,  85,  90, 
109, 151,  66,  64, 143, 209, 172, 142,  40, 180, 168, 171, 220, 127, 127, 183, 213, 264,  81, 166, 177, 123,   0,  44,  92, 
 65, 107,  22,  31, 108, 176, 139, 109,  54, 146, 133, 127, 176,  94,  83, 139, 183, 231,  48, 133, 143,  85,  44,   0,  48, 
 70, 103,  41,  66,  69, 193, 156, 144,  71, 151,  94, 123, 144, 129,  88,  91, 218, 246,  83, 168, 148,  90,  92,  48,   0 
];


// compute cycle via a greedy algorithm, starting with a random vertex
greedy := function(A)
  n := Nrows(A);
  cycle := [ Random([1..n]) ]; // start with a random vertex
  while #cycle lt n do
    // find the closest neighbour not yet in the cycle
    min := 2^31; // arbitrary large number
    for j in [1..n] do
      if not j in cycle and A[cycle[#cycle], j] lt min then
        min := A[cycle[#cycle], j];
        closest := j;
      end if;
    end for;
    cycle := cycle cat [closest]; // append closest neighbour to the cycle
  end while;
  // compute and print the total length of the cycle
  dist := &+[ A[cycle[i], cycle[i+1]] : i in [1..n-1] ] + A[cycle[n], cycle[1]];
  print "greedy algorithm found path of length", dist;
  return cycle;
end function;

