A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. Graphs are used to solve many real-life problems such as representing networks - like paths in a city or telephone network or circuit network. Graphs are also used in social networks like Linkedin and Facebook.
There are many times that I've come across problems in the IT industry that graphs could help solve. To demonstrate the use of graphs to process connections between items, we'll use Exchange server mailboxes as nodes and the permissions between them as edges.
The mailboxes variable shown below is loaded with mailbox info for five users. The majority of the objects' properties have been removed to simplify the demo:
We'll start with importing the DataStructures module that contains the Graph type and then create a graph object:
There are no nodes in the graph so it is empty.
The first thing to do now is to add the nodes. We'll loop through the mailboxes array and create nodes that will only contain the email address of the mailbox. Any type of object can be configured as a node, we'll keep it simple by adding the email string only:
The graph now contains a node for each mailbox.
A visual representation of the graph at this point would be the following:
Now it's time to add the permissions to the graph. Since permissions are one-way, we'll use directed edges:
With the edges added, the graph is now:
Now to the interesting stuff. Having all the information about mailboxes and permissions organized allows us to use algorithms to extract information from the entire graph.
Take the migration of the mailboxes from one Exchange organization to another for example. As a best practice, mailboxes that are associated with some kind of permission delegation are moved in the same batch to minimize any impact on the users' experience.
To identify the groups of mailboxes that are part of permission delegations is to identify the strongly connected sub-graphs of the graph.
The FindDisconnectedSubGraphs method returns a collection of graph objects that are not connected:
Two sub-graphs have been identified, as you can easily tell from the above diagram! The first graph contains the nodes User1, User2 and User3, and the second User4 and User5.
Another useful set of methods of the graph object is IsConnected and IsRecursivelyConnected. Those methods return a boolean result based on whether two nodes are connected or not. It requires three arguments to be provided, the two nodes and a boolean value on whether to check direction or not. Let's see some examples based on the graph we've created.
User1 is connected to User2 whether we are considering the direction of the edges or not - keep in mind that we've used directed edges! When checking if User2 is connected to User1, we get a positive output only when ignoring edge direction:
The IsRecursivelyConnected method can be invoked in the same way and it will check the connection between two nodes through the rest of the nodes of the graph by finding a path.
You can find more information on graphs
here.
I will soon be adding more methods to solve problems such as the shortest path and minimum spanning tree. The module is available on
Powershell Gallery as always. Happy coding!
