[PYTHON] Learn with Splatoon nervous breakdown! Graph theory

Introduction

Introducing the knowledge of graph theory used in Splatoon Nervous Weakness made as a hobby, and how the algorithm of graph theory is applied to actual problems. This is an article with the purpose of learning happily.

The app is open to the public, so please play with it if you like.

Splatoon Concentration

Overview description of the app

I wrote on my blog about the rules, problems during development, and a part of the contents of the implementation, so please read that for details.

Splatoon Concentration App Released-Gugurira Nikki

Here's a quick overview, focusing on what you need to read this article.

It's basically the same rule as normal nervous breakdown.

The difference from normal nervous breakdown is that the opponents of the paired cards are diverse and the score changes depending on the rarity of the pair.

In Splatoon Concentration, turn over each card with Splatoon's buki and pair it.

There are many buki in Splatoon, and each buki has a main weapon, a sub weapon, and a special weapon.

In the figure above, the main weapon is displayed on the left, and the sub weapon and special weapon are displayed on the right.

In Splatoon Concentration, you can pair if any of Buki's main weapon, sub weapon, or special weapon matches.

Also, the score when paired will change depending on the type of pair. If you get a rare pair, you will get a high score, and if it is a pair of cards that are easy to pair, you will get a low score.

The logic for setting this score is omitted in this article.

You can see it as a weighted undirected graph by using Buki as a node, whether it can be paired as an edge, and the score when paired as an edge weight.

This time, I would like to learn the knowledge of graph theory required for Splatoon nervous breakdown using this weighted undirected graph as a theme.

Which card do you use for the game? ~ Concatenated subgraph ~

This time, we targeted Splatoon 2 Buki, so there are 139 types of cards in all. If you use all of these to cause nervous breakdown, your nerves will really weaken, so I would like to take out only a part and use it in the game. (This time, 12 types will be used for the game.)

The easiest way is to select from 139 types of buki completely randomly without allowing duplication, but this method tends to reduce the number of pairs that can be created.

in this way,

• I want the type of card to change every time
• And it is easy to make a pair to some extent

It is a requirement that you want to get a set of cards.

This time to meet this requirement

1. Randomly select one buki
2. Randomly obtain from candidates for buki that can be paired with any of the buki currently selected
3. Continue 2 until 12 are collected

I made the algorithm.

When you make a graph with Buki as a node and whether it is paired as an edge, you randomly select the start node and sample one connected subgraph that includes that node.

Here is the one implemented in Python.

def get_connected_subgraph(mat, seed_node, nodes_num):
    """Receives an adjacency matrix and nodes that are seeds, and the number of nodes is nodes_Returns a concatenated subgraph of num."""
    ans = {seed_node}
    while len(ans) < nodes_num:
        sampled = random.sample(ans, 1)[0]
        connected_nodes = set(np.where(mat[sampled] > 0)[0].tolist())
        candidates = list(connected_nodes - ans)
        if len(candidates) == 0:
            raise Exception("Failed.")
        to_be_added = random.choice(candidates)
        ans.add(to_be_added)
    return list(ans)

Of course, it is not necessary to have one connected component, but if you take a subgraph with a connected component with a small number of elements, the diversity of pairs will be small and the game will not be interesting, so the connected component is I made it one.

Here is a drawing of the graph randomly acquired by this code. If it is 12, it is difficult to understand, so I narrowed it down to 6.

Can you get rid of all the cards? ~ Perfect matching ~

Perfect matching

The concatenated subgraphs obtained by the algorithm in the previous chapter are somewhat easier to pair. Since it is linked, there are opponents who can pair any card at the beginning of the game.

However, just because it is connected does not mean that you can remove all the cards. The following is an example. Two nodes are left over by all means.

Matching is the problem of pairing nodes that are connected by edges from the nodes in the graph. (The same node cannot be used twice.)

The question I want to ask this time is, "When matching the nodes of the obtained graph, can the matching be done so that all the nodes are used up?"

Matching that uses all the nodes in this way is called perfect matching.

In this case, if the set of cards (the graph made up of) is a graph that has perfect matching, then ** hopefully all the cards can be removed **. It can be said that.

It seems difficult to directly fetch a graph that has perfect matching among the subgraphs of a certain graph (please tell me if there is a good way).

This time, I will judge "Is the graph that has perfect matching?" The graph obtained by using the method of taking the subgraph explained earlier. The logic is to keep sampling until a graph with perfect matching exists.

Judgment of perfect matching

The judgment is "Is the graph with perfect matching?", But this can be judged using Tutte theorem.

Reference: I want to be friends with Tutte theorem

I implemented the judgment logic according to this theorem. Written in Python.

python

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components
import itertools

def get_all_sub_indexes(repeat_num):
    """bit for full search"""
    sub_indexes = []
    for case in itertools.product([0, 1], repeat=repeat_num):
        sub_indexes.append([i for i, v in enumerate(case) if v == 1])
    return sub_indexes

def exists_perfect_matching(G):
    """Takes the adjacency matrix of a graph and determines if it contains a complete graph."""
    size_G = G.shape[0]
    sub_indexes = get_all_sub_indexes(size_G)

    for sub_index in sub_indexes:
        # sub_index is G-Equivalent to U
        size_U = size_G-len(sub_index)
        G_minus_U = G[np.ix_(sub_index, sub_index)]
        #Decomposed into connected components
        csr_graph = csr_matrix(G_minus_U)
        _, groups = connected_components(csr_graph, directed=False)
        conntected_nodes = collections.Counter(groups)
        odd_G_minus_U = len(
            [freq for freq in conntected_nodes.values() if freq % 2 == 1])
        if odd_G_minus_U > size_U:  #From Tutte theorem
            return False
    return True

