| | | 1 | | namespace MoreStructures.Graphs; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// A graph data structure, directed or undirected. |
| | | 5 | | /// </summary> |
| | | 6 | | /// <remarks> |
| | | 7 | | /// <para id="definition"> |
| | | 8 | | /// DEFINITION |
| | | 9 | | /// <br/> |
| | | 10 | | /// A graph is a data structure composed of two types of objects: <g>vertices</g> and <g>edges</g>. |
| | | 11 | | /// <br/> |
| | | 12 | | /// Both vertices and edges can carry labels, weights, costs, or any other piece of information, specific to the |
| | | 13 | | /// scenario in which they are used. |
| | | 14 | | /// <br/> |
| | | 15 | | /// More precisely, a graph is conceptually defined as a couple of two collections: |
| | | 16 | | /// <br/> |
| | | 17 | | /// - a collection of vertices, |
| | | 18 | | /// <br/> |
| | | 19 | | /// - and a collection of edges, connecting such vertices, directionally or undirectionally. |
| | | 20 | | /// <br/> |
| | | 21 | | /// The actual underlying representation of a graph instance depends on the specific <see cref="IGraph"/> used. |
| | | 22 | | /// </para> |
| | | 23 | | /// </remarks> |
| | | 24 | | public interface IGraph |
| | | 25 | | { |
| | | 26 | | /// <summary> |
| | | 27 | | /// Returns the total number of vertices of the graph. |
| | | 28 | | /// </summary> |
| | | 29 | | /// <returns>A non-negative integer.</returns> |
| | | 30 | | int GetNumberOfVertices(); |
| | | 31 | | |
| | | 32 | | /// <summary> |
| | | 33 | | /// Returns the vertices of the graph which are neighbor of the <paramref name="start"/> vertex, each vertex |
| | | 34 | | /// together with its incoming or outgoing edge, linking the vertex to the <paramref name="start"/> vertex. |
| | | 35 | | /// </summary> |
| | | 36 | | /// <param name="start">The id of the vertex, to look for neighbors of.</param> |
| | | 37 | | /// <param name="takeIntoAccountEdgeDirection"> |
| | | 38 | | /// Whether to consider the direction of edges, when looking for neighbors. |
| | | 39 | | /// </param> |
| | | 40 | | /// <returns> |
| | | 41 | | /// A sequence of <see cref="Adjacency"/> instances, containing the id of the neighboring vertex V found, and the |
| | | 42 | | /// edge which connects the <paramref name="start"/> vertex to V, or viceversa. The order is <b>undefined</b>, |
| | | 43 | | /// and depends on the implementation. |
| | | 44 | | /// </returns> |
| | | 45 | | IEnumerable<Adjacency> GetAdjacentVerticesAndEdges(int start, bool takeIntoAccountEdgeDirection); |
| | | 46 | | |
| | | 47 | | /// <summary> |
| | | 48 | | /// Returns all the edges of this graph. |
| | | 49 | | /// </summary> |
| | | 50 | | /// <returns>A sequence of couples (sourceVertex, targetVertex), each identifying an edge of the graph.</returns> |
| | | 51 | | IEnumerable<(int edgeStart, int edgeEnd)> GetAllEdges(); |
| | | 52 | | |
| | | 53 | | /// <summary> |
| | | 54 | | /// Builds the reverse graph, i.e. a graph with the same set of vertices and reversed edges: for each edge (u, v) |
| | | 55 | | /// of the graph G, there is one edge (v, u) in the reverse graph G^-1. |
| | | 56 | | /// </summary> |
| | | 57 | | /// <returns>A new instance of <see cref="IGraph"/>, representing the reverse graph.</returns> |
| | | 58 | | IGraph Reverse(); |
| | | 59 | | |
| | | 60 | | /// <summary> |
| | | 61 | | /// An adjacency in a <see cref="IGraph"/> structure to a vertex, consisting of a neighboring |
| | | 62 | | /// <paramref name="Vertex"/>, connected to the first vertex via edge, identified by <paramref name="EdgeStart"/> |
| | | 63 | | /// and <paramref name="EdgeEnd"/>. |
| | | 64 | | /// </summary> |
| | | 65 | | /// <param name="Vertex">The neighboring vertex.</param> |
| | | 66 | | /// <param name="EdgeStart">The start vertex of the edge, connecting from/to the neighbor.</param> |
| | | 67 | | /// <param name="EdgeEnd">The end vertex of the edge, connecting from/to the neighbor.</param> |
| | 316773 | 68 | | public record struct Adjacency(int Vertex, int EdgeStart, int EdgeEnd); |
| | | 69 | | } |