PHP combination of pairs for a 2D array as part of the solution for Christofides algorithm

Question

I am creating Christofides algorithm for the Traveling Salesman Problem. In part of the algorithm I need to find nodes of a graph that are of odd degree and then calculate the lowest weight. This can be done by the Blossom algorithm, but I am choosing to do it a different way by finding the sum of the possible combinations that you have from a 2D array because I am struggling with the blossom algorithm and do not understand it.

I have 2D array which stores the weights between vertices of odd degree in a graph. For example:

$array = array(
                   0=> array(0, 2, 20,4),
                   1=> array(2,0,7,8),
                   2=> array(20,2,0,12),
                   3=> array(4,8,12,0)
                   )

so between 0 and 1 is of weight 2, if i select the vertices 0 and 1, I am then left with the weight between vertex 2 and 3 because vertex 0 and 1 has already been used. I then need to sum the weights of array[0][1] and array[2][3].

I am struggling with creating an algorithm that returns the combination of possible vertex pairs. For example in the array above the possible pairs are [(0,1)(2,3)],[(0,2)(1,3)],[(0,3)(1,2)]

(0,0),(1,1),(2,2),(3,3) cannot be used as there is no edge weight between them. Also, the reverse of them is not needed([(1,0)(2,3)]).

With these pairs I can then calculate the sum of the weights and choose the smallest.

Any help would be much appreciated.

Answer 1

You can implement the requirements you lay out pretty quickly using php's array_* functions (which I'll do below), but I would be remiss to not call out that the presented solution limits you to an array of just 4 vertices specifically because of this statement:

if i select the vertices 0 and 1, I am then left with the weight between vertex 2 and 3 because vertex 0 and 1 has already been used.

If you have to interact with 5 vertices, the "remaining weight" aspect increases in complexity since you have more than just a left over unused pair. You'll have to define the desired behavior in the case of 5+ vertices to get more assistance if you are not able to modify the code provided below which solves your case of 4.

<?php

$array = array(
                   0=> array(0, 2, 20,4),
                   1=> array(2,0,7,8),
                   2=> array(20,2,0,12),
                   3=> array(4,8,12,0)
                   );

// Use the keys as the list of vertices.
$vertices = array_keys($array);

// Filter out nodes without weights (preserves array keys, which are used as index-relations to other nodes)
$array = array_map('array_filter', $array);

// Create a list of all valid pairs
$fullPairs = array_reduce(array_map(function($vert1, $otherVerts) use ($vertices) {
        // For each first vertice, create pair combinations using weighted edge and remaining vertices
        return array_map(function($vert2) use ($vert1, $vertices) {
                // Because reverse combinations are not desired, we sort the pairings to easily identify dupes
                $vert = array($vert1, $vert2);
                sort($vert);
                $vertPair = array($vert, array_values(array_diff($vertices, $vert)));
                usort($vertPair, function($v1, $v2) { return reset($v1) - reset($v2); });
                return $vertPair;
        }, array_keys($otherVerts));
}, $vertices, $array), 'array_merge', array());

// Unique the list using a string representation of the pairs
$uniqueIndexes = array_unique(array_map('json_encode', $fullPairs));

// Match up the indexes of the unique list against the full pair list to get the pairing structure
$uniquePairs = array_intersect_key($fullPairs, $uniqueIndexes);

// Print the pairings for verification
print_r(array_map('json_encode', $uniquePairs));

// Array
// (
//    [0] => [[0,1],[2,3]]
//    [1] => [[0,2],[1,3]]
//    [2] => [[0,3],[1,2]]
// )

Answer 2

You can use some for-loops when you just need a few combinations.