A full bit search is performed on the node set, the nodes are removed from the original graph and decomposed into connected components, and the number of connected components with an odd number of nodes is counted and judged by the inequality of Tutte theorem.

Bit full search uses ʻitertools, and connected component decomposition uses scipy`. If the number of nodes is 12, it would take a little time. Since it costs $ O (2 ^ n) $ in the bit full search part, it seems to be heavy if the number of nodes is a little larger.

The logic was to keep sampling until a graph with perfect matching exists. I was worried that if perfect matching was not possible, the latency would increase when I accessed it, so I experimented.

When I took a random (but concatenated) graph with 12 nodes and examined whether it included perfect matching, I simulated 100 times and found that the graph did not include perfect matching only once. was. There is a 1% chance that the perfect match will be judged twice, so if you feel that it is a little heavy, it may be 1%.

Since the original graph is a fairly dense graph, it may be easy to get a perfect match. (Of course, by bringing in a concatenated graph, it is effective to bring in candidates that are likely to be perfect matching.)

Can't you make a "graph that can take all the cards absolutely"?

Earlier, a graph with perfect matching = ** Hopefully all the cards can be removed ** I used to say that a graph has something stuck in the back teeth, but ** a graph with perfect matching is absolutely Not all cards can be removed. ** **

Even if perfect matching exists, it may result in non-perfect matching.

Here again, in terms of graph theory, "matching that cannot add more pairs" is called maximum matching. Splatoon nervous breakdown this time is matching in a state where the number of pairs cannot be increased any more.

It can be said that the end condition of the game is when the cards are paired and the matching becomes the maximum matching. Just because there is perfect matching, not all maximal matching is perfect matching, so it has become the phrase ** hopefully all the cards can be removed **. ..

In conventional nervous breakdown, all maximal matching is perfect matching, so it is possible to finally cut off all cards no matter how you take it.

Then, for a given graph, it would be nice if we could judge "Is all maximal matching perfect matching?" I think, but this seemed difficult.

It is judged whether the minimum and maximum matching is perfect matching, but I gave up because it seems to be difficult to find the minimum and maximum matching.

[Minimum Maximum Matching Problem-Wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E6%A5%B5%E5%A4%A7%E3%83% 9E% E3% 83% 83% E3% 83% 81% E3% 83% B3% E3% 82% B0% E5% 95% 8F% E9% A1% 8C #: ~: text =% E6% 9C% 80% E5% B0% 8F% E6% A5% B5% E5% A4% A7% E3% 83% 9E% E3% 83% 83% E3% 83% 81% E3% 83% B3% E3% 82% B0% E5% 95% 8F% E9% A1% 8C% EF% BC% 88% E3% 81% 95% E3% 81% 84,% E3% 81% 8C% E7% 9F% A5% E3% 82% 89% E3% 82 % 8C% E3% 81% A6% E3% 81% 84% E3% 82% 8B% E3% 80% 82)

For this reason, since we are only using a graph that has perfect matching, the problem of falling into maximum matching that is not perfect matching remains.

The figure when the last two sheets are finished without being paired.

What is the theoretical highest point? ~ Maximum weight matching ~

In addition to the part that samples the graph, I would like to introduce another process that uses graph theory.

We will use the card set sampled as described above to cause nervous breakdown, but since the maximum score that can be obtained changes for each sampled graph, ** the score I got is high or low. There is a problem that it is difficult to understand **.

Therefore, it would be nice to be able to calculate and display the highest score that can be obtained when a graph is sampled and the graph has a nervous breakdown.

In graph theory, this problem is the maximum weight matching problem.

The maximum weight matching problem is a problem of finding a match that maximizes the sum of the weights, and it matches what we want to do this time.

There seemed to be a Python implementation here, so I used it.

Reference: Combinatorial optimization --Typical problem --Weight matching problem --Qiita

import networkx as nx
from ortoolpy import graph_from_table

def get_max_weight_matching(mat):
    node_df = pd.DataFrame({"id": list(range(len(mat)))})
    edge_df = graph2df(mat)
    g = graph_from_table(node_df, edge_df)[0]
    d = nx.max_weight_matching(g)
    return sum([mat[k, v] for k, v in d.items()])/2  #Because it counts twice

def graph2df(graph):
    edge_df = pd.DataFrame(columns=['node1', 'node2', 'weight'])
    for i in range(graph.shape[0]):
        for j in range(i, graph.shape[1]):
            if graph[i, j] > 0:
                edge_df = edge_df.append(
                    {'node1': i, 'node2': j, 'weight': graph[i, j]}, ignore_index=True)
    return edge_df.astype("int64")

Let's find the maximum weight matching for this graph obtained earlier.

This is,

It will be matched like this. The theoretical value of the highest score in this graph was calculated to be 162.

As an aside, in this result, the maximum weight matching is a perfect match, but in general it does not always match.

In other words, even if you cut off all the cards as shown in this figure, it is possible that you will not reach the highest score.

in conclusion

This time, the content was to learn about the graph theory used internally, especially matching, based on the self-made application called Splatoon Concentration.

It's exciting to see mathematics being applied to real problems, not just graph theory. When I actually face a problem, I would like to have a lot of drawers asking "Is that algorithm usable?"

Until the end Thank you for reading!