C# - Simple Graph Interfaces and a MeshGraph


In a previous post about grids, I declared some interfaces to deal with graphs in an effort to explain how the grid segment could be treated as a graph.
Now I'm going to step further and define some generic graph interfaces as well as a MeshGraph that implements it based on the Mesh data structure from Unity3D.

To start, a vertex in a graph can be anything. So it will be an open type parameter for all interfaces.

An edge is a connection between 2 vertices, and as such, it can be defined as:

/// <summary>
/// An edge is simply a conection between 2 vertexes
/// </summary>
/// <typeparam name="TVertex">Vertex Type</typeparam>
public interface IGraphEdge<TVertex> : IEquatable<IGraphEdge<TVertex>>
{
    TVertex VertexA { get; }
    TVertex VertexB { get; }
}

Now, let's move to the graph. Starting with a read-only graph.

/// <summary>
/// A read-only graph is a collection of vertices with methods to get the edges
/// </summary>
/// <typeparam name="TVertex">Vertex Type</typeparam>
public interface IReadOnlyGraph<TVertex> : IEnumerable<TVertex>, IReadOnlyCollection<TVertex>
{
    bool Contains(TVertex vertex);
    IEnumerable<IGraphEdge<TVertex>> Edges(TVertex vertex);
}

So, a graph is an enumeration of vertices (IEnumerable<TVertex>) and it contains 2 methods, one to check if a vertex is in the graph and other that return edges.

Moving on to an editable-graph:

/// <summary>
/// A graph is a read-only graph with the ICollection methods (add,remove,etc..)
/// </summary>
/// <typeparam name="TVertex">Vertex Type</typeparam>
public interface IGraph<TVertex> : IReadOnlyGraph<TVertex>, ICollection<TVertex> { }

So we just add the typed ICollection interface to the vertex type and it will require whatever implements IGraph<TVertex> to implement collections methods, such as Add, Remove, etc...

Now let start to implement these interfaces in concrete classes:

/// <summary>
/// A struct that defines a graph edge
/// </summary>
public struct UndirectedEdge<T> : IGraphEdge<T> where T : IEquatable<T>
{
    public T VertexA { get; private set; }
    public T VertexB { get; private set; }

    public UndirectedEdge(T vertexA, T vertexB)
    {
        if(vertexA == null)
            throw new ArgumentNullException("vertexA");
        if (vertexB == null)
            throw new ArgumentNullException("vertexB");
        this.VertexA = vertexA;
        this.VertexB = vertexB;
    }

    /// <summary>
    /// Since this is an undirected graph, it evaluates to true if the vertexes are the same, no matter the order
    /// </summary>
    /// <param name="o">The other edge to compare</param>
    /// <returns>true (A=o.A and B=o.B) or (A=o.B and B=o.A)</returns>
    public bool Equals(IGraphEdge<T> o)
    {
        return (VertexA.Equals(o.VertexA) && VertexB.Equals(o.VertexB)) ||
            (VertexA.Equals(o.VertexB) && VertexB.Equals(o.VertexA));
    }

    /// <summary>
    /// Get hash code using big prime numbers to avoid hash conflict
    /// </summary>
    /// <returns>the hash code</returns>
    public override int GetHashCode()
    {
        var hashCode = 105289569;
        hashCode = hashCode * -1521134295 + (VertexA.GetHashCode() + VertexB.GetHashCode());
        return hashCode;
    }

    /// <summary>
    /// Get the other vertex.
    /// </summary>
    /// <param name="AorB">One of the vertices</param>
    /// <returns>The other vertex</returns>
    public T Other(T AorB)
    {
        if (AorB.Equals(VertexA))
            return VertexB;
        else if (AorB.Equals(VertexB))
            return VertexA;
        return default;
    }
} 
This is a simple undirected graph edge. In this case, it is a struct and when comparing 2 edges they will be the same of both vertexes are the same, no matter the order. Now moving on to a graph based on the mesh:
/// <summary>
/// A simple instance of a read-only graph based on a mesh.
/// The class does no allocate anything, all the methods are getters for Mesh fields/properties
/// </summary>
public class MeshGraph : IReadOnlyGraph<Vector3>
{
    /// <summary>
    /// Vertex count
    /// </summary>
    public int Count => mesh.vertices.Length;

