```
# install Chocolatey
[System.Net.ServicePointManager]::SecurityProtocol = [System.Net.ServicePointManager]::SecurityProtocol -bor
[System.Net.SecurityProtocolType]::Tls12
Invoke-RestMethod -UseBasicParsing -Uri 'https://chocolatey.org/install.ps1' | Invoke-Expression
# use chocolatey to install graphviz
cinst graphviz -
# install PSgraph
Install-Module PSGraph
```

```
Import-Module PSGraph
function Show-PSGraph ([ValidateSet('dot', 'circular', 'Hierarchical', 'Radial', 'fdp', 'neato', 'sfdp', 'SpringModelLarge', 'SpringModelSmall', 'SpringModelMedium', 'twopi')]$LayoutEngine = 'circular') {
$all = @($Input)
$tempPath = [System.IO.Path]::GetTempFileName()
$all | Out-File $tempPath
$new = Get-Content $tempPath -raw | ForEach-Object { $_ -replace "`r", "" }
$new | Set-Content -NoNewline $tempPath
Export-PSGraph -Source $tempPath -ShowGraph -LayoutEngine $LayoutEngine
Invoke-Item ($tempPath + '.png')
Remove-Item $tempPath
}
```

```
function New-Edge ($From, $To, $Attributes, [switch]$AsObject) {
$null = $PSBoundParameters.Remove('AsObject')
$ht = [Hashtable]$PSBoundParameters
if ($AsObject) {
return [PSCustomObject]$ht
}
return $ht
}
function New-Node ($Name, $Attributes) {
[Hashtable]$PSBoundParameters
}
function Get-GraphVisual ($Name, $Nodes, $Edges, [switch]$Undirected) {
$sb = {
if ($Undirected) { inline 'edge [arrowsize=0]' }
foreach ($node in $Nodes) {
node @node
}
foreach ($edge in $Edges) {
edge @edge
}
}
graph $sb
}
```

```
$edges = & {
New-Edge Alice Bob
New-Edge Alice Chuck
New-Edge Bob Alice
New-Edge Bob Chuck
}
Get-GraphVisual Friends -Edges $edges | Show-PSGraph
```

```
$nodes = & {
New-Node Albany @{ pos = '-74,43!' }
New-Node Boston @{ pos = '-71,42!' }
New-Node NYC @{ pos = '-74,41!' }
New-Node Philly @{ pos = '-75,40!' }
}
$edges = & {
New-Edge Albany Boston @{label = 3 }
New-Edge Albany NYC @{label = 4 }
New-Edge Boston NYC @{label = 4 }
New-Edge NYC Philly @{label = 2 }
}
Get-GraphVisual Cities $nodes $edges -Undirected | Show-PSGraph -LayoutEngine neato
```

```
function Get-CompleteGraph($Nodes) {
$ht = [ordered]@{}
$ht.Nodes = $Nodes
$ht.Edges = for ($i = 0; $i -lt $Nodes.Count; $i++) {
for ($j = 0; $j -lt $nodes.Count; $j++) {
if ($i -lt $j) {
New-Edge $Nodes[$i] $Nodes[$j] -AsObject
}
}
}
$ht.Visual = graph {
inline 'edge [arrowsize=0]'
edge $ht.Edges -FromScript { $_.To } -ToScript { $_.From }
}
[PSCustomObject]$ht
}
```

```
$completeGraph = Get-CompleteGraph (0..9)
$completeGraph.Visual | Show-PSGraph
```

```
function Get-RandomGraph ($NodeCount, $Probability, [switch]$NoVisual) {
$ht = [ordered]@{}
$ht.Edges = for ($i = 0; $i -le $NodeCount - 1; $i++) {
for ($j = 0; $j -le $NodeCount - 1; $j++) {
if ($i -lt $j) {
$rand = (Get-Random -Minimum 0 -Maximum 10000) / 10000
if ($rand -lt $Probability) {
New-Edge $i $j -AsObject
}
}
}
}
$ht.Nodes = 0..($NodeCount - 1)
if (-not $NoVisual) {
$ht.Visual = graph -Name Random {
inline 'edge [arrowsize=0]'
node $ht.Nodes
edge $ht.Edges -FromScript { $_.From } -ToScript { $_.To }
}
}
[PSCustomObject]$ht
}
```

```
$randomGraph = Get-RandomGraph 10 .3
$randomGraph.Visual | Show-PSGraph
$randomGraph.Edges.Count
```

```
function Get-Neighbours ($Edges, $Name, [switch]$Undirected) {
$edgeObjects = @($Edges)
if (@($Edges)[0].GetType().FullName -ne 'System.Management.Automation.PSCustomObject') {
$edgeObjects = foreach ($edge in $Edges) {
[PSCustomObject]$edge
}
}
(& {
($edgeObjects.where{ $_.From -eq $Name }).To
if ($Undirected) {
($edgeObjects.where{ $_.To -eq $Name }).From
}
}).where{ ![String]::IsNullOrEmpty($_) }
}
```

```
Get-Neighbours $completeGraph.Edges 0
```

```
Get-Neighbours $randomGraph.Edges 2
```

```
function Get-ReachableNodes ($Edges, $StartNode, [switch]$Undirected) {
$seen = New-Object System.Collections.Generic.HashSet[string]
$stack = New-Object System.Collections.Generic.Stack[string]
$null = $stack.Push($StartNode)
while ($stack.Count -gt 0) {
$node = $stack.Pop()
if (-not $seen.Contains($node)) {
$null = $seen.Add($node)
Get-Neighbours $Edges $node -Undirected:$Undirected | ForEach-Object {
$null = $stack.Push( $_ )
}
}
}
return $seen
}
```

```
function Get-IsConnected($Graph, [switch]$Undirected) {
if ($Graph.Edges.Count -eq 0) { return $false }
$startNode = $Graph.Edges[0].From
$reachable = Get-ReachableNodes $Graph.Edges $startNode -Undirected:$Undirected
$reachable.Count -eq $Graph.Nodes.Count
}
```

```
Get-IsConnected $completeGraph -Undirected
```

```
Get-IsConnected $randomGraph -Undirected
```

```
function Get-ProbabilityConnected($NodeCount, $Probability, $Iterations = 100) {
$count = 0
for ($i = 0; $i -le $Iterations; $i++) {
$randomGraph = Get-RandomGraph $NodeCount $Probability -Undirected -NoVisual
if ((Get-IsConnected $randomGraph -Undirected )) { $count++ }
}
$count / $Iterations
}
```

```
$nodeCount = 10
Get-ProbabilityConnected $nodeCount .23 100
```

```
[System.Math]::Log($nodeCount) / $nodeCount
```

```
function Get-LogSpace([Double]$Minimum, [Double]$Maximum, $Count) {
$increment = ($Maximum - $Minimum) / ($Count - 1)
for ( $i = 0; $i -lt $Count; $i++ ) {
[Math]::Pow( 10, ($Minimum + $increment * $i))
}
}
#So let's plot the probability of connectivity for a range of values for p
$probabilities = Get-LogSpace -1.3 0 11
$probabilities
```

```
foreach ($probability in $probabilites) {
[PSCustomObject][ordered]@{
Probability = $probability
ProbabilityConnected = (Get-ProbabilityConnected $nodeCount $probability 100)
}
}
```

WordPress conversion from GraphTheory.ipynb by nb2wp v0.3.1

Photo Credit: PapaPiper Flickr via Compfight cc

## One thought on “Graph theory with PowerShell”