graph theory, data structure, python,

Among Us: Graph Theory & Data Structure

Stéphan Stéphan Follow on Github Dec 18, 2020 · 208 mins read
Among Us: Graph Theory & Data Structure
Share this
LEBLANC_&_ADJARIAN_Among_Us

Presentation : Among Us - Mini problem

This mini-problem is available online: ADSA Project.

You should definitely go on Google Collab try the code.

The subject can also be downloaded here. And this is the report we've submitted to the computer science department.

Basically, this is about organizing a giant tournament of Among Us with the best data structure, setting up the best strategies to demask impostor using our graph theory skills. So here is the code we worked on to achieve this. Don't hesitate to copy the notebook to run it.

NB: Some functions are interactive.

This job has been done by ADJARIAN Stéphan & LEBLANC César.

Step 1

In [114]:
import random
import numpy as np


class Player:
    """Create nodes that represent players with their information."""
    def __init__(self, player):
        self.player = player
        self.name = player["name"]
        self.impostor = player["impostor"]  # True or False
        self.scores = player["scores"]
        self.score = player["scores"][0]
        self.info = player["name"] + " " + str(player["scores"][0])
        self.left = None
        self.right = None
        self.height = 1

    """Some nice display methods found on geeksforgeek blog."""
    def display(self):
        lines, *_ = self._display_aux()
        for line in lines:
            print(line)

    def _display_aux(self):
        if self.right is None and self.left is None:
            line = '%s' % self.info
            width = len(line)
            height = 1
            middle = width // 2
            return [line], width, height, middle
        if self.right is None:
            lines, n, p, x = self.left._display_aux()
            s = '%s' % self.info
            u = len(s)
            first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
            second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
            shifted_lines = [line + u * ' ' for line in lines]
            return [first_line, second_line] + \
                    shifted_lines, n + u, p + 2, n + u // 2
        if self.left is None:
            lines, n, p, x = self.right._display_aux()
            s = '%s' % self.info
            u = len(s)
            first_line = s + x * '_' + (n - x) * ' '
            second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' '
            shifted_lines = [u * ' ' + line for line in lines]
            return [first_line, second_line] + \
                    shifted_lines, n + u, p + 2, u // 2
        left, n, p, x = self.left._display_aux()
        right, m, q, y = self.right._display_aux()
        s = '%s' % self.info
        u = len(s)
        first_line = (x + 1) * ' ' \
                      + (n - x - 1) * '_' \
                      + s + y * '_' \
                      + (m - y) * ' '
        second_line = x * ' ' + '/' \
                      + (n - x - 1 + u + y) * ' ' \
                      + '\\' + (m - y - 1) * ' '
        if p < q:
            left += [n * ' '] * (q - p)
        elif q < p:
            right += [m * ' '] * (p - q)
        zipped_lines = zip(left, right)
        lines = [first_line, second_line] \
                + [a + u * ' ' + b for a, b in zipped_lines]
        return lines, n + m + u, max(p, q) + 2, n + u // 2

"""AVL tree class with nodes containing dictionnary with player's info."""
class AVLTree(object):

    """Recursive function to insert nodes in our AVL tree."""
    def insert_player(self, root, player):
        # Since we passed a node in argument and not a key
        # we have to retrieve beforehand the key value
        score = player.score

        # Step 1 - Perform normal BST 
        if root is None:
            return player
        elif score < root.score:
            root.left = self.insert_player(root.left, player)
        else:
            root.right = self.insert_player(root.right, player)

        # Step 2 - Update the height of the ancestor node 
        root.height = 1 + max(self.get_height(root.left),
                              self.get_height(root.right))

        # Step 3 - Get the balance factor 
        balance_factor = self.get_balance(root)

        # Step 4 - If the node is unbalanced, then try out the 4 cases 
        # Case 1 - Left Left 
        if balance_factor > 1 and score <= root.left.score:
          return self.right_rotate(root)

        # Case 2 - Right Right 
        if balance_factor < -1 and score >= root.right.score:
          return self.left_rotate(root)

        # Case 3 - Left Right 
        if balance_factor > 1 and score > root.left.score:
          root.left = self.left_rotate(root.left)
          return self.right_rotate(root)

        # Case 4 - Right Left 
        if balance_factor < -1 and score < root.right.score:
          root.right = self.right_rotate(root.right)
          return self.left_rotate(root)

        return root

    """Delete a node in our AVL tree."""
    def delete_player(self, root, player):
        score = player.score
        if not root:
            return root
        elif score < root.score:
            root.left = self.delete_player(root.left, player)
        elif score > root.score:
            root.right = self.delete_player(root.right, player)
        else:
            if root.left is None:
                temp = root.right
                root = None
                return temp
            elif root.right is None:
                temp = root.left
                root = None
                return temp
            temp = self.get_min_value_player(root.right)
            root.val = temp.player
            root.right = self.delete_player(root.right, temp.player)
        if root is None:
            return root

        root.height = 1 + max(self.get_height(root.left),
                              self.get_height(root.right))

        balance = self.get_balance(root)

        # If the deletion unbalanced the tree we have 
        # to rebalance by performing rotations
        if balance > 1 and self.get_balance(root.left) >= 0:
            return self.right_rotate(root)

        if balance < -1 and self.get_balance(root.right) <= 0:
            return self.left_rotate(root)

        if balance > 1 and self.get_balance(root.left) < 0:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        if balance < -1 and self.get_balance(root.right) > 0:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

    """Perform left rotation."""
    def left_rotate(self, player):
        right = player.right
        left = right.left
        right.left = player
        player.right = left

        player.height = 1 + max(self.get_height(player.left),
                                self.get_height(player.right))
        right.height = 1 + max(self.get_height(right.left),
                               self.get_height(right.right))
        return right

    """Perform right rotation."""
    def right_rotate(self, player):
        left = player.left
        right = left.right
        left.right = player
        player.left = right

        player.height = 1 + max(self.get_height(player.left),
                                self.get_height(player.right))
        left.height = 1 + max(self.get_height(left.left),
                              self.get_height(left.right))
        return left

    """Return the height of the tree."""
    def get_height(self, root):
        if not root:
            return 0

        return root.height

    """Return the balance factor of a node."""
    def get_balance(self, root):
        if not root:
            return 0

        return self.get_height(root.left) - self.get_height(root.right)

    """Return leftmost node which is the smallest value in the tree."""
    def get_min_value_player(self, root):
        if root is None or root.left is None:
            return root
        else:
          Get_min_value_player(root.left)

