| | | 1 | | namespace MoreStructures.Graphs.Visitor; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// A <see cref="IVisitStrategy"/> implementation which can perform the visit taking into account or not the |
| | | 5 | | /// direction of the edges of the graph, based on the <see cref="DirectedGraph"/> property. |
| | | 6 | | /// </summary> |
| | | 7 | | public abstract class DirectionableVisit : IVisitStrategy |
| | | 8 | | { |
| | | 9 | | /// <summary> |
| | | 10 | | /// Whether the provided <see cref="IGraph"/> should be considered as directed (i.e. edges should be |
| | | 11 | | /// traversed from start to end) or inderected (i.e. edges should be traversed both from start to end and from |
| | | 12 | | /// end to start). |
| | | 13 | | /// </summary> |
| | 4237 | 14 | | public bool DirectedGraph { get; } |
| | | 15 | | |
| | | 16 | | /// <summary> |
| | | 17 | | /// <inheritdoc cref="DirectionableVisit"/> |
| | | 18 | | /// </summary> |
| | | 19 | | /// <param name="directedGraph"> |
| | | 20 | | /// <inheritdoc cref="DirectedGraph" path="/summary"/> |
| | | 21 | | /// </param> |
| | 1171 | 22 | | protected DirectionableVisit(bool directedGraph) |
| | 1171 | 23 | | { |
| | 1171 | 24 | | DirectedGraph = directedGraph; |
| | 1171 | 25 | | } |
| | | 26 | | |
| | | 27 | | /// <inheritdoc/> |
| | 9645 | 28 | | public event EventHandler<VisitEventArgs> VisitingVertex = delegate { }; |
| | | 29 | | |
| | | 30 | | /// <summary> |
| | | 31 | | /// Invoke the <see cref="VisitingVertex"/> event with the provided <paramref name="args"/>. |
| | | 32 | | /// </summary> |
| | | 33 | | /// <param name="args">The arguments to be provided, when raising the event.</param> |
| | 4237 | 34 | | protected virtual void RaiseVisitingVertex(VisitEventArgs args) => VisitingVertex.Invoke(this, args); |
| | | 35 | | |
| | | 36 | | /// <inheritdoc/> |
| | 9587 | 37 | | public event EventHandler<VisitEventArgs> VisitedVertex = delegate { }; |
| | | 38 | | |
| | | 39 | | /// <summary> |
| | | 40 | | /// Invoke the <see cref="VisitedVertex"/> event with the provided <paramref name="args"/>. |
| | | 41 | | /// </summary> |
| | | 42 | | /// <param name="args">The arguments to be provided, when raising the event.</param> |
| | 4208 | 43 | | protected virtual void RaiseVisitedVertex(VisitEventArgs args) => VisitedVertex.Invoke(this, args); |
| | | 44 | | |
| | | 45 | | /// <inheritdoc/> |
| | 4887 | 46 | | public event EventHandler<VisitEventArgs> AlreadyVisitedVertex = delegate { }; |
| | | 47 | | |
| | | 48 | | /// <summary> |
| | | 49 | | /// Invoke the <see cref="AlreadyVisitedVertex"/> event with the provided <paramref name="args"/>. |
| | | 50 | | /// </summary> |
| | | 51 | | /// <param name="args">The arguments to be provided, when raising the event.</param> |
| | 1858 | 52 | | protected virtual void RaiseAlreadyVisitedVertex(VisitEventArgs args) => AlreadyVisitedVertex.Invoke(this, args); |
| | | 53 | | |
| | | 54 | | /// <summary> |
| | | 55 | | /// Runs a Depth First Search and returns vertices and related connected components. |
| | | 56 | | /// </summary> |
| | | 57 | | /// <param name="graph">The <see cref="IGraph"/> instance to be explored.</param> |
| | | 58 | | /// <returns> |
| | | 59 | | /// A sequence of couples of <see cref="int"/>, the first being the vertex id and the second being the label of the |
| | | 60 | | /// connected component, the vertex belongs to. |
| | | 61 | | /// </returns> |
| | | 62 | | /// <remarks> |
| | | 63 | | /// Generalizes both <see cref="DepthFirstSearchOfGraph(IGraph)"/> and <see cref="ConnectedComponents(IGraph)"/> |
| | | 64 | | /// methods, which have very similar implementations. Check those two methods for further information. |
| | | 65 | | /// </remarks> |
| | | 66 | | protected abstract IEnumerable<(int, int)> DepthFirstSearchAndConnectedComponentsOfGraph(IGraph graph); |
| | | 67 | | |
| | | 68 | | /// <inheritdoc/> |
| | | 69 | | public virtual IEnumerable<int> DepthFirstSearchOfGraph(IGraph graph) |
| | 232 | 70 | | { |
| | 2752 | 71 | | foreach (var (vertex, _) in DepthFirstSearchAndConnectedComponentsOfGraph(graph)) |
| | 1028 | 72 | | yield return vertex; |
| | 225 | 73 | | } |
| | | 74 | | |
| | | 75 | | /// <inheritdoc/> |
| | | 76 | | public virtual IDictionary<int, int> ConnectedComponents(IGraph graph) |
| | 56 | 77 | | { |
| | 56 | 78 | | var connectedComponents = new Dictionary<int, int>(); |
| | 452 | 79 | | foreach (var (vertex, connectedComponent) in DepthFirstSearchAndConnectedComponentsOfGraph(graph)) |
| | 142 | 80 | | connectedComponents[vertex] = connectedComponent; |
| | 56 | 81 | | return connectedComponents; |
| | 56 | 82 | | } |
| | | 83 | | |
| | | 84 | | /// <inheritdoc/> |
| | | 85 | | public abstract IEnumerable<int> DepthFirstSearchFromVertex(IGraph graph, int vertex); |
| | | 86 | | |
| | | 87 | | /// <inheritdoc/> |
| | | 88 | | public abstract IEnumerable<int> BreadthFirstSearchFromVertex(IGraph graph, int vertex); |
| | | 89 | | |
| | | 90 | | /// <inheritdoc/> |
| | | 91 | | public abstract IEnumerable<int> BreadthFirstSearchFromVertices(IGraph graph, IEnumerable<int> vertices); |
| | | 92 | | } |