    /// <summary>
    /// The mesh-graph
    /// </summary>
    public readonly Mesh mesh;
    /// <summary>
    /// check if a vertex is part of the mesh vertexes.
    /// </summary>
    /// <param name="vertex">the vertex to check</param>
    /// <returns>true if the vertex is one of the mesh vertexes</returns>
    public bool Contains(Vector3 vertex) => Array.IndexOf(mesh.vertices, vertex) != -1;

    /// <summary>
    /// 
    /// </summary>
    /// <param name="vertex"></param>
    /// <returns></returns>
    public IEnumerable<IGraphEdge<Vector3>> Edges(Vector3 vertex)
    {
        // Get the vertex index to check against triangle indexes
        var vertexIndex = Array.IndexOf(mesh.vertices, vertex);

        // A hash set for the found edges. Since UndirectedEdge implements GetHashCode the query for Contains should be O(1)
        // The same edge can exist defined in 2 different triples, so a HashSet garantees that there wil be no repeated edges
        HashSet<UndirectedEdge<Vector3>> triangleEdgesWithVertex = new HashSet<UndirectedEdge<Vector3>>();

        // Iterate through all triangles
        for (int i = 0; i < mesh.triangles.Length; i += 3)
        {
            // The 3 indexes of the vertices that form the triangle
            // This is allocated in separate variables for readability sake. The compiler should optimize this when compiling since they are only used once.
            var i0 = mesh.triangles[i];
            var i1 = mesh.triangles[i + 1];
            var i2 = mesh.triangles[i + 2];

            // The 3 vertices that form the triangle
            // The edges are v1-v2, v2-v3, v3-4.
            var v1 = mesh.vertices[i0];
            var v2 = mesh.vertices[i1];
            var v3 = mesh.vertices[i2];

            UndirectedEdge<Vector3> edge;
            if (v1 == vertex)
            {
                edge = new UndirectedEdge<Vector3>(v1, v2);
                if (triangleEdgesWithVertex.Add(edge))
                    yield return edge;
            }
            if (v2 == vertex)
            {
                edge = new UndirectedEdge<Vector3>(v2, v3);
                if (triangleEdgesWithVertex.Add(edge))
                    yield return edge;
            }
            if (v3 == vertex)
            {
                edge = new UndirectedEdge<Vector3>(v3, v1);
                if (triangleEdgesWithVertex.Add(edge))
                    yield return edge;
            }
        }
    }

    /// <summary>
    /// Getter for the vertices enumerator
    /// </summary>
    /// <returns>the vertices enumerator</returns>
    public IEnumerator<Vector3> GetEnumerator() => (IEnumerator<Vector3>)mesh.vertices.GetEnumerator();

    /// <summary>
    /// same as GetEnumerator(), but untyped
    /// </summary>
    /// <returns>the vertices enumerator</returns>
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

From what I looked into other APIs, some people like to assign data directly to vertices and edges as part of the graph itself. I'm a not big fan of this approach. Even if a generic data type for vertices and edges is declared on the class/interface

This Graph class I presented has no allocation besides the reference to the Mesh instance and wraps all graph definitions around it. If you want to assign data to the edges, you can declare an IGraph<TVertex, TEdge> interface save edge data on the graph class.

Personally, I think this is just one particular case of a graph. So, I'd rather keep things simple as it is very common to create graphs from external data rather than to build the graph itself by declaring vertexes and edges.

Comments

Popular posts from this blog

Unity3D/C# - Asynchronous Programming - Coroutines vs await/async

Unity/C# - Grids - Simple Grid Segment struct