1. Propose a data structure to represent a Player and its Score

In [115]:
"""We create 100 impostors named from player_1 to player_100.
At the beginning they all have a mean score of 0 and they aren't impostor."""
players = []
for x in range(1, 101):
    player = {"name": "player_{}".format(x), "scores": [0], "impostor": False}
    players.append(player)

2. Propose a most optimized data structures for the tournament

(called database in the following questions)

In [ ]:
"""Create an AVL Tree and insert every player in it."""
tree = AVLTree()
root_tree = None
for player in players:
    root_tree = tree.insert_player(root_tree, Player(player))
root_tree.display()

3. Present and argue about a method that randomize player score at each game

(between 0 point to 12 points)

In [117]:
"""Randomize players score."""
def randomize_score(players):
  for player in players:
    # We add a random score to the list of scores
    player["scores"].append(random.randint(0,12))
    # We must then update the mean score of the player,
    # which is the first cell of the list
    player["scores"][0] = round(np.mean(player["scores"][1:]),2)
  return players

4. Present and argue about a method to update Players score and the database

In [ ]:
# We choose to traverse the Tree in-order so that we get
# all players in a ascending order (from worst to best).
players = []

"""In order traversing."""
def print_inorder(root):
    if root:
        print_inorder(root.left)
        # print(root.info)
        player = {"name": root.name,
                  "scores": root.scores,
                  "impostor": root.impostor}
        players.append(player)
        print_inorder(root.right)


print_inorder(root_tree)

# Once they played a game, we have to update their score
print(players)
players = randomize_score(players)
print(players)

# We can then re-insert them in the tournament.
tree = AVLTree()
root_tree = None
for player in players:
    root_tree = tree.insert_player(root_tree, Player(player))
root_tree.display()

5. Present and argue about a method to create random games based on the database

In [ ]:
# We create 10 AVL Trees (because there are still 100 players)
roots = []
for x in range(10):
  roots.append(None)

trees = []
for x in range(10):
    trees.append(AVLTree())

players = []
print_inorder(root_tree)

# The key of the dictionnary is the number of the tree.
# The value of each key is the number of player in this tree.
dictionary = {0: 0, 1: 0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0}

for i in range(len(players)):
  # We choose a random tree in which we place the player
  choice = random.choice(tuple((dictionary.keys())))
  # We increment the value of the associated key in the dictionnary
  dictionary[choice] += 1
  # If there are now 10 players in a game
  if dictionary[choice] == 10:
    # We remove this game from the choices
    dictionary.pop(choice)
  # We insert the player in this game
  roots[choice] = trees[choice].insert_player(roots[choice], Player(players[i]))

for i in range(10):
  roots[i].display()

6. Present and argue about a method to create games based on ranking

In [ ]:
players = []
print_inorder(root_tree)

# This time we create a number of games based on the number of remaining players.
roots = []
for x in range(int(len(players) / 10)):
  roots.append(None)

trees = []
for x in range(int(len(players) / 10)):
    trees.append(AVLTree())

count = 0
current = 0

# This time we want to put the best players together in order.
for i in range(len(players)):
  # When a game is full we go to the next game and continue
  if count == 10:
    count = 0
    current += 1
  roots[current] = trees[current].insert_player(roots[current], Player(players[i]))
  count += 1

for i in range(int(len(players) / 10)):
  roots[i].display()

7. Present and argue about a method to drop the players and to play game until the last 10 players

In [ ]:
"""You have to run this cell the number of times you want to drop 10 players.
For example if you want to remove 10 players just run it once. However if you 
want to remove all the players, you have to run this cell 9 times (to remove 
90 players). Don't be afraid of clicking fast, there is a security and you 
won't be able to remove all the players. It will stop when 10 players are 
remaining and you won't be able to remove more."""

players = []
print_inorder(root_tree)

if len(players) > 10:
  # We remove the 10 players with the worst score
  players = players[10:]

