< Summary

Class:Towel.DataStructures.GraphSetOmnitree<T1, T2, T3>
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/Graph.cs
Covered lines:64
Uncovered lines:49
Coverable lines:113
Total lines:898
Line coverage:56.6% (64 of 113)
Covered branches:11
Total branches:22
Branch coverage:50% (11 of 22)

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
File 1: get_Start()100%1100%
File 1: get_End()100%1100%
File 1: .ctor(...)100%1100%
File 1: .ctor(...)100%10%
File 1: .ctor(...)100%4100%
File 1: get_Equate()100%10%
File 1: get_Hash()100%10%
File 1: get_EdgeCount()100%1100%
File 1: get_NodeCount()100%1100%
File 1: TryAdd(...)50%271.42%
File 1: TryAdd(...)66.66%670.58%
File 1: TryRemove(...)50%277.77%
File 1: TryRemove(...)0%60%
File 1: Adjacent(...)100%1100%
File 1: Neighbors(...)50%275%
File 1: Clone()100%10%
File 1: Clear()100%10%
File 1: StepperBreak(...)100%10%
File 1: EdgesBreak(...)100%1100%
File 1: System.Collections.IEnumerable.GetEnumerator()100%10%
File 1: GetEnumerator()100%10%
File 1: GetNeighbours(...)100%10%
File 1: ToArray()100%10%

File(s)

/home/runner/work/Towel/Towel/Sources/Towel/DataStructures/Graph.cs

