Soccer and Graphs in C#

Soccer and Graphs in C#

Written by Amir on May 15th, 2021 ・ Views ・ Report Post

Amir Visit User Profile

Introdcution

In this post I will explain how to build an unordered graph in C# and how to find the minimum relation level between any 2 nodes in the graph

There are 3 ways to represent a graph:

  • Adjacency list
  • Adjacency matrix
  • Incidence matrix

In my implementations I will use Adjacency list representation.

( If you wish to read about the differences go ahead and check this link: Comparison between Adjacency List and Adjacency Matrix representation of Graph )

Also, all code was written using Visual studio 2019 and .Net Core 5.0 console application. you can check the code here

But first, Terminology:

  • Graph - a non-linear data structure consisting of vertices (nodes) and edges
  • Vertices - the nodes in the graph
  • Edges - the arcs (or lines) between any 2 vertices
  • Adjacency list - in this representation each vertex (node) has a list of adjacent vertices
  • n-level relation - when you can reach from node A to B in n steps (an edge is 1-level relation)

Soccer and friends

Let's start by building a graph. But let's make it a little bit more interesting than just your regular A-B-C-D-E-F graph.

Let's build a graph of famous soccer players. each player has a name, place of birth and current team. we define that 2 players are "colleagues" if the play on the same team and\or they were born in the same country

Take a look at the following graph:

Soccer players graph

🤩 Our Amazing Sponsors 👇
DigitalOcean View Website
DigitalOcean offers a simple and reliable cloud hosting solution that enables developers to get their website or application up and running quickly.
Laravel News View Website
Laravel News keeps you up to date with everything Laravel. Everything from framework news to new community packages, Laravel tutorials, and more.
Genesis View Website
A Laravel Starter Kit that includes Authentication, User Dashboard, Edit Profile, and a set of UI Components.

In this example, you can see that Lionel Messi and Angel Di maria are colleagues since they are both from Argentina and that Angel Di maria and Ryan Giggs are also colleagues since they both play on the same team