tree = AVLTree()
root_tree = None

for player in players:
    root_tree = tree.insert_player(root_tree, Player(player))
root_tree.display()

8. Present and argue about a method which display the TOP10 players and the podium after the final game.

In [122]:
players = []
print_inorder(root_tree)

for i in range(10):
  print(str(10-i) + " : " + players[i]["name"] + " with an average of " + str(players[i]["scores"][0]) + " points")
10 : player_40 with an average of 1.0 points
9 : player_54 with an average of 1.0 points
8 : player_56 with an average of 1.0 points
7 : player_78 with an average of 1.0 points
6 : player_85 with an average of 1.0 points
5 : player_91 with an average of 1.0 points
4 : player_6 with an average of 2.0 points
3 : player_39 with an average of 2.0 points
2 : player_46 with an average of 2.0 points
1 : player_76 with an average of 2.0 points

STEP 2

4. Implement the algorithm and show a solution.

In [124]:
"""To create the adjacency matrix, we create a square matrix of dimensions 
rooms x rooms (the number of rooms being 14 in our case). Then we put 0 in 
the diagonal. Now we look only at the upper side of the diagonal. If the 
intersection of the line and the column represents two rooms that are 
connected by a path, we put a 1. For example, if the room 1 and the room 3 
are connected, we put a "1" on the intersection of line 1 and column 3.
Otherwise, if there is no direct path, we put a 0. Then, because our graph 
is undirected (if someone can go from room A to room B then he can go from 
room B to room A), we make the matrix symetrical. For example, if we have 
a 1 on the intersection of line 1 and column 3, then we put a 1 on the 
intersection of line 3 and column 1."""

