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, [switch]$Undirected) {
$null = $PSBoundParameters.Remove('AsObject')
$ht = [Hashtable]$PSBoundParameters
if ($AsObject) {
return [PSCustomObject]$ht
}
return $ht
}
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($_) }
}
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))
}
}
function Get-RingLattice($Nodes, $NumConnections){
$ht = [ordered]@{}
$ht.Nodes = $Nodes
$cons = [int]($NumConnections/2)
$len = $Nodes.Count
$ht.Edges = foreach ($node in $Nodes){
for ($i=$node+1;$i -le ($node+$cons);$i++){
New-Edge $node $Nodes[($i % $len)] -AsObject
}
}
$ht.Visual = graph {
inline 'edge [arrowsize=0]'
edge $ht.Edges -FromScript { $_.To } -ToScript { $_.From }
}
[PSCustomObject]$ht
}
$ringLattice = Get-RingLattice (0..9) 4
$ringLattice.Visual | Show-PSGraph
function Get-SmallWorldGraph($Nodes, $NumConnections, $Probability){
$graph = Get-RingLattice $Nodes $NumConnections
$edges = $graph.Edges.Clone()
foreach ($edge in $graph.Edges){
$rand = (Get-Random -Minimum 0 -Maximum 10000) / 10000
if ($rand -le $Probability) {
$fromNeighbours = Get-Neighbours $graph.Edges $edge.From -Undirected
#need to use foreach construct to expand nexted array of fromNeighbours
$exclude = $edge.From,$edge.To,($fromNeighbours.foreach{$_})
$toConnect = $graph.Nodes.where{$_ -notin ($exclude.foreach{$_})}
#remove the current edge
#see https://en.wikipedia.org/wiki/De_Morgan%27s_laws
$graph.Edges = $graph.Edges.where{$_.From -ne $edge.From -or $_.To -ne $edge.To}
#add the new edge += for "adding to an array is bad but good enough in this case
$graph.Edges += New-Edge $edge.From (Get-Random -InputObject $toConnect) -AsObject
}
}
#redo the visual part based on the new edges
$graph.Visual = graph {
inline 'edge [arrowsize=0]'
edge $graph.Edges -FromScript { $_.To } -ToScript { $_.From }
}
$graph
}
foreach ($prob in (.1,.2,.8)){
$swGraph = Get-SmallWorldGraph (0..19) 4 $prob
$swGraph.Visual | Show-PSGraph
}
If you imagine a room with n people, where you want to determine the number of unique pairs:function Get-ClusteringCoefficient ($Graph){
$individualCEs = foreach ($node in $Graph.Nodes){
$neighbours = Get-Neighbours $Graph.Edges $node -Undirected
$numNeighbours = $neighbours.Count
#CE undefined skip to next node
if ($numNeighbours -lt 2) {
[Single]::NaN
continue
}
$possibleConnections = $numNeighbours * ($numNeighbours -1) / 2
$nodes = $Graph.Nodes
$actualConnections = for ($i = 0; $i -lt $numNeighBours; $i++) {
for ($j = 0; $j -lt $neighbours.Count; $j++) {
if ($i -lt $j) {
$l = $neighbours[$i]
$r = $neighbours[$j]
#the way the edge objects are setup currently we will need to check for both sides
#would be better to setup sundirected edges differently
$Graph.Edges.where{($_.From -eq $l -and $_.To -eq $r) -or ($_.From -eq $r -and $_.To -eq $l) }
}
}
}
($actualConnections.Count/$possibleConnections)
}
#return the average of the clustering coefficients per node exlcuding NaNs
($individualCEs.where{-not ([Single]::IsNaN($_)) } | Measure-Object -Average).Average
}
Get-ClusteringCoefficient $ringLattice
function Get-ShortestPath ($Graph, $StartNode) {
#distances keeps track of distances from the start node for each node
$distances = @{$StartNode = 0}
#usage of linked list to be able to add at the end (like in a stack) and remove from the beginning (like in a queue)
$list = New-Object System.Collections.Generic.LinkedList[int]
$null = $list.AddFirst($StartNode)
while ($list.Count -gt 0) {
#get the first element from the linked list
$node = $list.First.Value
$null = $list.RemoveFirst()
$neighbours = Get-Neighbours $Graph.Edges $node -Undirected
#find the neighbours that are not already contained in the hashtable
$neighbours = $neighbours.where{ $_ -notin $distances.Keys }
foreach ($neighbour in $neighbours){
#the distance to the neighbour is, by defintion, the current node's distance + 1
$distances.$neighbour = $distances.$node + 1
#add the neighbour to the list to discover further connections
$null = $list.AddLast($neighbour)
}
}
$distances.GetEnumerator().foreach{
[PSCustomObject][ordered]@{
Source = $startNode
Destination = $_.Name
Distance = $_.Value
}
}
}
Get-ShortestPath $ringLattice 0
$groupedEdges = $ringLattice.Edges | group From
$distances = foreach ($group in $groupedEdges){
Get-ShortestPath $ringLattice $group.Name
}
($distances.where{$_.Distance -ne 0 -and $_.Distance} |
Measure-Object -Property Distance -Average).Average
function Do-Experiment ($Nodes = (0..99), $NumConnections=3, $Probabilities){
foreach ($probability in $Probabilities){
$apl = [System.Collections.ArrayList]@()
$ccoe = [System.Collections.ArrayList]@()
$jobs = @()
$graph = Get-SmallWorldGraph $Nodes $NumConnections $probability
$groupedEdges = $graph.Edges | group From
foreach ($group in $groupedEdges){
$initBlock = [ScriptBlock]::Create(
'function Get-ShortestPath{' + (Get-Command Get-ShortestPath).Definition + '}' +
'function Get-Neighbours{' + (Get-Command Get-Neighbours).Definition + '}'
)
$jobs += Start-ThreadJob -InitializationScript $initBlock {
$group = $using:group
Get-ShortestPath $using:graph $group.Name
}
}
$null = $jobs | Wait-Job
$distances = $jobs | Receive-Job
$null = $jobs | Remove-Job
$null = $apl.Add(($distances.where{$_.Distance -ne 0} |
Measure-Object -Property Distance -Average).Average)
$null = $ccoe.Add((Get-ClusteringCoefficient $graph))
[PSCustomObject][ordered]@{
Probability = $probability
AveragePathLength = ($apl | Measure-Object -Average).Average
ClusteringCoeeficient = ($ccoe | Measure-Object -Average).Average
}
}
}
#get log-spaced probabilites to simulate the experiment with the same parameters
$probabilities = Get-LogSpace -4 0 9
$result = Do-Experiment -Probabilities $probabilities
#scale the avg. path length and clustering coeff.
#to be able to plot them on the same axis (same as in the experiment)
$firstApl = $result[0].AveragePathLength
$firstCoeff = $result[0].ClusteringCoeeficient
for ($i=0;$i -lt $result.Count;$i++){
$result[$i].AveragePathLength = $result[$i].AveragePathLength/$firstApl
$result[$i].ClusteringCoeeficient = $result[$i].ClusteringCoeeficient/$firstCoeff
}
WordPress conversion from graphTheory2.ipynb by nb2wp v0.3.1
Photo Credit: Tree Stock photos by Vecteezy
Tech thoughts 