Detecting Faction in Friend-Foe Networks

Description

Friend-Foe networks are weighted undirected graphs, which describe the friend-foe relations between people, countries or other entities.

An edge between two nodes, such as two people, implies that they know each other. The weight of the edge makes a statement about what the relation between the two nodes is. A weight of 1 indicates friendship, trust or an alliance, while a weight of -1 indicates the opposite, for example hatred, mistrust or rivalry.

Enmitiy between communities is an old phenomena. In today's world we can observe these rivalries between communities of different games, operating systems or programming languages. People, who belong to the same communities are usually friends, while members of different rivaling communities are rivals or enemies most of the time.

For this task, we want to look at networks of gamers. Especially we want to look at networks of gamers, which play either "League of Legends" or "Dota 2". In these networks, gamers are represented as nodes and edges describe friend- or foeship between gamers. We also have two factions: "League of Legends" and "Dota 2".

Assumptions

We make the following assumptions about our network:

• Playing "League of Legends" or "Dota 2" is mutually exclusive. A gamer can always only be part of one gaming community (faction).
• Two gamers, who play the same game and know each other, have to be friends.
• Two gamers, who play different games and know each other, have to be enemies.
• Every gamer plays one of the games. There is no gamer who does not belong to one of the games.
• We always know that the gamer identified with index 0 plays "League of Legends".

Problem Statement

Task

Implement the function detect_factions(network). This function is given a friend-foe network and has to return a list, which assigns each gamer one of the two games.

Input

The function detect_factions(network) receives a friend-foe network network as input.

Friend-Foe networks are generally weighted, undirected graphs. Additionally all given graphs will be connected.

A graphs is represented as adjacency matrix network with dimensions N*N, where N is the number of nodes in the network. The cell network[i][j] represent the edge between node i and node j. If the cell equals 0 no edge exists, if the cell equals 1 a friendship edge exist, and if the cell equals -1 a foeship edge exists. Because the network is undirected, the adjacency matrix is symmetric, therefore network[i][j] = network[j][i] applies.

Node 0 always belongs to "League of Legends".

Output

The function detect_factions(network) should output a list of length N, where N is the number of nodes in the network. The indexes of the list correspond to the indexes of the network. At each position either the string "League of Legends" or "Dota 2" can be found. If gamer i play "Dota 2", then the list should have the value "Dota 2" at index i.

Hints

• A graph traversal algorithm, such as breadth-first search or depth-first search, is useful.
• This problem is a graph coloring problem with 2 colors.

This is my first Kata, so any comments would be appreciated.