adjacency_matrix = [[0, 1, 0, 0, 1, 1, 0, 0, 0, 0],
                    [1, 0, 1, 0, 0, 0, 1, 0, 0, 0],
                    [0, 1, 0, 1, 0, 0, 0, 1, 0, 0],
                    [0, 0, 1, 0, 1, 0, 0, 1, 0, 0],
                    [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
                    [1, 0, 0, 0, 0, 0, 0, 1, 1, 0],
                    [0, 1, 0, 0, 0, 0, 0, 0, 1, 1],
                    [0, 0, 1, 0, 0, 1, 0, 0, 0, 1],
                    [0, 0, 0, 1, 0, 1, 1, 0, 0, 0],
                    [0, 0, 0, 0, 1, 0, 1, 1, 0, 0]]

impostor1 = [1, 4, 5]
# We will not visit player that we already
# know are possible impostor or dead player
neighborToVisit = [i for i in range(10) if i not in impostor1 and i != 0]
solution = []

# For every possible impostor
for impostor in impostor1:
  # We look at all players that are not dead nor a possible impostor
  for i in neighborToVisit:
    # If their path didn't cross
    if adjacency_matrix[i][impostor] == 0:
     # We add the tuple of the impostor and this 
     # player to the possible set of impostors.
      solution.append([impostor, i])

solution
Out[124]:
[[1, 3],
 [1, 7],
 [1, 8],
 [1, 9],
 [4, 2],
 [4, 6],
 [4, 7],
 [4, 8],
 [5, 2],
 [5, 3],
 [5, 6],
 [5, 9]]

STEP 3

2. Argue about a pathfinding algorithm to implement.

In [2]:
class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    """Just to print the matrix in a "nice way"."""
    def print_solution_floyd_warshall(self, distance):
        for i in range(self.vertices):
            for j in range(self.vertices):
                if distance[i][j] == 999:
                    print("! ", end=" ")
                else:
                    print(distance[i][j], end="  ")
            print(" ")

    """Print and return the matrix containing all the distance between rooms."""
    def floyd_warshall(self):
        distance = list(map(lambda i: list(map(lambda j: j, i)), self.graph))
        for k in range(self.vertices):
            for i in range(self.vertices):
                for j in range(self.vertices):
                    # We want to find the shortest path between room i 
                    # and room j (we round it so it's still readable)
                    distance[i][j] = round(min(distance[i][j],
                                               distance[i][k] + distance[k][j]),
                                           2)
        for i in range(self.vertices):
            for j in range(i, self.vertices):
                # If we find a shorter path than what we had
                if distance[i][j] < distance[j][i]:
                    # This becomes the shortest path
                    distance[j][i] = distance[i][j]
                else:
                    distance[i][j] = distance[j][i]
        self.print_solution_floyd_warshall(distance)
        return distance

3. Implement the method and show the time to travel for any pair of rooms for both models.

In [3]:
# Create the graph with 14 rooms.
g_crew = Graph(14)

# We use the adjacency matrix of the crewmates
g_crew.graph = [
    [0, 8.31, 8.31, 6.52, 999, 999, 999, 999, 999, 999, 999, 999, 999, 999],
    [8.31, 0, 9.54, 7.75, 9.7, 12.33, 999, 999, 999, 999, 999, 999, 999, 999],
    [8.31, 9.54, 0, 7.75, 999, 999, 11.77, 13.25, 999, 999, 999, 999, 999, 999],
    [6.52, 7.75, 7.75, 0, 999, 999, 999, 999, 999, 999, 999, 999, 999, 999],
    [999, 9.7, 999, 999, 0, 10.01, 999, 999, 999, 999, 999, 999, 999, 999],
    [999, 12.33, 999, 999, 10.01, 0, 999, 9.87, 999, 9.98, 999, 7.54, 999, 999],
    [999, 999, 11.77, 999, 999, 999, 0, 9.34, 999, 999, 999, 999, 999, 999],
    [999, 999, 13.25, 999, 999, 9.87, 9.34, 0, 8.21, 7.71, 999, 999, 999, 8.6],
    [999, 999, 999, 999, 999, 999, 999, 8.21, 0, 999, 999, 999, 999, 5.99],
    [999, 999, 999, 999, 999, 9.98, 999, 7.71, 999, 0, 999, 999, 999, 999],
    [999, 999, 999, 999, 999, 999, 999, 999, 999, 999, 0, 5.82, 9.36, 12.92],
    [999, 999, 999, 999, 999, 7.54, 999, 999, 999, 999, 5.82, 0, 10.16, 13.72],
    [999, 999, 999, 999, 999, 999, 999, 999, 999, 999, 9.36, 10.16, 0, 11.6],
    [999, 999, 999, 999, 999, 999, 999, 8.6, 5.99, 999, 12.92, 13.72, 11.6, 0]]

# Store the result for crewmates graph
distance_between_rooms_crewmates = g_crew.floyd_warshall()
0  8.31  8.31  6.52  18.01  20.64  20.08  21.56  29.77  29.27  34.0  28.18  38.34  30.16
8.31  0  9.54  7.75  9.7  12.33  21.31  22.2  30.41  22.31  25.69  19.87  30.03  30.8
8.31  9.54  0  7.75  19.24  21.87  11.77  13.25  21.46  20.96  34.77  29.41  33.45  21.85
6.52  7.75  7.75  0  17.45  20.08  19.52  21.0  29.21  28.71  33.44  27.62  37.78  29.6
18.01  9.7  19.24  17.45  0  10.01  29.22  19.88  28.09  19.99  23.37  17.55  27.71  28.48
20.64  12.33  21.87  20.08  10.01  0  19.21  9.87  18.08  9.98  13.36  7.54  17.7  18.47
20.08  21.31  11.77  19.52  29.22  19.21  0  9.34  17.55  17.05  30.86  26.75  29.54  17.94
21.56  22.2  13.25  21.0  19.88  9.87  9.34  0  8.21  7.71  21.52  17.41  20.2  8.6
29.77  30.41  21.46  29.21  28.09  18.08  17.55  8.21  0  15.92  18.91  19.71  17.59  5.99
29.27  22.31  20.96  28.71  19.99  9.98  17.05  7.71  15.92  0  23.34  17.52  27.68  16.31
34.0  25.69  34.77  33.44  23.37  13.36  30.86  21.52  18.91  23.34  0  5.82  9.36  12.92
28.18  19.87  29.41  27.62  17.55  7.54  26.75  17.41  19.71  17.52  5.82  0  10.16  13.72
38.34  30.03  33.45  37.78  27.71  17.7  29.54  20.2  17.59  27.68  9.36  10.16  0  11.6
30.16  30.8  21.85  29.6  28.48  18.47  17.94  8.6  5.99  16.31  12.92  13.72  11.6  0
In [7]:
# Create the graph with 14 rooms.
g_impostors = Graph(14)

# We use the adjacency matrix of the impostors.
g_impostors.graph = [
      [0, 1, 1, 6.52, 999, 999, 999, 999, 999, 999, 999, 999, 999, 999],
      [1, 0, 9.54, 7.75, 9.7, 12.33, 999, 999, 999, 999, 999, 999, 999, 999],
      [1, 9.54, 0, 7.75, 999, 999, 11.77, 13.25, 999, 999, 999, 999, 999, 999],
      [6.52, 7.75, 7.75, 0, 1, 999, 1, 999, 999, 999, 999, 999, 999, 999],
      [999, 9.7, 999, 1, 0, 10.01, 1, 999, 999, 999, 999, 999, 999, 999],
      [999, 12.33, 999, 999, 10.01, 0, 999, 9.87, 999, 1, 999, 7.54, 999, 1],
      [999, 999, 11.77, 1, 1, 999, 0, 9.34, 999, 999, 999, 999, 999, 999],
      [999, 999, 13.25, 999, 999, 9.87, 9.34, 0, 8.21, 7.71, 999, 999, 999, 8.6],
      [999, 999, 999, 999, 999, 999, 999, 8.21, 0, 999, 999, 999, 999, 5.99],
      [999, 999, 999, 999, 999, 1, 999, 7.71, 999, 0, 999, 999, 999, 1],
      [999, 999, 999, 999, 999, 999, 999, 999, 999, 999, 0, 5.82, 9.36, 12.92],
      [999, 999, 999, 999, 999, 7.54, 999, 999, 999, 999, 5.82, 0, 1, 13.72],
      [999, 999, 999, 999, 999, 999, 999, 999, 999, 999, 9.36, 1, 0, 1],
      [999, 999, 999, 999, 999, 1, 999, 8.6, 5.99, 1, 12.92, 13.72, 1, 0]]

# Store the result for impostors graph
distance_between_rooms_impostors = g_impostors.floyd_warshall()
0  1  1  6.52  7.52  13.33  7.52  14.25  20.32  14.33  22.15  16.33  15.33  14.33
1  0  2  7.52  8.52  12.33  8.52  15.25  19.32  13.33  21.15  15.33  14.33  13.33
1  2  0  7.52  8.52  14.33  8.52  13.25  21.32  15.33  23.15  17.33  16.33  15.33
6.52  7.52  7.52  0  1  11.01  1  10.34  18.0  12.01  19.83  14.01  13.01  12.01
7.52  8.52  8.52  1  0  10.01  1  10.34  17.0  11.01  18.83  13.01  12.01  11.01
13.33  12.33  14.33  11.01  10.01  0  11.01  8.71  6.99  1  8.82  3  2  1
7.52  8.52  8.52  1  1  11.01  0  9.34  17.55  12.01  19.83  14.01  13.01  12.01
14.25  15.25  13.25  10.34  10.34  8.71  9.34  0  8.21  7.71  16.42  10.6  9.6  8.6
20.32  19.32  21.32  18.0  17.0  6.99  17.55  8.21  0  6.99  13.81  7.99  6.99  5.99
14.33  13.33  15.33  12.01  11.01  1  12.01  7.71  6.99  0  8.82  3  2  1
22.15  21.15  23.15  19.83  18.83  8.82  19.83  16.42  13.81  8.82  0  5.82  6.82  7.82
16.33  15.33  17.33  14.01  13.01  3  14.01  10.6  7.99  3  5.82  0  1  2
15.33  14.33  16.33  13.01  12.01  2  13.01  9.6  6.99  2  6.82  1  0  1
14.33  13.33  15.33  12.01  11.01  1  12.01  8.6  5.99  1  7.82  2  1  0

Here we provide a user friendly method to know the distance between rooms in both case.

In [17]:
print("Please input the rooms you want to know the \
in between distance (an int between 0 and 13):")

# Inputs
while True:
  print("Room 1 =>")
  try:
    room_one = int(input())
    if room_one in range(14):
      break
    else:
      print("Value not in range(0,14). Try again.")
  except:
    print("Value not an int. Try again.")
while True:
  print("Room 2 =>")
  try:
    room_two = int(input())
    if room_two in range(14):
      break
    else:
      print("Value not in range(0,14). Try again.")
  except:
    print("Value not an int. Try again.")

print("Is it for crewmates (enter yes or anything else for no)?")
choice = input()

# For crewmates choice
validate = ["y", "ye", "yes", "Y", "Ye", "Yes", "YES", "YE",
            "o", "ou", "oui", "O", "Ou", "Oui", "OUI", "OU"]

# Print result
if choice in validate:  # Yes
  print("The distance between room {0} and {1} \
for crewmates is about {2}cm or about {2}s." \
  .format(room_one,
          room_two,
          distance_between_rooms_crewmates[room_one][room_two]))
else:
  print("The distance between room {0} and {1} \
for impostors is about {2}cm or about {2}s." \
  .format(room_one,
          room_two,
          distance_between_rooms_impostors[room_one][room_two]))
Please input the rooms you want to know the in between distance (an int between 0 and 13):
Room 1 =>
4
Room 2 =>
12
Is it for crewmates (enter yes or anything else for no)?
y
The distance between room 4 and 12 for crewmates is about 27.71cm or about 27.71s.

STEP 4

In [ ]:
# Install dependencies
! apt-get install -y graphviz-dev
! pip install pygraphviz
! pip install mpld3

4. Implement the algorithm and show a solution

In [21]:
import numpy as np
from math import inf

# For better graph plots
import matplotlib.pyplot as plt
import networkx as nx
from networkx.drawing.nx_agraph import graphviz_layout


class Graph:
    """We init the adjacency with inf value and then 
    values in the matrix with the add_edge function."""
    def __init__(self, nb_node=0):
        self.adjacency_matrix = np.ones((nb_node, nb_node)) * inf
        self.label = [""] * nb_node

    """Modify the adjacency matrix with the input nodes and weight"""
    def add_edge(self, node_one, node_two, weight=1.0):
        self.adjacency_matrix[node_one, node_two] = weight
        self.adjacency_matrix[node_two, node_one] = weight

    """Return the list of available neighbors of 
    one node to construct the hamiltonian path"""
    def get_neighbors(self, node):
        neighbors = []
        for i in range(self.nb_node):
            if i != node and self.adjacency_matrix[i, node] != inf:
                neighbors.append(i)
        return neighbors

    """Return all the hamilton paths from all vertices 
    sorted with respect to the travelled distance."""
    def get_all_hamilton_paths(self):
        all_path = []
        for i in range(self.nb_node):
            graph.get_hamilton_paths([i], all_path)
        return sorted(all_path, key=lambda x: x[1])

    """Return all the hamilton paths from one vertex."""
    def get_hamilton_paths(self, path, all_path):
        # The path isn't valid, we have two times the same node in the path
        if path.count(path[-1]) > 1:
            return None
        # The path is valid, thus added to all paths
        if len(path) == self.nb_node:
            # Compute the score of the path
            travelled_distance = 0
            for i in range(len(path) - 1):
                travelled_distance += self.adjacency_matrix[path[i]][path[i + 1]]
            all_path.append([path, travelled_distance])
            return None
        neighbors = self.get_neighbors(path[-1])
        for n in neighbors:
            new_path = path + [n]
            self.get_hamilton_paths(new_path, all_path)

    def __getattr__(self, key):
        if key == "nb_node":
            return self.adjacency_matrix.shape[0]

    """Plot the graph thanks to the adjacency matrix. Encoded here for 
    more visibility but can easily be retrieved from class graph 
    (just need to replace inf by zeros)"""
    def plot(self):
        matrix = [[0, 12.33, 9.7, 0, 0, 0, 0, 0, 0, 0, 0, 9.54, 8.31, 7.75],
                  [0, 0, 10.01, 7.54, 0, 0, 0, 0, 9.87, 9.98, 0, 0, 0, 0],
                  [9.7, 10.01, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                  [0, 7.54, 0, 0, 5.82, 10.16, 13.72, 0, 0, 0, 0, 0, 0, 0],
                  [0, 0, 0, 5.82, 0, 9.36, 12.92, 0, 0, 0, 0, 0, 0, 0],
                  [0, 0, 0, 10.16, 9.36, 0, 11.6, 0, 0, 0, 0, 0, 0, 0],
                  [0, 0, 0, 13.72, 12.92, 11.6, 0, 5.99, 8.6, 0, 0, 0, 0, 0],
                  [0, 0, 0, 0, 0, 0, 5.99, 0, 8.21, 0, 0, 0, 0, 0],
                  [0, 9.87, 0, 0, 0, 0, 8.6, 8.21, 0, 7.71, 9.34, 13.25, 0, 0],
                  [0, 9.98, 0, 0, 0, 0, 0, 0, 7.71, 0, 0, 0, 0, 0],
                  [0, 0, 0, 0, 0, 0, 0, 0, 9.34, 0, 0, 11.77, 0, 0],
                  [9.54, 0, 0, 0, 0, 0, 0, 0, 13.25, 0, 11.77, 0, 8.31, 7.75],
                  [8.31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8.31, 0, 6.52],
                  [7.75, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7.75, 6.52, 0]]

        # Create networks graph using the adjacency matrix
        G = nx.from_numpy_matrix(np.matrix(matrix))

        # Retrieve coordinates
        pos = graphviz_layout(G, prog='sfdp')

        # Rescale plot
        plt.figure(1, figsize=(12, 8))

        # Plot
        nx.draw_networkx(G, pos, font_weight='bold',
                         with_labels=False, width=2)

        # Add Vertex Label
        nx.draw_networkx_labels(G, pos, {0: '1', 1: '5', 2: '4', 3: '11',
                                         4: '10', 5: '12', 6: '13', 7: '8',
                                         8: '7', 9: '9', 10: '6', 11: '2',
                                         12: '0', 13: '3'})

        # Add Edge Label
        labels = nx.get_edge_attributes(G, 'weight')
        nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)

        # Save snapshot
        plt.savefig("graph.pdf")

graph = Graph(14)
graph.add_edge(0, 1, 8.31)
graph.add_edge(0, 2, 8.31)
graph.add_edge(0, 3, 6.52)
graph.add_edge(1, 2, 9.54)
graph.add_edge(1, 3, 7.75)
graph.add_edge(1, 4, 9.7)
graph.add_edge(1, 5, 12.33)
graph.add_edge(2, 3, 7.75)
graph.add_edge(2, 6, 11.77)
graph.add_edge(2, 7, 13.25)
graph.add_edge(4, 5, 10.01)
graph.add_edge(5, 7, 9.87)
graph.add_edge(5, 9, 9.98)
graph.add_edge(5, 11, 7.54)
graph.add_edge(6, 7, 9.34)
graph.add_edge(7, 8, 8.21)
graph.add_edge(7, 9, 7.71)
graph.add_edge(7, 13, 8.6)
graph.add_edge(8, 13, 5.99)
graph.add_edge(10, 11, 5.82)
graph.add_edge(10, 12, 9.36)
graph.add_edge(10, 13, 12.92)
graph.add_edge(11, 13, 13.72)
graph.add_edge(11, 12, 10.16)
graph.add_edge(12, 13, 11.6)

# Plot
graph.plot()
In [14]:
# For all hamiltonian paths in the graph sorted
# in function of the travelled distance
graph.get_all_hamilton_paths()
Out[14]:
[[[6, 2, 0, 3, 1, 4, 5, 11, 10, 12, 13, 8, 7, 9], 110.28999999999998],
 [[6, 2, 3, 0, 1, 4, 5, 11, 10, 12, 13, 8, 7, 9], 110.28999999999998],
 [[9, 7, 8, 13, 12, 10, 11, 5, 4, 1, 0, 3, 2, 6], 110.29],
 [[9, 7, 8, 13, 12, 10, 11, 5, 4, 1, 3, 0, 2, 6], 110.29],
 [[4, 1, 0, 3, 2, 6, 7, 9, 5, 11, 10, 12, 13, 8], 111.38999999999999],
 [[4, 1, 3, 0, 2, 6, 7, 9, 5, 11, 10, 12, 13, 8], 111.38999999999999],
 [[8, 13, 12, 10, 11, 5, 9, 7, 6, 2, 0, 3, 1, 4], 111.38999999999999],
 [[8, 13, 12, 10, 11, 5, 9, 7, 6, 2, 3, 0, 1, 4], 111.38999999999999],
 [[8, 13, 12, 10, 11, 5, 4, 1, 0, 3, 2, 6, 7, 9], 111.41999999999999],
 [[8, 13, 12, 10, 11, 5, 4, 1, 3, 0, 2, 6, 7, 9], 111.41999999999999],
 [[9, 7, 6, 2, 0, 3, 1, 4, 5, 11, 10, 12, 13, 8], 111.42000000000002],
 [[9, 7, 6, 2, 3, 0, 1, 4, 5, 11, 10, 12, 13, 8], 111.42000000000002],
 [[9, 5, 11, 10, 12, 13, 8, 7, 6, 2, 0, 3, 1, 4], 111.89],
 [[9, 5, 11, 10, 12, 13, 8, 7, 6, 2, 3, 0, 1, 4], 111.89],
 [[4, 1, 0, 3, 2, 6, 7, 8, 13, 12, 10, 11, 5, 9], 111.89000000000001],
 [[4, 1, 3, 0, 2, 6, 7, 8, 13, 12, 10, 11, 5, 9], 111.89000000000001],
 [[6, 2, 0, 3, 1, 4, 5, 9, 7, 8, 13, 12, 10, 11], 112.72999999999996],
 [[6, 2, 3, 0, 1, 4, 5, 9, 7, 8, 13, 12, 10, 11], 112.72999999999996],
 [[11, 10, 12, 13, 8, 7, 9, 5, 4, 1, 0, 3, 2, 6], 112.73],
 [[11, 10, 12, 13, 8, 7, 9, 5, 4, 1, 3, 0, 2, 6], 112.73],
 [[6, 2, 0, 3, 1, 4, 5, 9, 7, 8, 13, 12, 11, 10], 113.52999999999997],
 [[6, 2, 3, 0, 1, 4, 5, 9, 7, 8, 13, 12, 11, 10], 113.52999999999997],
 [[10, 11, 12, 13, 8, 7, 9, 5, 4, 1, 0, 3, 2, 6], 113.53],
 [[10, 11, 12, 13, 8, 7, 9, 5, 4, 1, 3, 0, 2, 6], 113.53],
 [[9, 5, 4, 1, 0, 3, 2, 6, 7, 8, 13, 12, 10, 11], 114.35999999999999],
 [[9, 5, 4, 1, 3, 0, 2, 6, 7, 8, 13, 12, 10, 11], 114.35999999999999],
 [[11, 10, 12, 13, 8, 7, 6, 2, 0, 3, 1, 4, 5, 9], 114.36000000000001],
 [[11, 10, 12, 13, 8, 7, 6, 2, 3, 0, 1, 4, 5, 9], 114.36000000000001],
 [[6, 2, 0, 3, 1, 4, 5, 9, 7, 8, 13, 10, 11, 12], 114.84999999999997],
 [[6, 2, 3, 0, 1, 4, 5, 9, 7, 8, 13, 10, 11, 12], 114.84999999999997],
 [[6, 2, 0, 3, 1, 4, 5, 9, 7, 8, 13, 11, 10, 12], 114.84999999999998],
 [[6, 2, 3, 0, 1, 4, 5, 9, 7, 8, 13, 11, 10, 12], 114.84999999999998],
 [[12, 10, 11, 13, 8, 7, 9, 5, 4, 1, 0, 3, 2, 6], 114.85000000000001],
 [[12, 10, 11, 13, 8, 7, 9, 5, 4, 1, 3, 0, 2, 6], 114.85000000000001],
 [[12, 11, 10, 13, 8, 7, 9, 5, 4, 1, 0, 3, 2, 6], 114.85000000000001],
 [[12, 11, 10, 13, 8, 7, 9, 5, 4, 1, 3, 0, 2, 6], 114.85000000000001],
 [[9, 5, 4, 1, 0, 3, 2, 6, 7, 8, 13, 12, 11, 10], 115.16],
 [[9, 5, 4, 1, 3, 0, 2, 6, 7, 8, 13, 12, 11, 10], 115.16],
 [[10, 11, 12, 13, 8, 7, 6, 2, 0, 3, 1, 4, 5, 9], 115.16000000000001],
 [[10, 11, 12, 13, 8, 7, 6, 2, 3, 0, 1, 4, 5, 9], 115.16000000000001],
 [[6, 2, 0, 3, 1, 4, 5, 11, 12, 10, 13, 8, 7, 9], 115.94999999999997],
 [[6, 2, 3, 0, 1, 4, 5, 11, 12, 10, 13, 8, 7, 9], 115.94999999999997],
 [[9, 7, 8, 13, 10, 12, 11, 5, 4, 1, 0, 3, 2, 6], 115.95],
 [[9, 7, 8, 13, 10, 12, 11, 5, 4, 1, 3, 0, 2, 6], 115.95],
 [[9, 5, 4, 1, 0, 3, 2, 6, 7, 8, 13, 10, 11, 12], 116.47999999999999],
 [[9, 5, 4, 1, 3, 0, 2, 6, 7, 8, 13, 10, 11, 12], 116.47999999999999],
 [[9, 5, 4, 1, 0, 3, 2, 6, 7, 8, 13, 11, 10, 12], 116.48],
 [[9, 5, 4, 1, 3, 0, 2, 6, 7, 8, 13, 11, 10, 12], 116.48],
 [[12, 10, 11, 13, 8, 7, 6, 2, 0, 3, 1, 4, 5, 9], 116.48],
 [[12, 10, 11, 13, 8, 7, 6, 2, 3, 0, 1, 4, 5, 9], 116.48],
 [[12, 11, 10, 13, 8, 7, 6, 2, 0, 3, 1, 4, 5, 9], 116.48],
 [[12, 11, 10, 13, 8, 7, 6, 2, 3, 0, 1, 4, 5, 9], 116.48],
 [[4, 1, 0, 3, 2, 6, 7, 9, 5, 11, 12, 10, 13, 8], 117.05],
 [[4, 1, 3, 0, 2, 6, 7, 9, 5, 11, 12, 10, 13, 8], 117.05],
 [[8, 13, 10, 12, 11, 5, 9, 7, 6, 2, 0, 3, 1, 4], 117.05],
 [[8, 13, 10, 12, 11, 5, 9, 7, 6, 2, 3, 0, 1, 4], 117.05],
 [[8, 13, 10, 12, 11, 5, 4, 1, 0, 3, 2, 6, 7, 9], 117.07999999999998],
 [[8, 13, 10, 12, 11, 5, 4, 1, 3, 0, 2, 6, 7, 9], 117.07999999999998],
 [[9, 7, 6, 2, 0, 3, 1, 4, 5, 11, 12, 10, 13, 8], 117.08000000000001],
 [[9, 7, 6, 2, 3, 0, 1, 4, 5, 11, 12, 10, 13, 8], 117.08000000000001],
 [[9, 5, 11, 12, 10, 13, 8, 7, 6, 2, 0, 3, 1, 4], 117.55],
 [[9, 5, 11, 12, 10, 13, 8, 7, 6, 2, 3, 0, 1, 4], 117.55],
 [[4, 1, 0, 3, 2, 6, 7, 8, 13, 10, 12, 11, 5, 9], 117.55000000000001],
 [[4, 1, 3, 0, 2, 6, 7, 8, 13, 10, 12, 11, 5, 9], 117.55000000000001],
 [[6, 2, 0, 3, 1, 4, 5, 9, 7, 8, 13, 10, 12, 11], 118.38999999999997],
 [[6, 2, 3, 0, 1, 4, 5, 9, 7, 8, 13, 10, 12, 11], 118.38999999999997],
 [[11, 12, 10, 13, 8, 7, 9, 5, 4, 1, 0, 3, 2, 6], 118.39],
 [[11, 12, 10, 13, 8, 7, 9, 5, 4, 1, 3, 0, 2, 6], 118.39],
 [[6, 2, 0, 3, 1, 4, 5, 9, 7, 8, 13, 11, 12, 10], 119.18999999999997],
 [[6, 2, 3, 0, 1, 4, 5, 9, 7, 8, 13, 11, 12, 10], 119.18999999999997],
 [[10, 12, 11, 13, 8, 7, 9, 5, 4, 1, 0, 3, 2, 6], 119.19000000000001],
 [[10, 12, 11, 13, 8, 7, 9, 5, 4, 1, 3, 0, 2, 6], 119.19000000000001],
 [[9, 5, 4, 1, 0, 3, 2, 6, 7, 8, 13, 10, 12, 11], 120.02],
 [[9, 5, 4, 1, 3, 0, 2, 6, 7, 8, 13, 10, 12, 11], 120.02],
 [[11, 12, 10, 13, 8, 7, 6, 2, 0, 3, 1, 4, 5, 9], 120.02000000000001],
 [[11, 12, 10, 13, 8, 7, 6, 2, 3, 0, 1, 4, 5, 9], 120.02000000000001],
 [[9, 5, 4, 1, 0, 3, 2, 6, 7, 8, 13, 11, 12, 10], 120.82],
 [[9, 5, 4, 1, 3, 0, 2, 6, 7, 8, 13, 11, 12, 10], 120.82],
 [[10, 12, 11, 13, 8, 7, 6, 2, 0, 3, 1, 4, 5, 9], 120.82000000000001],
 [[10, 12, 11, 13, 8, 7, 6, 2, 3, 0, 1, 4, 5, 9], 120.82000000000001]]
In [22]:
# For all hamiltonian paths from one vertex
all_path = []
graph.get_hamilton_paths([7], all_path) # here you choose the node '4'
for path in all_path:
  print(path)
In [2]:
! jupyter nbconvert --to html "LEBLANC_&_ADJARIAN_Among_Us.ipynb"
[NbConvertApp] Converting notebook LEBLANC_&_ADJARIAN_Among_Us.ipynb to html
[NbConvertApp] Writing 505257 bytes to LEBLANC_&_ADJARIAN_Among_Us.html
Join Newsletter
Get the latest news right in your inbox. I never spam!
Stéphan
Written by Stéphan
Computer science student in Paris.