Graf w PowerShell

Dzisiaj troszkę się namęczyłem z implementacją grafu skierowanego w PowerShellu. Co prawda dużo łatwiej było by mi zaimplementować graf w c#, ale w ramach ćwiczeń ... chciałem się namęczyć :)

Poniżej jest moja implementacji grafu skierowane
Na początku tworzymy obiekt, który będzie zawierał listę krawędzi:

function Create-Graph
{
    return new-object PSObject | 
            Add-Member -PassThru -MemberType NoteProperty -Name  Edges  -Value @()  -TypeName "array" 
}

Do dodawania krawędzi potrzebujemy dodatkowych funkcja. Zakładamy, że krawędź będzie zawierała informację o połączeniu dwóch wierzchołków oraz wartości tego połączenia.

function Create-Edge
{
    param(
        [ValidateNotNullOrEmpty()] 
        [string]$from,
        [ValidateNotNullOrEmpty()]
        [string]$to,
        [int]$weight=1
    )
    return @{
        From  = $from;
        To = $to;
        Weight = $weight;
    }
}

function Add-Edge
{
    param(
        [Parameter(Mandatory=$true, Position=1,ValueFromPipeline=$true)]  
        [ValidateNotNull()]    
        $graph,

        [Parameter(Mandatory=$true, Position=2)] 
        [ValidateNotNull()]     
        $edge
      )
    process{
        $graph.Edges +=$edge
        return $graph
    }
}

Wtedy poniższy kod tworzy graf skierowany:

$graph  = Create-Graph | 
    Add-Edge -edge (Create-Edge A B  1 ) |
    Add-Edge -edge (Create-Edge A C  5) |
    Add-Edge -edge (Create-Edge A D  3) |
    Add-Edge -edge (Create-Edge A E  11) |
    Add-Edge -edge (Create-Edge B C  9) |
    Add-Edge -edge (Create-Edge B D  1) |
    Add-Edge -edge (Create-Edge B E  2) |
    Add-Edge -edge (Create-Edge C D  6) |
    Add-Edge -edge (Create-Edge C E  4) |
    Add-Edge -edge (Create-Edge D E  3) 

Do sprawdzenia nazw wierzchołków pomocne będą poniższe funkcje:

function Get-EdgesNumber
{
    param(
        [Parameter(Mandatory=$true, Position=1)] 
        [ValidateNotNull()]     
        $graph
      )
    return $graph.Edges.Count
}

function Get-Vertices
{
    [cmdletBinding(SupportsShouldProcess=$true,ConfirmImpact='Medium')] 
    param(
        [Parameter(Mandatory=$true, Position=1)]
        [ValidateNotNull()]      
        $graph
      )
      Write-Verbose "Getting number of Vertices in graph"

      [array] $toVertices = $graph.Edges.To 
      [array] $fromVertices =   $graph.Edges.From
      return [array](($toVertices + $fromVertices) | select -Unique | sort)
}

function ConvertFrom-Graph
{
    [cmdletBinding(SupportsShouldProcess=$true,ConfirmImpact='Medium')] 
    param(
        [Parameter(Mandatory=$true, Position=1,ValueFromPipeline=$true)]
        [ValidateNotNull()] 
        $graph
      )
    process {
        $graph.Edges | %{
              $from =  $_.From 
              $to = $_.To
              $weight = $_.Weight
              Write-Verbose "Weight is $weight for:"
              "$from -> $to"
              }
    }
}

A poniżej przedstawione są wywołania tych funkcji:

Get-EdgesNumber $graph

Get-Vertices $graph

$graph | ConvertFrom-Graph

Oprócz reprezentacji grafu za pomocą kolekcji krawędzi można przedstawić graf za pomocą macierzy:

function ConvertTo-Matrix
{
   param(
        [Parameter(Mandatory=$true, Position=1,ValueFromPipeline=$true)]
        [ValidateNotNull()] 
        $graph
      )
  process{
        $vertices= Get-Vertices $graph
        $dim  = $vertices.Length
        [object[][]]$matrix =  Create-ZeroMatrix $dim
   
        $graph.Edges | % {
            $from = $_.From
            $to = $_.To
            $weight = $_.Weight

            $fromIndex = $vertices.IndexOf($from)
            $toIndex = $vertices.IndexOf($to)

            $matrix[$fromIndex][$toIndex]= $weight
        }
        return $matrix
    }
}

function Create-ZeroMatrix 
{
    param(
        [ValidateScript({$_ -ge 0})]
        [int]$dim
      )
      $matrix = New-Object 'object[][]' $dim,$dim

      for($i =0; $i -lt $dim; $i++ )
      {
        for($j=0; $j -lt $dim ; $j++)
        {
            $matrix[$i][$j] = 0
        }
      }
      return $matrix
}

function ConvertFrom-Matrix 
{
    [cmdletBinding(SupportsShouldProcess=$true,ConfirmImpact='Medium')] 
    param(
    [Parameter(Mandatory=$true, Position=1)]
    [object[][]]$matrix,
    [string]$seperator = ' '
      )
    for($i=0; $i -lt $matrix.Length; $i++)
    {
        Write-Verbose $i
        $(($matrix[$i]) -join $seperator)
    }
}

Konwersja kolekcji krawędzi na macierz jest przestawiona poniżej:

$matrix =  $graph | ConvertTo-Matrix
ConvertFrom-Matrix $matrix 

Oczywiście jeszcze wiele muszę poprawić m.in. konwersja z reprezentacji macierzowej do kolekcji krawędzi, modyfikacja wierzchołków, modyfikacja grafu skierowanego na graf nieskierowanego, walidacja czy wszystkie punkty są ze sobą połączone, ujednolicenie operacji na grafie itd.