Develop equivalence relations among pairs of strings-CodePudding

I have a set of <string, string> pairs which represents equivalency among them: [(“Player1”, “Player2”), (“Player3”, “Player4”), (“Player2”, “Player3”), (“Player11”, “Player13”)]

This means, “Player1” is equivalent to “Player2” and “Player3” is equivalent to “Player4” and so on. Basically all players with relations belong to a same team.

Then I have Scores also in a set as <string, int> pairs. [(“Player1”, 50), (“Player3”, 25)]

I want to find out he total score of Player1's team. (which would be 75 in this case)

My idea is to develop a bidirectional graph relation among pairs from the equivalency pairs like: Player1<--->Player2<--->Player3<--->Player4 and mark them under a similar id or enum

So that when I want to get the total score of Player1's team, I can get the scores of other players related to Player1 and sum them up.

Below is the interface design I can imagine:

void buildRelations(vector<pair<string, string>> equivalances) {
// make some data scructure to store the relations:
// Player1<--->Player2<--->Player3<--->Player4 (team1)
// Player11<--->Player13 (team2)
}

int getTotalTeamScore(string player) {
// If Player1 is passed, the return should be 50   25 as Player 3 belongs to Playes1's team
}

I found related articles, which seems interesting but can't fire out how I design the data structure to store the relations and search related players to sum their scores. [1] Enumerating equivalence classes [2] DFS implementation in c using adjacency list (using <vector> and linked list)

It would be great if someone can help me to understand and develop the data structure.

CodePudding user response：

There is no need to bother with a graph. A map will do the job

Declare a structure for the players.

struct sPlayer 
{
    string name;
    int score;
    vector< string > eqivalency;
};

Declare a map for the relationships

 map< string, sPlayer > mpPlayer;

Now write code to implement:

- read the scores, inserting the player name and score into the map
- read the equivalencies, updating the map with the equivalencies
- input a player
- look up the player in the map
- LOOP over the player's equivalencies
   - Sum the scores of the equivalent players
- Add player score to sum