(disclaimer: yes I know that the data may be incorrect. it's just an example!)

Build the graph

Great! now that we know what are the relations between every 2 nodes in the graph we can finally start to build it.

First define a Player class

public class Player
{
	public string FullName { get; set; }
	public string Country { get; set; }
	public string Team { get; set; }

	public Player(string fullName, string country, string team)
	{
		this.FullName = fullName;
		this.Country = country;
		this.Team = team;
	}

	public bool IsColleague(Player other)
	{
		return 	this.Country == other.Country || 
				this.Team == other.Team;
	}

	public override string ToString()
	{
		return $"{this.FullName} is from {this.Country} and playing for {this.Team}";
	}
}

Now, lets define the graph class itself


public class SoccerPlayersGraph<T> where T : Player
{
	// A graph class represented by an adjacency list
	// Each key is a vertex(node)
	// Each value is a set of neighbor vertices (nodes)
	public readonly Dictionary<T, HashSet<T>> AdjacencyList = new();

	public SoccerPlayersGraph(List<T> soccerPlayers)
	{
		// Create a list of tuples for each 2 colleagues players
		var relatedPersons = CreateColleaguesList(soccerPlayers);

		// Add each player into the graph as a vertex
		soccerPlayers.ForEach(AddVertex);

		// Add each colleagues tuple in the graph as an edge
		relatedPersons.ForEach(AddEdge);
	}

	private List<Tuple<T, T>> CreateColleaguesList(List<T> players)
	{
		var edges = new List<Tuple<T, T>>();

		for (var i = 0; i < players.Count; i++)
		{
			var player1 = players[i];

			for (var j = 0; j < players.Count; j++)
			{
				if (i == j)
				{
					// skip self in order not to create self loops
					continue;
				}

				var player2 = players[j];

				if (player1.IsColleague(player2))
				{
					edges.Add(Tuple.Create(player1, player2));
				}
			}
		}

		return edges;
	}

	private void AddVertex(T vertex)
	{
		if (!this.AdjacencyList.ContainsKey(vertex))
		{
			this.AdjacencyList.Add(vertex, new HashSet<T>());
		}
	}

	private void AddEdge(Tuple<T, T> edge)
	{
		// An edge is is a tuple with 2 vertex : <v,u>
		var (u, v) = edge;

		// Add the "right" side of the edge to it's neighbors set
		if (this.AdjacencyList.ContainsKey(u) && !this.AdjacencyList[u].Contains(v))
		{
			this.AdjacencyList[u].Add(v);
		}
	}
}

  • The graph class has an AdjacencyList which is a dictionary that hold as a key the "player" object and the value is a set of all adjacent vertices (it's "neighbors")

  • In the constructor we receive a list of players and we perform 3 operations:

  1. CreateColleaguesList() - for each player we go over all other players and decide if they are "colleagues" . if so we create a tuple from both. the function will return a list of tuples that represent all colleagues players
  2. AddVertex() - for each player we create a vertex , i.e. we create a new key in the AdjacencyList dictionary.
  3. AddEdge() - for each (u,v) tuple we create an edge, i.e. we add v to the set of u in the AdjacencyList dictionary.

And there you go! we are now the proud owners of our own soccer players graph where each edge represents a colleague relation.

Find the Minimum relation level between 2 nodes

Now for the fun part. We want to write a function that will take any 2 nodes and will return what is the minimum relation level between them, or in other word how many edges you need to cross in order to reach from one to another

In order to do so we need to use the Breadth-first search algorithm.

The basic idea is to start with some vertex and explore all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Also, for each node we visit for the first time we save from which node we came (i.e. the first "ancestor" of it). this will give us a way, in case we found the target node, to traverse back for it all the way back to the source node in the **shorts path available" .

Let's look at the code:

public class SoccerPlayersUtil
{
	public SoccerPlayersGraph<Player> SoccerPlayersGraph;

	public void Init(List<Player> players)
	{
		this.SoccerPlayersGraph = new SoccerPlayersGraph<Player>(players);
	}

	public int FindMinRelationLevel(Player player1, Player player2)
	{
		if (player1 == null | player2 == null)
		{
			return -1;
		}

		if (player1.Equals(player2))
		{
			return 0;
		}

		// A dictionary that store for each node we gonna visit from what node we came from
		// Since this method using a BFS algorithm this promise us that for each key
		// we always save the closest node that is in the shortest path
		var prevPlayerNodeDictionary = new Dictionary<Player, Player>();

		// Helper queue to traverse all node in the graph
		var playersQueue = new Queue<Player>();

		playersQueue.Enqueue(player1);

		while (playersQueue.Count > 0)
		{
			var currentNode = playersQueue.Dequeue();

			if (!this.SoccerPlayersGraph.AdjacencyList.ContainsKey(currentNode))
			{
				continue;
			}

			foreach (var neighbor in this.SoccerPlayersGraph.AdjacencyList[currentNode])
			{
				if (!prevPlayerNodeDictionary.ContainsKey(neighbor))
				{
					// Save the neighbor node as the key, and the current node as the value
					prevPlayerNodeDictionary.Add(neighbor, currentNode);

					// If neighbor node is equal to player2 we can calc the relation level and return
					if (neighbor.Equals(player2))
					{
						return CalcRelationLevel(prevPlayerNodeDictionary, player2, player1);
					}

					// Enqueue the neighbor node so we cant traverse it later
					playersQueue.Enqueue(neighbor);
				}
			}

		}

		// If we reached this code that means that player2 was not found
		// ==> hence no connection at all between player1 and player2
		return -1;
	}

	private int CalcRelationLevel(
		IReadOnlyDictionary<Player, Player> prevPlayerNodeDictionary, Player targetPlayer, Player sourcePlayer)
	{
		int counter = 0;
		var currentPlayer = targetPlayer;

		while (!currentPlayer.Equals(sourcePlayer))
		{
			currentPlayer = prevPlayerNodeDictionary[currentPlayer];
			counter++;
		}

		return counter;
	}
}

We define a util class for this functionality.

*Init() function receive a list of players and return a graph (like we explained before)

  • FindMinRelationLevel() - first we init a new prevPlayerNodeDictionary dictionary. then we use a Queue in order and traverse all nodes in the graph. while the queue is not empty we:
  1. pop the next player in the queue
  2. Go over all it's neighbors and:
    • save for the neighbor node the current node as it's prevouse
    • check if the neighbor is the target player , and if so call ```CalcRelationLevel`` and return the result
    • else, Enqueue the neighbor node
  • CalcRelationLevel - traverse the "prevPlayerNodeDictionary" starting for the target player until we reach the source player and count the number of steps it took. this will tell us what is the minimal relation level between them

Conclusion

in this article I've showed how to build a graph in C# with Adjacency list representation based on some relation between the vertices.

I've also showed how to calculate the minimum relation level between any 2 nodes using BFS algorithm.

If you have any question , or some suggestions , or just want to tell me I'm awesome feel free to contact me using any one of the ways in the Contact page

Comments (0)