#LineLine coverage
 1namespace Towel.DataStructures;
 2
 3/// <summary>Static helpers for <see cref="IGraph{T}"/>.</summary>
 4public static class Graph
 5{
 6  #region Extension Methods
 7
 8  /// <summary>Adds an edge to a graph.</summary>
 9  /// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 10  /// <param name="graph">The data structure to add the value to.</param>
 11  /// <param name="a">The start of the edge.</param>
 12  /// <param name="b">The end of the edge.</param>
 13  public static void Add<T>(this IGraph<T> graph, T a, T b)
 14  {
 15    var (success, exception) = graph.TryAdd(a, b);
 16    if (!success)
 17    {
 18      throw exception ?? new ArgumentException($"{nameof(Add)} failed but the {nameof(exception)} is null");
 19    }
 20  }
 21
 22  /// <summary>Removes a value from a graph.</summary>
 23  /// <typeparam name="T">The type of value.</typeparam>
 24  /// <param name="graph">The data structure to remove the value from.</param>
 25  /// <param name="value">The value to be removed.</param>
 26  public static void Remove<T>(this IGraph<T> graph, T value)
 27  {
 28    var (success, exception) = graph.TryRemove(value);
 29    if (!success)
 30    {
 31      throw exception ?? new ArgumentException($"{nameof(Remove)} failed but the {nameof(exception)} is null");
 32    }
 33  }
 34
 35  /// <summary>Removes an edge from a graph.</summary>
 36  /// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 37  /// <param name="graph">The data structure to remove the value from.</param>
 38  /// <param name="a">The start of the edge.</param>
 39  /// <param name="b">The end of the edge.</param>
 40  public static void Remove<T>(this IGraph<T> graph, T a, T b)
 41  {
 42    var (success, exception) = graph.TryRemove(a, b);
 43    if (!success)
 44    {
 45      throw exception ?? new ArgumentException($"{nameof(Remove)} failed but the {nameof(exception)} is null");
 46    }
 47  }
 48
 49  /// <summary>Invokes a function on every edge in the graph.</summary>
 50  /// <typeparam name="T">The type of values stored in this graph.</typeparam>
 51  /// <param name="graph">The graph to traverse the edges of.</param>
 52  /// <param name="step">The function on every edge in the graph.</param>
 53  public static void Edges<T>(this IGraph<T> graph, Action<(T, T)> step)
 54  {
 55    if (step is null) throw new ArgumentNullException(nameof(step));
 56    graph.Edges<T, SAction<(T, T)>>(step);
 57  }
 58
 59  /// <summary>Invokes a function on every edge in the graph.</summary>
 60  /// <typeparam name="T">The type of values stored in this graph.</typeparam>
 61  /// <typeparam name="TStep">The type of the step function.</typeparam>
 62  /// <param name="graph">The graph to traverse the edges of.</param>
 63  /// <param name="step">The function on every edge in the graph.</param>
 64  public static void Edges<T, TStep>(this IGraph<T> graph, TStep step = default)
 65    where TStep : struct, IAction<(T, T)> =>
 66    graph.EdgesBreak<StepBreakFromAction<(T, T), TStep>>(step);
 67
 68  /// <summary>Invokes a function on every edge in the graph.</summary>
 69  /// <typeparam name="T">The type of values stored in this graph.</typeparam>
 70  /// <param name="graph">The graph to traverse the edges of.</param>
 71  /// <param name="step">The function on every edge in the graph.</param>
 72  /// <returns>The status of iteration.</returns>
 73  public static StepStatus EdgesBreak<T>(this IGraph<T> graph, Func<(T, T), StepStatus> step)
 74  {
 75    if (step is null) throw new ArgumentNullException(nameof(step));
 76    return graph.EdgesBreak<SFunc<(T, T), StepStatus>>(step);
 77  }
 78
 79  #endregion
 80}
 81
 82/// <summary>A graph data structure that stores nodes and edges.</summary>
 83/// <typeparam name="T">The generic node type to store in the graph.</typeparam>
 84public interface IGraph<T> : IDataStructure<T>,
 85  DataStructure.IAddable<T>,
 86  DataStructure.IRemovable<T>,
 87  DataStructure.IClearable
 88{
 89  #region Properties
 90
 91  /// <summary>The number of edges in the graph.</summary>
 92  int EdgeCount { get; }
 93  /// <summary>The number of nodes in the graph.</summary>
 94  int NodeCount { get; }
 95
 96  #endregion
 97
 98  #region Methods
 99
 100  /// <summary>Checks if an edge exists from <paramref name="a"/> to <paramref name="b"/>.</summary>
 101  /// <param name="a">The start of the edge.</param>
 102  /// <param name="b">The end of the edge.</param>
 103  /// <returns>True if an edge exists from <paramref name="a"/> to <paramref name="b"/>; False if not</returns>
 104  bool Adjacent(T a, T b);
 105
 106  /// <summary>Gets all the nodes adjacent to a and performs the provided delegate on each.</summary>
 107  /// <param name="a">The node to find all the adjacent node to.</param>
 108  /// <param name="function">The delegate to perform on each adjacent node to a.</param>
 109  void Neighbors(T a, Action<T> function);
 110
 111  /// <summary>Gets enumerator of all neighbours of a node</summary>
 112  /// <param name="node">The node to get neighbours of</param>
 113  /// <returns>IEnumerable of all neighbours of the given node</returns>
 114  System.Collections.Generic.IEnumerable<T> GetNeighbours(T node);
 115
 116  /// <summary>Adds an edge to the graph starting at a and ending at b.</summary>
 117  /// <param name="start">The stating point of the edge to add.</param>
 118  /// <param name="end">The ending point of the edge to add.</param>
 119  /// <returns>
 120  /// - <see cref="bool"/> Success: true if the edge was added or false if not<br/>
 121  /// - <see cref="Exception"/>? Exception: the exception that occured if the add failed
 122  /// </returns>
 123  (bool Success, Exception? Exception) TryAdd(T start, T end);
 124
 125  /// <summary>Removes an edge from the graph.</summary>
 126  /// <param name="start">The starting point of the edge to remove.</param>
 127  /// <param name="end">The ending point of the edge to remove.</param>
 128  /// <returns>
 129  /// - <see cref="bool"/> Success: true if the edge was removed or false if not<br/>
 130  /// - <see cref="Exception"/>? Exception: the exception that occured if the remove failed
 131  /// </returns>
 132  (bool Success, Exception? Exception) TryRemove(T start, T end);
 133
 134  /// <summary>Invokes a function on every edge in the graph.</summary>
 135  /// <typeparam name="TStep">The type of the step function.</typeparam>
 136  /// <param name="step">The function to perform on every edge in the graph.</param>
 137  /// <returns>The status of the traversal.</returns>
 138  StepStatus EdgesBreak<TStep>(TStep step = default)
 139    where TStep : struct, IFunc<(T, T), StepStatus>;
 140
 141  #endregion
 142}
 143
 144/// <summary>Static helpers for <see cref="GraphSetOmnitree{T, TEquate, THash}"/>.</summary>
 145public static class GraphSetOmnitree
 146{
 147  #region Extension Methods
 148
 149  /// <summary>Constructs a new <see cref="GraphSetOmnitree{T, TEquate, THash}"/>.</summary>
 150  /// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 151  /// <param name="equate">The function for comparing <typeparamref name="T"/> values for equality.</param>
 152  /// <param name="hash">The function for hashing <typeparamref name="T"/> values.</param>
 153  /// <returns>The new constructed <see cref="GraphSetOmnitree{T, TEquate, THash}"/>.</returns>
 154  public static GraphSetOmnitree<T, SFunc<T, T, bool>, SFunc<T, int>> New<T>(
 155    Func<T, T, bool>? equate = null,
 156    Func<T, int>? hash = null) =>
 157    new(equate ?? Equate, hash ?? Hash);
 158
 159  #endregion
 160}
 161
 162/// <summary>Stores the graph as a set-hash of nodes and quadtree of edges.</summary>
 163/// <typeparam name="T">The generic type of this data structure.</typeparam>
 164/// <typeparam name="TEquate">The type of function for quality checking <typeparamref name="T"/> values.</typeparam>
 165/// <typeparam name="THash">The type of function for hashing <typeparamref name="T"/> values.</typeparam>
 166public class GraphSetOmnitree<T, TEquate, THash> : IGraph<T>,
 167  ICloneable<GraphSetOmnitree<T, TEquate, THash>>,
 168  DataStructure.IEquating<T, TEquate>,
 169  DataStructure.IHashing<T, THash>
 170  where TEquate : struct, IFunc<T, T, bool>
 171  where THash : struct, IFunc<T, int>
 172{
 173  internal SetHashLinked<T, TEquate, THash> _nodes;
 174  internal OmnitreePointsLinked<Edge, T, T> _edges;
 175
 176  #region Nested Types
 177
 178  /// <summary>Represents an edge in a graph.</summary>
 179  internal class Edge
 180  {
 181    /// <summary>The starting node of the edge.</summary>
 167182    internal T Start { get; set; }
 183    /// <summary>The ending node of the edge.</summary>
 169184    internal T End { get; set; }
 185
 25186    internal Edge(T start, T end)
 25187    {
 25188      Start = start;
 25189      End = end;
 25190    }
 191  }
 192
 193  #endregion
 194
 195  #region Constructors
 196
 197  /// <summary>This constructor is for cloning purposes.</summary>
 198  /// <param name="graph">The graph to construct a clone of.</param>
 0199  internal GraphSetOmnitree(GraphSetOmnitree<T, TEquate, THash> graph)
 0200  {
 0201    _edges = graph._edges.Clone();
 0202    _nodes = graph._nodes.Clone();
 0203  }
 204
 205  /// <summary>Constructs a new GraphSetOmnitree.</summary>
 206  /// <param name="equate">The equate delegate for the data structure to use.</param>
 207  /// <param name="compare">The compare delegate for the data structure to use.</param>
 208  /// <param name="hash">The hash delegate for the datastructure to use.</param>
 5209  public GraphSetOmnitree(
 5210    TEquate equate = default,
 5211    THash hash = default,
 5212    Func<T?, T?, CompareResult>? compare = null)
 5213  {
 5214    compare ??= Compare;
 5215    _nodes = new(equate, hash);
 5216    _edges = new OmnitreePointsLinked<Edge, T, T>(
 5217      (Edge a, out T start, out T end) =>
 139218      {
 139219        start = a.Start;
 139220        end = a.End;
 139221      },
 5222      compare, compare);
 5223  }
 224
 225  #endregion
 226
 227  #region Properties
 228
 229  /// <inheritdoc/>
 0230  public TEquate Equate => _nodes.Equate;
 231
 232  /// <inheritdoc/>
 0233  public THash Hash => _nodes.Hash;
 234
 235  /// <inheritdoc/>
 1236  public int EdgeCount => _edges.Count;
 237
 238  /// <inheritdoc/>
 1239  public int NodeCount => _nodes.Count;
 240
 241  #endregion
 242
 243  #region Methods
 244
 245  /// <inheritdoc/>
 246  public (bool Success, Exception? Exception) TryAdd(T node)
 25247  {
 25248    var (success, exception) = _nodes.TryAdd(node);
 25249    if (!success)
 0250    {
 0251      return (false, new ArgumentException(paramName: nameof(node), message: "Attempting to add an already existing node
 252    }
 25253    return (true, null);
 25254  }
 255
 256  /// <inheritdoc/>
 257  public (bool Success, Exception? Exception) TryAdd(T start, T end)
 26258  {
 26259    if (!_nodes.Contains(start))
 0260    {
 0261      return (false, new ArgumentException("Adding an edge to a graph from a node that does not exists"));
 262    }
 26263    if (!_nodes.Contains(end))
 1264    {
 1265      return (false, new ArgumentException("Adding an edge to a graph to a node that does not exists"));
 266    }
 25267    Exception? exception = null;
 25268    _edges.Stepper(
 0269      e => { exception = new ArgumentException("Adding an edge to a graph that already exists"); return Break; },
 25270      start, start, end, end);
 25271    if (exception is not null)
 0272    {
 0273      return (false, exception);
 274    }
 25275    _edges.Add(new Edge(start, end));
 25276    return (true, null);
 26277  }
 278
 279  /// <inheritdoc/>
 280  public (bool Success, Exception? Exception) TryRemove(T node)
 1281  {
 1282    var (success, exception) = _nodes.TryRemove(node);
 1283    if (!success)
 0284    {
 0285      return (false, new ArgumentException("Removing a node from a graph from a node that does not exists", innerExcepti
 286    }
 1287    _edges.Remove(node, node, None, None);
 1288    _edges.Remove(None, None, node, node);
 1289    return (true, null);
 1290  }
 291
 292  /// <inheritdoc/>
 293  public (bool Success, Exception? Exception) TryRemove(T start, T end)
 0294  {
 0295    if (!_nodes.Contains(start))
 0296    {
 0297      return (false, new ArgumentException("Removing an edge from a graph from a node that does not exists"));
 298    }
 0299    if (!_nodes.Contains(end))
 0300    {
 0301      return (false, new ArgumentException("Removing an edge from a graph to a node that does not exists"));
 302    }
 303#warning TODO: Add the number of values removed in Omnitree Remove method (then you can use the return count rather than
 0304    Exception? exception = null;
 0305    _edges.Stepper(
 0306      edge => { exception = new ArgumentException("Removing a non-existing edge in a graph"); return Break; },
 0307      start, start, end, end);
 0308    if (exception is not null)
 0309    {
 0310      return (false, exception);
 311    }
 0312    _edges.Remove(start, start, end, end);
 0313    return (true, null);
 0314  }
 315
 316  /// <inheritdoc/>
 317  public bool Adjacent(T a, T b)
 1318  {
 1319    bool exists = false;
 1320    _edges.Stepper(edge =>
 1321    {
 1322      exists = true;
 1323      return Break;
 2324    }, a, a, b, b);
 1325    return exists;
 1326  }
 327
 328  /// <inheritdoc/>
 329  public void Neighbors(T node, Action<T> step)
 1330  {
 1331    if (!_nodes.Contains(node))
 0332    {
 0333      throw new InvalidOperationException("Attempting to look up the neighbors of a node that does not belong to a graph
 334    }
 3335    _edges.Stepper(e => step(e.End),
 1336      node, node,
 1337      None, None);
 1338  }
 339
 340  /// <inheritdoc/>
 0341  public GraphSetOmnitree<T, TEquate, THash> Clone() => new(this);
 342
 343  /// <inheritdoc/>
 344  public void Clear()
 0345  {
 0346    _nodes.Clear();
 0347    _edges.Clear();
 0348  }
 349
 350  /// <inheritdoc/>
 351  public StepStatus StepperBreak<TStep>(TStep step = default)
 352    where TStep : struct, IFunc<T, StepStatus> =>
 0353    _nodes.StepperBreak(step);
 354
 355  /// <inheritdoc/>
 356  public StepStatus EdgesBreak<TStep>(TStep step = default)
 357    where TStep : struct, IFunc<(T, T), StepStatus> =>
 358#warning TODO: optimize this (structs vs delegate)
 4359      _edges.StepperBreak(edge => step.Invoke((edge.Start, edge.End)));
 360
 0361  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 362
 363  /// <inheritdoc/>
 0364  public System.Collections.Generic.IEnumerator<T> GetEnumerator() => _nodes.GetEnumerator();
 365
 366  /// <inheritdoc/>
 367  public System.Collections.Generic.IEnumerable<T> GetNeighbours(T node)
 0368  {
 0369    ListArray<T> NodeList = new();
 0370    Neighbors(node, n => NodeList.Add(n));
 0371    return NodeList;
 0372  }
 373
 374  /// <inheritdoc/>
 0375  public T[] ToArray() => _nodes.ToArray();
 376
 377  #endregion
 378}
 379
 380/// <summary>Static helpers for <see cref="GraphMap{T, TEquate, THash}"/>.</summary>
 381public static class GraphMap
 382{
 383  #region Extension Methods
 384
 385  /// <summary>Constructs a new <see cref="GraphMap{T, TEquate, THash}"/>.</summary>
 386  /// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 387  /// <param name="equate">The function for comparing <typeparamref name="T"/> values for equality.</param>
 388  /// <param name="hash">The function for hashing <typeparamref name="T"/> values.</param>
 389  /// <returns>The new constructed <see cref="GraphMap{T, TEquate, THash}"/>.</returns>
 390  public static GraphMap<T, SFunc<T, T, bool>, SFunc<T, int>> New<T>(
 391    Func<T, T, bool>? equate = null,
 392    Func<T, int>? hash = null) =>
 393    new(equate ?? Equate, hash ?? Hash);
 394
 395  #endregion
 396}
 397
 398/// <summary>Stores a graph as a map and nested map (adjacency matrix).</summary>
 399/// <typeparam name="T">The generic node type of this graph.</typeparam>
 400/// <typeparam name="TEquate">The type of the equate function.</typeparam>
 401/// <typeparam name="THash">The type of the hash function.</typeparam>
 402public class GraphMap<T, TEquate, THash> : IGraph<T>,
 403  ICloneable<GraphMap<T, TEquate, THash>>,
 404  DataStructure.IEquating<T, TEquate>,
 405  DataStructure.IHashing<T, THash>
 406  where TEquate : struct, IFunc<T, T, bool>
 407  where THash : struct, IFunc<T, int>
 408{
 409  internal MapHashLinked<(SetHashLinked<T, TEquate, THash> Incoming, SetHashLinked<T, TEquate, THash> Outgoing), T, TEqu
 410  internal int _edgeCount;
 411
 412  #region Constructors
 413
 414  /// <summary>Constructs a new GraphMap.</summary>
 415  /// <param name="equate">The equate delegate for the data structure to use.</param>
 416  /// <param name="hash">The hash function for the data structure to use.</param>
 417  public GraphMap(TEquate equate = default, THash hash = default)
 418  {
 419    _edgeCount = 0;
 420    _map = new(equate, hash);
 421  }
 422
 423  /// <summary>Constructor for cloning purposes.</summary>
 424  /// <param name="graph">The graph to clone.</param>
 425  internal GraphMap(GraphMap<T, TEquate, THash> graph)
 426  {
 427    _edgeCount = graph._edgeCount;
 428    _map = graph._map.Clone();
 429  }
 430
 431  #endregion
 432
 433  #region Properties
 434
 435  /// <inheritdoc/>
 436  public TEquate Equate => _map.Equate;
 437
 438  /// <inheritdoc/>
 439  public THash Hash => _map.Hash;
 440
 441  /// <inheritdoc/>
 442  public int EdgeCount => _edgeCount;
 443
 444  /// <inheritdoc/>
 445  public int NodeCount => _map.Count;
 446
 447  #endregion
 448
 449  #region Methods
 450
 451  /// <inheritdoc/>
 452  public (bool Success, Exception? Exception) TryAdd(T node)
 453  {
 454    var (success, exception) = _map.TryAdd(node, (new(Equate, Hash), new(Equate, Hash)));
 455    if (!success)
 456    {
 457      return (false, new ArgumentException(paramName: nameof(node), message: "Adding an allready existing node to a grap
 458    }
 459    return (true, null);
 460  }
 461
 462  /// <inheritdoc/>
 463  public (bool Success, Exception? Exception) TryAdd(T start, T end)
 464  {
 465    if (!_map.Contains(start))
 466    {
 467      return (false, new ArgumentException(message: "Adding an edge to a non-existing starting node."));
 468    }
 469    if (!_map.Contains(end))
 470    {
 471      return (false, new ArgumentException(message: "Adding an edge to a non-existing ending node."));
 472    }
 473
 474    //// Commenting out the case below, as it should not occur
 475    // if (_map[start].Outgoing is null)
 476    // _map[start].Outgoing = new(_map.Equate, _map.Hash);
 477
 478    _map[start].Outgoing.Add(end);
 479    _map[end].Incoming.Add(start);
 480    _edgeCount++;
 481    return (true, null);
 482  }
 483
 484  /// <inheritdoc/>
 485  public (bool Success, Exception? Exception) TryRemove(T node)
 486  {
 487    if (!_map.Contains(node))
 488    {
 489      return (false, new ArgumentException(paramName: nameof(node), message: "Removing a non-existing node from a graph.
 490    }
 491    foreach (var item in _map[node].Outgoing)
 492    {
 493      this.Remove(node, item);
 494    }
 495    foreach (var item in _map[node].Incoming)
 496    {
 497      this.Remove(node, item);
 498    }
 499    _map.Remove(node);
 500    return (true, null);
 501  }
 502
 503  /// <inheritdoc/>
 504  public (bool Success, Exception? Exception) TryRemove(T start, T end)
 505  {
 506    if (_map.Contains(start) && _map.Contains(end) && _map[start].Outgoing.Contains(end))
 507    {
 508      _map[start].Outgoing.Remove(end);
 509      _map[end].Incoming.Remove(start);
 510      _edgeCount--;
 511      return (true, null);
 512    }
 513    return (false, new InvalidOperationException("Removing a non-existing edge from the graph."));
 514  }
 515
 516  /// <inheritdoc/>
 517  public bool Adjacent(T a, T b)
 518  {
 519    if (_map.Contains(a) && _map.Contains(b)) return _map[a].Outgoing.Contains(b);
 520    else return false;
 521  }
 522
 523  /// <inheritdoc/>
 524  public void Neighbors(T a, Action<T> step)
 525  {
 526    foreach (var node in _map[a].Outgoing) step(node);
 527  }
 528
 529  /// <inheritdoc/>
 530  public StepStatus StepperBreak<TStep>(TStep step = default)
 531    where TStep : struct, IFunc<T, StepStatus> =>
 532    _map.KeysBreak(step);
 533
 534  /// <inheritdoc/>
 535  public StepStatus EdgesBreak<TStep>(TStep step)
 536    where TStep : struct, IFunc<(T, T), StepStatus> =>
 537    _map.PairsBreak(pair =>
 538#warning TODO: use structs instead of delegates
 539        pair.Value.Outgoing.StepperBreak(b => step.Invoke((pair.Key, b))));
 540
 541  /// <inheritdoc/>
 542  public GraphMap<T, TEquate, THash> Clone() => new(this);
 543
 544  /// <inheritdoc/>
 545  public T[] ToArray() => _map.KeysToArray();
 546
 547  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 548
 549  /// <inheritdoc/>
 550  public System.Collections.Generic.IEnumerator<T> GetEnumerator() => _map.GetKeys().GetEnumerator();
 551
 552  /// <inheritdoc/>
 553  public System.Collections.Generic.IEnumerable<T> GetNeighbours(T node) => _map[node].Outgoing;
 554
 555  /// <inheritdoc/>
 556  public void Clear()
 557  {
 558    _edgeCount = 0;
 559    _map = new(_map.Equate, _map.Hash);
 560  }
 561
 562  #endregion
 563}
 564
 565/// <summary>A weighted graph data structure that stores nodes, edges with their corresponding weights.</summary>
 566/// <typeparam name="T">The generic node type of this graph.</typeparam>
 567/// <typeparam name="TWeight">The generic weight type of this graph.</typeparam>
 568public interface IGraphWeighted<T, TWeight> : IGraph<T>
 569{
 570  #region Methods
 571
 572  (bool Success, Exception? Exception) IGraph<T>.TryAdd(T start, T end) => TryAdd(start, end, default);
 573
 574  /// <summary>Adds a weighted edge to the graph </summary>
 575  /// <param name="start">The starting point of the edge to add</param>
 576  /// <param name="end">The ending point of the edge to add</param>
 577  /// <param name="weight">The weight of the edge</param>
 578  /// <returns>
 579  /// (<see cref="bool"/> Success, <see cref="Exception"/>? Exception)<br/>
 580  /// - <see cref="bool"/> Success: true if the value was added or false<br/>
 581  /// - <see cref="Exception"/>? Exception: the exception that occured if the add was not successful
 582  /// </returns>
 583  (bool Success, Exception? Exception) TryAdd(T start, T end, TWeight? weight);
 584
 585  /// <summary>Checks if b is adjacent to a.</summary>
 586  /// <param name="a">The starting point of the edge to check.</param>
 587  /// <param name="b">The ending point of the edge to check.</param>
 588  /// <param name="weight">The weight of the edge, if it exists.</param>
 589  /// <returns>True if b is adjacent to a; False if not</returns>
 590  bool Adjacent(T a, T b, out TWeight? weight);
 591
 592  /// <summary>Gets the weight of an edge.</summary>
 593  /// <param name="a">The starting node of the edge.</param>
 594  /// <param name="b">The ending node of the edge.</param>
 595  /// <returns>The weight of the edge.</returns>
 596  TWeight? GetWeight(T a, T b);
 597
 598  /// <summary>Enumerates and returns all edges present in the graph</summary>
 599  /// <returns>Array of Tuple of nodes that represent an edge</returns>
 600  (T, T)[] EdgesToArray();
 601
 602  /// <summary>Enumerates and returns all edges present in the graph</summary>
 603  /// <returns>Array of Tuple of nodes and weight that represent an edge</returns>
 604  (T, T, TWeight?)[] EdgesAndWeightsToArray();
 605
 606  #endregion
 607}
 608
 609/// <summary>Static helpers for <see cref="IGraphWeighted{T, W}"/>.</summary>
 610public static class GraphWeighted
 611{
 612  #region Extension Methods
 613
 614  /// <summary>Adds an edge to a weighted graph</summary>
 615  /// <typeparam name="T">The generic node type of this graph.</typeparam>
 616  /// <typeparam name="TWeight">The generic weight type of this graph.</typeparam>
 617  /// <param name="graph">The data structure to add the value to.</param>
 618  /// <param name="start">The starting point of the edge.</param>
 619  /// <param name="end">The ending point of the edge.</param>
 620  /// <param name="weight">The weight of the edge.</param>
 621  public static void Add<T, TWeight>(this IGraphWeighted<T, TWeight> graph, T start, T end, TWeight? weight)
 622  {
 623    var (success, exception) = graph.TryAdd(start, end, weight);
 624    if (!success)
 625    {
 626      throw exception ?? new ArgumentException(message: $"{nameof(Add)} failed but the {nameof(exception)} is null", inn
 627    }
 628  }
 629
 630  #endregion
 631}
 632
 633/// <summary>Static helpers for <see cref="GraphWeightedMap{T, W, TEquate, THash}"/>.</summary>
 634public static class GraphWeightedMap
 635{
 636  #region Extension Methods
 637
 638  /// <summary>Constructs a new <see cref="GraphWeightedMap{V, W, TEquate, THash}"/>.</summary>
 639  /// <typeparam name="T">The type of values stored in this data structure.</typeparam>
 640  /// <typeparam name="TWeight">The type of weight stored in the edges in this data structure.</typeparam>
 641  /// <param name="equate">The function for comparing <typeparamref name="T"/> values for equality.</param>
 642  /// <param name="hash">The function for hashing <typeparamref name="T"/> values.</param>
 643  /// <returns>The new constructed <see cref="GraphWeightedMap{V, W, TEquate, THash}"/>.</returns>
 644  public static GraphWeightedMap<T, TWeight, SFunc<T, T, bool>, SFunc<T, int>> New<T, TWeight>(
 645    Func<T, T, bool>? equate = null,
 646    Func<T, int>? hash = null) =>
 647    new(equate ?? Equate, hash ?? Hash);
 648
 649  #endregion
 650}
 651
 652/// <summary>Implements a weighted graph. Implements a Dictionary of Nodes and edges.</summary>
 653/// <typeparam name="T">The generic node type of this graph.</typeparam>
 654/// <typeparam name="TWeight">The generic weight type of this graph.</typeparam>
 655/// <typeparam name="TEquate">The type of function for quality checking <typeparamref name="T"/> values.</typeparam>
 656/// <typeparam name="THash">The type of function for hashing <typeparamref name="T"/> values.</typeparam>
 657public class GraphWeightedMap<T, TWeight, TEquate, THash> : IGraphWeighted<T, TWeight>,
 658  ICloneable<GraphWeightedMap<T, TWeight, TEquate, THash>>,
 659  DataStructure.IEquating<T, TEquate>,
 660  DataStructure.IHashing<T, THash>
 661  where TEquate : struct, IFunc<T, T, bool>
 662  where THash : struct, IFunc<T, int>
 663{
 664  internal MapHashLinked<(MapHashLinked<TWeight?, T, TEquate, THash> OutgoingEdges, SetHashLinked<T, TEquate, THash> Inc
 665  internal int _edgeCount;
 666
 667  #region Constructors
 668
 669  /// <summary>Constructs a new graph.</summary>
 670  /// <param name="equate">The function for equality checking <typeparamref name="T"/> values.</param>
 671  /// <param name="hash">The function for hashing <typeparamref name="T"/> values.</param>
 672  public GraphWeightedMap(TEquate equate = default, THash hash = default)
 673  {
 674    _map = new(equate, hash);
 675    _edgeCount = 0;
 676  }
 677
 678  internal GraphWeightedMap(GraphWeightedMap<T, TWeight, TEquate, THash> graph)
 679  {
 680    _edgeCount = graph._edgeCount;
 681    _map = graph._map.Clone();
 682  }
 683
 684  #endregion
 685
 686  #region Properties
 687
 688  /// <inheritdoc/>
 689  public TEquate Equate => _map.Equate;
 690
 691  /// <inheritdoc/>
 692  public THash Hash => _map.Hash;
 693
 694  /// <inheritdoc/>
 695  public int EdgeCount => _edgeCount;
 696
 697  /// <inheritdoc/>
 698  public int NodeCount => _map.Count;
 699
 700  #endregion
 701
 702  #region Methods
 703
 704  /// <inheritdoc/>
 705  public (bool Success, Exception? Exception) TryAdd(T value)
 706  {
 707#warning TODO: change this so that it does not allocate the new collections until necessary
 708    var (success, exception) = _map.TryAdd(value, (new(Equate, Hash), new(Equate, Hash)));
 709    if (!success)
 710    {
 711      return (false, new ArgumentException(message: "Queried value already exists in graph", paramName: nameof(value), e
 712    }
 713    else
 714    {
 715      return (true, null);
 716    }
 717  }
 718
 719  /// <inheritdoc/>
 720  public (bool Success, Exception? Exception) TryAdd(T start, T end, TWeight? weight)
 721  {
 722    var x = _map.TryGet(start);
 723    if (!x.Success)
 724    {
 725      return (false, new ArgumentException(message: "start Vertex must be present in graph before adding edge", paramNam
 726    }
 727    var y = _map.TryGet(end);
 728    if (!y.Success)
 729    {
 730      return (false, new ArgumentException(message: "end Vertex must be present in graph before adding edge", paramName:
 731    }
 732    x.Value.OutgoingEdges.Add(end, weight);
 733    y.Value.IncomingNodes.Add(start);
 734    _edgeCount++;
 735    return (true, null);
 736  }
 737
 738  /// <inheritdoc/>
 739  public bool Adjacent(T a, T b, out TWeight? weight)
 740  {
 741    var (success, exception, value) = _map.TryGet(a);
 742    if (!success)
 743    {
 744      throw new ArgumentException(message: "Vertex must be present in graph", paramName: nameof(a), innerException: exce
 745    }
 746    if (!_map.Contains(b)) throw new ArgumentException(message: "Vertex must be present in graph", paramName: nameof(b))
 747    if (value.OutgoingEdges.Contains(b))
 748    {
 749      weight = _map[a].OutgoingEdges[b];
 750      return true;
 751    }
 752    else
 753    {
 754      weight = default;
 755      return false;
 756    }
 757  }
 758
 759  /// <inheritdoc/>
 760  public bool Adjacent(T a, T b) => Adjacent(a, b, out var _);
 761
 762  /// <inheritdoc/>
 763  public void Clear() => _map.Clear();
 764
 765  /// <inheritdoc/>
 766  public void Neighbors(T a, Action<T> function) => _map[a].OutgoingEdges.Keys(function);
 767
 768  /// <inheritdoc/>
 769  public (bool Success, Exception? Exception) TryRemove(T start, T end)
 770  {
 771    if (!_map.Contains(start)) return (false, new ArgumentException(message: "Vertex must be present in graph", paramNam
 772    if (!_map.Contains(end)) return (false, new ArgumentException(message: "Vertex must be present in graph", paramName:
 773    _map[start].OutgoingEdges.Remove(end);
 774    _map[end].IncomingNodes.Remove(start);
 775    _edgeCount--;
 776    return (true, null);
 777  }
 778
 779  /// <inheritdoc/>
 780  public StepStatus StepperBreak<TStep>(TStep step = default)
 781    where TStep : struct, IFunc<T, StepStatus> =>
 782    _map.KeysBreak<TStep>(step);
 783
 784  /// <inheritdoc/>
 785  public StepStatus EdgesBreak<TStep>(TStep step = default)
 786    where TStep : struct, IFunc<(T, T), StepStatus>
 787  {
 788    EdgesStep<TStep> step2 = new() { _step = step, };
 789    return _map.PairsBreak<EdgesStep<TStep>>(step2);
 790  }
 791
 792  internal struct EdgesStep<TStep> : IFunc<((MapHashLinked<TWeight?, T, TEquate, THash> OutgoingEdges, SetHashLinked<T, 
 793    where TStep : struct, IFunc<(T, T), StepStatus>
 794  {
 795    internal TStep _step;
 796
 797    public StepStatus Invoke(((MapHashLinked<TWeight?, T, TEquate, THash> OutgoingEdges, SetHashLinked<T, TEquate, THash
 798    {
 799      EdgesStep2<TStep> step2 = new() { _a = a.Item2, _step = _step, };
 800      return a.Item1.OutgoingEdges.PairsBreak<EdgesStep2<TStep>>(step2);
 801    }
 802  }
 803
 804  internal struct EdgesStep2<TStep> : IFunc<(TWeight?, T), StepStatus>
 805    where TStep : struct, IFunc<(T, T), StepStatus>
 806  {
 807    internal TStep _step;
 808    internal T _a;
 809
 810    public StepStatus Invoke((TWeight?, T) a)
 811    {
 812      var edge = (_a, a.Item2);
 813      return _step.Invoke(edge);
 814    }
 815  }
 816
 817  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 818
 819  /// <inheritdoc/>
 820  public System.Collections.Generic.IEnumerator<T> GetEnumerator() =>
 821    _map.GetKeys().GetEnumerator();
 822
 823  /// <inheritdoc/>
 824  public (bool Success, Exception? Exception) TryRemove(T node)
 825  {
 826    if (!_map.Contains(node))
 827    {
 828      return (false, new ArgumentException("Node does not exist in graph", nameof(node)));
 829    }
 830    foreach (var item in _map[node].IncomingNodes)
 831    {
 832      this.Remove(node, item);
 833    }
 834    foreach (var item in _map[node].OutgoingEdges.GetKeys())
 835    {
 836      this.Remove(node, item);
 837    }
 838    _map.Remove(node);
 839    return (true, null);
 840  }
 841
 842  /// <inheritdoc/>
 843  public GraphWeightedMap<T, TWeight, TEquate, THash> Clone() => new(this);
 844
 845  /// <inheritdoc/>
 846  public T[] ToArray() => _map.KeysToArray();
 847
 848  /// <inheritdoc/>
 849  public (T, T)[] EdgesToArray()
 850  {
 851    (T, T)[] array = new (T, T)[_edgeCount];
 852    int i = 0;
 853    foreach (var (adjacencies, start) in _map.GetPairs())
 854    {
 855      foreach (var (_, end) in adjacencies.OutgoingEdges.GetPairs())
 856      {
 857        array[i++] = (start, end);
 858      }
 859    }
 860    return array;
 861  }
 862
 863  /// <inheritdoc/>
 864  public (T, T, TWeight?)[] EdgesAndWeightsToArray()
 865  {
 866    (T, T, TWeight?)[] array = new (T, T, TWeight?)[_edgeCount];
 867    int i = 0;
 868    foreach (var (adjacencies, start) in _map.GetPairs())
 869    {
 870      foreach (var (weight, end) in adjacencies.OutgoingEdges.GetPairs())
 871      {
 872        array[i++] = (start, end, weight);
 873      }
 874    }
 875    return array;
 876  }
 877
 878  /// <inheritdoc/>
 879  public System.Collections.Generic.IEnumerable<T> GetNeighbours(T node) => _map[node].OutgoingEdges.GetKeys();
 880
 881  /// <inheritdoc/>
 882  public TWeight? GetWeight(T a, T b)
 883  {
 884    var get1 = _map.TryGet(a);
 885    if (!get1.Success)
 886    {
 887      throw new ArgumentException("No edge found between the queried nodes");
 888    }
 889    var get2 = get1.Value.OutgoingEdges.TryGet(b);
 890    if (!get2.Success)
 891    {
 892      throw new ArgumentException("No edge found between the queried nodes");
 893    }
 894    return get2.Value;
 895  }
 896
 897  #endregion
 898}
Generated by: ReportGenerator 4.8.11.0
08/14/2022 - 14:40:42
GitHub | www.palmmedia.de

Methods/Properties

get_Start()
get_End()
.ctor(...)
.ctor(...)
.ctor(...)
get_Equate()
get_Hash()
get_EdgeCount()
get_NodeCount()
TryAdd(...)
TryAdd(...)
TryRemove(...)
TryRemove(...)
Adjacent(...)
Neighbors(...)
Clone()
Clear()
StepperBreak(...)
EdgesBreak(...)
System.Collections.IEnumerable.GetEnumerator()
GetEnumerator()
GetNeighbours(...)
ToArray()