Player Marking , Optimal Marking Using Graph

Question

I was asked this problem for a challenge, and I decided to share my solution here to review the code:

Here is the problem statement:

For this challenge, we are going to cover some graph problems. We shall imagine a game of basketball or football. If we think of each of the players as nodes in a graph, we can calculate the optimal number of people to mark each of the players.

Let's assume that a player at one vertex can only mark another player if there is an edge between them. So from the example graph, a player at A can mark an opponent at A, B and C. A player at D can mark an opponent at C and D. Each edge of the graph should be covered.

Your goal is to provide a minimum number of players to mark all opponents represented by a graph. So, for example, one solution to this graph could be [1, 1, 1, 1] which indicates you have players stationed at A, B, C, D marking all positions, a total of 4 players. However, this would not be the most optimal. A solution like [0, 1, 0, 1] may be a better solution because the two players at B and D represented by the 1's can mark all other positions comfortably. However again it may not be the most optimal (i.e. the minimum deployment needed to mark all players).

To solve this problem we shall require a function that takes a graph that represents the positions of all players on the football pitch and returns the most optimal marking strategy in the form [1, 0, X, X, ...] where the 1's represent vertices where you would place your player.

We want every player of the opponent's side marked. We shall represent the graph as an adjacency matrix. For example, the above graph of 4 nodes can be represented as a 4 X 4 matrix where the 1's represent an edge between two nodes.

[[0, 1, 1, 0], 
 [1, 0, 1, 0], 
 [1, 1, 0, 1], 
 [0, 0, 1, 0]]

To solve this problem, I was thinking about all algorithms related to graphs like: depth-first search, breadth-first search and Dijkstra shortest path. However, none of them was appropriate for this challenge.

So I decide to go with a simple approach using loops.

1. To solve this problem we will have a function that returns true if a set of markings is a valid solution to a graph of players.

Here is my solution :

def valid_markings(solution, graph):
    marked = [] # the list will contain an edge if it's marked
    for idx, i in enumerate(solution):
    # in this loop we are going to check for marked item
        if  i == 1:
            # add element as marked by him
            for edx_j, j in enumerate(graph[i]):
                if graph[idx][edx_j] == 1:
                    marked.append(edx_j)
    return list(set(marked)) == list(range(0, len(graph)))

In the end, we will compare the marked list, with a list of all elements to check if all elements were marked, so for example:

If graph1 = [[0, 1, 0, 0, 1], [1, 0, 1, 0, 0], [0, 1, 0, 1, 1], [0, 0, 1, 0, 0], [1, 0, 1, 0, 0]], then valid_markings([1, 0, 1, 0], graph1) will return false while valid_markings([1, 0, 1, 0, 1], graph1) will return true

2. The second task was: Write a function that returns the most optimal marking solution for an input graph.

The following function will return the most optimal marking for an input graph. To do it, we will try all possibles markings, and check if they are valid markings by using the previous function. Once all valid markings are found, we need to sort them according to the number of the element it required to achieve a full marking. The most optimal markings are the markings with the lowest number of players.

def optimal_markings(input_graph):
    results_counts = []
    for combination in itertools.product([1, 0], repeat=len(input_graph)):
        results = combination
        if valid_markings(results, input_graph):
            results_counts.append((results.count(1), results))
    optimal_required = sorted(results_counts, key = lambda x : x[0] )[0][0]
    optimal_marking = list(filter( lambda x : x[0] == optimal_required, results_counts))
    return optimal_marking[0]

So one of the optimal markings is

optimal_markings(graph1) is (2, (0, 1, 1, 0, 0)).

Concerns:

• I think my solution is too simple for this problem. If someone has another solution using graph theory kindly add it and explain it.
• So if my solution is a good one please help me to improve it for performance, readability, etc.

Thanks.

Answer 1

Improving the existing

Let's try to improve valid_markings.

Names

I got very confused by valid_markings until I understood i and j where not the index loops but the corresponding value. Depending on the context, naming your variable ì may not be a big deal but in nested loops with enumerate, it is probably better to avoid. I suggest using sol_elt for the elements of solution and _ for the value which is unused (_ is a usual name in Python for throw-away values).

Avoid the un-necessary

The 0 value as a first argument to range is not needed, you can get rid of it.

Also, instead of keeping a list marked and convert it to a set at the end, you can use a set directly.

Finally, because you are considering only 0 and 1, you could write if val == 1 as if val.

You'd have something like:

def valid_markings(solution, graph):
    marked = set() # the list will contain an edge if it's marked
    for i, sol_elt in enumerate(solution):
    # in this loop we are going to check for marked item
        if sol_elt:
            # add element as marked by him
            for j, _ in enumerate(graph[sol_elt]):
                if graph[i][j]:
                    marked.add(j)
    return list(marked) == list(range(len(graph)))

Simplify the logic

Instead of using enumerate to get the index and iterate over both solution and graph, you could use zip.

Also, instead of converting marked to a list and to compare to [0, 1, 2, etc], you could simply count its elements.

You'd have something like:

def valid_markings(solution, graph):
    marked = set() # the list will contain an edge if it's marked
    for sol_elt, line in zip(solution, graph):
    # in this loop we are going to check for marked item
        if sol_elt:
            # add element as marked by him
            for j, _ in enumerate(line):
                if line[j]:
                    marked.add(j)
    return len(marked) == len(graph)

Now, let's try to improve optimal_markings.

Useless variable

combinations and results seem redundant.

Simplify logic

You generate a list of results sorted by score, take the score of the first element, get the list of results with that score and eventually get the first of that list. You could get this directly at first step.

This:

sorted_results = sorted(results_counts, key = lambda x : x[0])
optimal_required = sorted_results[0][0]
optimal_marking = list(filter( lambda x : x[0] == optimal_required, results_counts))
return optimal_marking[0]

becomes this:

sorted_results = sorted(results_counts, key = lambda x : x[0])
return sorted_results[0]

Different way to get the best result

Instead of sorting all the results at the end, we could get track of the best result found so far.

def optimal_markings(input_graph):
    l = len(input_graph)
    marking, score = [1] * l, l
    for comb in itertools.product([1, 0], repeat=l):
        comb_score = comb.count(1)
        if comb_score < score and valid_markings(comb, input_graph):
            marking, score = comb, comb_score
    return (score, marking)

Yet another way to get the best results

Another approach could be to start from the same element than previously and to try to reduce it. At each iteration you keep elements that are still valid:

def optimal_markings(input_graph):
    l = len(input_graph)
    candidates = [[1] * l]
    while True: 
        new_candidates = []
        for cand in candidates:
            for i, val in enumerate(cand):
                if val:
                    new_cand = list(cand)
                    new_cand[i] = 0
                    if valid_markings(new_cand, input_graph):
                        new_candidates.append(new_cand)
        if new_candidates:
            candidates = new_candidates
        else:
            return candidates[0]

A different algorithm

I though that by the time I'd write this, I'd have found the name of the algorithm to solve your problem but I haven't yet. :(

Real life problem and data example

In your description, you say

So from the example graph, a player at A can mark an opponent at A, B and C

which makes sense from what I know of basketball.

But then, from the matrix you provide which an empty diagonal, it looks like a player at A can mark an opponent at B and C but not A.

I reckon you could fix this in your matrix examples or as a special case in your case (spoiler alert: it breaks your tests in any case).