A simple in-memory graph

Edge.cs

using System.Diagnostics;

namespace AboditUnits.Graph
{
    public partial class Graph<TNode, TRelation>
    {
        /// <summary>
        /// A relationship between two objects
        /// </summary>
        [DebuggerDisplay("{Start} -- {Predicate} --> {End}")]
        public struct Edge
        {
            public readonly TNode Start;
            public readonly TRelation Predicate;
            public readonly TNode End;

            public Edge(TNode start, TRelation predicate, TNode end)
            {
                this.Start = start;
                this.Predicate = predicate;
                this.End = end;
            }

            public override bool Equals(object obj)
            {
                if (!(obj is Edge)) return false;
                Edge other = (Edge) obj;
                return this.Start.Equals(other.Start) 
                    && this.Predicate.Equals(other.Predicate) 
                    && this.End.Equals(other.End);
            }

            public override int GetHashCode()
            {
                return this.Start.GetHashCode() ^ this.Predicate.GetHashCode() ^ this.End.GetHashCode();
            }
        }
    }
}

Graph.cs

using System;
using System.Collections;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;

namespace AboditUnits.Graph
{
    /// <summary>
    /// An in-memory graph of statements (subject, predicate, object)
    /// </summary>
    public partial class Graph<TNode, TRelation> : IEnumerable<TNode>
        where TNode : class, IEquatable<TNode>
        where TRelation : IEquatable<TRelation>
    {
        /// <summary>
        /// Limit the number of edges that can be attached to any node
        /// </summary>
        public int Limit { get; set; } = 10000;

        protected readonly ConcurrentDictionary<TNode, PredicateNext> StartIndexedEdges = new ConcurrentDictionary<TNode, PredicateNext>();
        protected readonly ConcurrentDictionary<TNode, PredicatePrevious> EndIndexedEdges = new ConcurrentDictionary<TNode, PredicatePrevious>();

        /// <summary>
        /// Add a statement, returns true if it was added, false if already there
        /// </summary>
        /// <remarks>
        /// Direct loops back to self are not allowed
        /// </remarks>
        public bool AddStatement(TNode start, TRelation predicate, TNode end)
        {
            if (start == null || end == null) throw new Exception("Trying to relate a null");
            // If something is a synonym of itself, really don't care
            if (start == end) return false;
            return this.AddStatement(new Edge(start, predicate, end));
        }

        /// <summary>
        /// Add a statement, returns true if it was added, false if already there
        /// </summary>
        private bool AddStatement(Edge statement)
        {
            var forward = new PredicateNext(statement.Predicate, statement.End);
            if (!StartIndexedEdges.TryAdd(statement.Start, forward))
            {
                var current = StartIndexedEdges[statement.Start];
                // Skip if the statement is already there
                if (current.Predicate.Equals(statement.Predicate) && current.End == statement.End)
                    return false;
                int i = Limit;
                while (current.Next != null)
                {
                    current = current.Next;
                    // Skip if the statement is already there
                    if (current.Predicate.Equals(statement.Predicate) && current.End == statement.End)
                        return false;
                    if (i-- < 0) throw new Exception("Infinite loop possible");
                }
                current.Next = forward;
            }

            var reverse = new PredicatePrevious(statement.Predicate, statement.Start);
            if (!EndIndexedEdges.TryAdd(statement.End, reverse))
            {
                var current = EndIndexedEdges[statement.End];
                // Skip if the statement is already there
                if (current.Predicate.Equals(statement.Predicate) && current.Start == statement.Start)
                    return false;
                int i = Limit;
                while (current.Next != null)
                {
                    current = current.Next;
                    // Skip if the statement is already there
                    if (current.Predicate.Equals(statement.Predicate) && current.Start == statement.Start)
                        return false;
                    if (i-- < 0) throw new Exception("Infinite loop possible");
                }
                current.Next = reverse;
            }
            return true;
        }

        public IEnumerable<TNode> Nodes
        {
            get
            {
                // Every node in the graph must be either a start node or an end node or it wouldn't be here
                return this.StartIndexedEdges.Select(x => x.Key).Concat(this.EndIndexedEdges.Select(x => x.Key)).Distinct();
            }
        }

        /// <summary>
        /// Examine every node in the graph for ones of type T
        /// </summary>
        public IEnumerable<T> GetNodes<T>() where T:TNode => this.Nodes.OfType<T>();

        /// <summary>
        /// Get all the edges of the graph
        /// </summary>
        public IEnumerable<Edge> Edges
        {
            get
            {
                return this.StartIndexedEdges
                    .SelectMany(e => e.Value.Select(pn => new Edge(e.Key, pn.Predicate, pn.End)));
            }
        }

        /// <summary>
        /// Find all the outgoing edges from a vertex with a given predicate (or null)
        /// </summary>
        /// <remarks>
        /// A single step in the graph away from a node
        /// </remarks>
        public IEnumerable<Edge> Follow(TNode start, TRelation predicate = default(TRelation))
        {
            PredicateNext startLink = null;
            if (StartIndexedEdges.TryGetValue(start, out startLink))
            {
                foreach (var pn in startLink.Where(pn =>
                    EqualityComparer<TRelation>.Default.Equals(predicate, default(TRelation)) || pn.Predicate.Equals(predicate)))
                {
                    yield return new Edge(start, pn.Predicate, pn.End);
                }
            }
        }

        /// <summary>
        /// Find all the outgoing edges from a vertex with a given predicate (or null)
        /// </summary>
        public IEnumerable<Edge> Back(TNode end, TRelation predicate)
        {
            PredicatePrevious endLink = null;
            if (EndIndexedEdges.TryGetValue(end, out endLink))
            {
                foreach (var pn in endLink.Where(pn =>
                    EqualityComparer<TRelation>.Default.Equals(predicate, default(TRelation)) || pn.Predicate.Equals(predicate)))
                {
                    yield return new Edge(pn.Start, pn.Predicate, end);
                }
            }
        }

        /// <summary>
        /// Find all the outgoing edges from a vertex with a given predicate (or null) and keep following edges of that type
        /// match only nodes of type T. Return the results as a tree (can be flattened using SelectMany).
        /// </summary>
        public Graph<T, TRelation> Successors<T>(TNode start, TRelation predicate)
            where T : class, TNode, IEquatable<T>
        {
            var visited = new HashSet<TNode>();
            var stack = new Stack<TNode>();
            stack.Push(start);

            var result = new Graph<T, TRelation>();

            while (stack.Count > 0)
            {
                start = stack.Pop();
                var outgoing = this.Follow(start, predicate);

                foreach (var edge in outgoing)
                {
                    T inEnd = edge.Start as T;
                    T outEnd = edge.End as T;
                    if (inEnd == null || outEnd == null) continue;

                    result.AddStatement(new Graph<T, TRelation>.Edge(inEnd, edge.Predicate, outEnd));

                    if (!visited.Contains(outEnd))
                    {
                        stack.Push(outEnd);
                        visited.Add(outEnd);
                    }
                }
            }
            return result;
        }

        /// <summary>
        /// Perform a search of the graph following a given predicate looking for nodes of type T
        /// </summary>
        public IEnumerable<T> Search<T>(TNode start, TRelation predicate, ISearchOrder<TNode> stack) where T : class, TNode
        {
            var visited = new HashSet<TNode>();
            stack.Enqueue(start);

            while (stack.Count > 0)
            {
                start = stack.Dequeue();
                var outgoing = this.Follow(start, predicate);

                foreach (var edge in outgoing)
                {
                    T outEnd = edge.End as T;
                    if (outEnd == null) continue;

                    if (!visited.Contains(outEnd))
                    {
                        stack.Enqueue(outEnd);
                        visited.Add(outEnd);
                        yield return outEnd;
                    }
                }
            }
        }

        /// <summary>
        /// Union two graphs
        /// </summary>
        public Graph<TNode, TRelation> Union(Graph<TNode, TRelation> other)
        {
            var result = new Graph<TNode, TRelation>();
            foreach (var edge in this.Edges.Concat(other.Edges).ToList())       // ToList for debugging
            {
                result.AddStatement(edge);
            }
            return result;
        }

        /// <summary>
        /// Intersect two graphs
        /// </summary>
        public Graph<TNode, TRelation> Intersect(Graph<TNode, TRelation> other)
        {
            var result = new Graph<TNode, TRelation>();
            // As a struct, this should just work - if they have the same start, Predicate and end
            var commonEdges = this.Edges.Intersect(other.Edges);
            foreach (var edge in commonEdges)
            {
                result.AddStatement(edge);
            }
            return result;
        }

        /// <summary>
        /// Topological sort approx
        /// </summary>
        public IEnumerable<TNode> TopologicalSortApprox()
        {
            var nodesWithNoIncomingLinks = Nodes.Except(StartIndexedEdges.SelectMany(e => e.Value).Select(pn => pn.End)).ToList();

            // L ← Empty list that will contain the sorted elements
            var l = new List<TNode>();
            //S ← Set of all nodes with no incoming edges
            var s = new Queue<TNode>(nodesWithNoIncomingLinks);

            var visited = new HashSet<TNode>(nodesWithNoIncomingLinks);

            //while S is non - empty do
            while (s.Count > 0)
            {
                //                    remove a node n from S
                var n = s.Dequeue();
                //                    add n to tail of L
                l.Add(n);
                //    for each node m with an edge e from n to m do
                foreach (var e in this.Follow(n, default(TRelation)))
                {
                    if (visited.Contains(e.End))
                        continue;
                    //                remove edge e from the graph
                    //                if m has no other incoming edges then
                    //                insert m into S
                    s.Enqueue(e.End);
                    visited.Add(e.End);
                }
            }
            //if graph has edges then
            //    return error(graph has at least one cycle)
            //else 
            //    return L(a topologically sorted order)
            return l;
        }

        public IEnumerator<TNode> GetEnumerator()
        {
            return this.GetNodes<TNode>().GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
}

GraphTests.cs

using System;
using System.Linq;
using NUnit.Framework;
using AboditUnits.Graph;
using FluentAssertions;

namespace AboditUnitsTest
{
    [TestFixture]
    public class GraphTests
    {
        Graph<string, Relation> A;
        Graph<string, Relation> B;
        Graph<string, Relation> C;

        static readonly string a = "a";
        static readonly string b = "b";
        static readonly string c = "c";
        static readonly string d = "d";
        static readonly string e = "e";
        static readonly string f = "f";

        public GraphTests()
        {
            A = new Graph<string, Relation>();
            A.AddStatement(a, Relation.RDFSType, b);
            A.AddStatement(a, Relation.RDFSType, c);
            A.AddStatement(b, Relation.RDFSType, d);
            A.AddStatement(c, Relation.RDFSType, e);
            A.AddStatement(d, Relation.RDFSType, f);
            A.AddStatement(e, Relation.RDFSType, f);

            Console.WriteLine("A");
            foreach (var edge in A.Edges)
            {
                Console.WriteLine("  " + edge);
            }

            B = new Graph<string, Relation>();
            B.AddStatement(a, Relation.RDFSType, b);
            B.AddStatement(a, Relation.RDFSType, c);
            B.AddStatement(b, Relation.RDFSType, d);

            Console.WriteLine("B");
            foreach (var edge in B.Edges)
            {
                Console.WriteLine("  " + edge);
            }

            C = new Graph<string, Relation>();
            C.AddStatement(a, Relation.RDFSType, f);

            Console.WriteLine("C");
            foreach (var edge in C.Edges)
            {
                Console.WriteLine("  " + edge);
            }
        }

        [Test]
        public void CanIntersectGraphs()
        {
            var AwithA = A.Intersect(A);
            var AwithB = A.Intersect(B);
            var BwithA = B.Intersect(A);
            var BwithC = B.Intersect(C);
            var CwithB = C.Intersect(B);

            AwithA.Nodes.Should().HaveCount(A.Nodes.Count(), "Intersection with self should preserve graph nodes");
            AwithA.Edges.Should().HaveCount(A.Edges.Count(), "Intersection with self should preserve graph edges");

            AwithB.Nodes.Should().HaveCount(B.Nodes.Count(), "B is a subgraph of A");
            BwithA.Nodes.Should().HaveCount(B.Nodes.Count(), "A is a supergraph of B");

            BwithC.Nodes.Should().HaveCount(0, "B is disjoint from C");
            CwithB.Nodes.Should().HaveCount(0, "C is disjoint from B");
        }

        [Test]
        public void UnionWithSelfIsIdentity()
        {
            var AwithA = A.Union(A);
            AwithA.Nodes.Should().HaveCount(A.Nodes.Count(), "Union with self should preserve graph nodes");
            AwithA.Edges.Should().HaveCount(A.Edges.Count(), "Union with self should preserve graph edges");
        }


        [Test]
        public void UnionWithSubgraph()
        {
            var AwithB = A.Union(B);
            var BwithA = B.Union(A);
            AwithB.Nodes.Should().HaveCount(A.Nodes.Count(), "B is a subgraph of A");
            BwithA.Nodes.Should().HaveCount(A.Nodes.Count(), "A is a supergraph of B");
        }

        [Test]
        public void UnionWithDisjoint()
        {
            var BwithC = B.Union(C);
            var CwithB = C.Union(B);
            BwithC.Nodes.Should().HaveCount(B.Nodes.Count() + C.Nodes.Count() - 1, "B is disjoint from C but shares one node");
            CwithB.Nodes.Should().HaveCount(B.Nodes.Count() + C.Nodes.Count() - 1, "C is disjoint from B but shares one node");

            BwithC.Edges.Should().HaveCount(B.Edges.Count() + C.Edges.Count(), "B is disjoint from C");
            CwithB.Edges.Should().HaveCount(B.Edges.Count() + C.Edges.Count(), "B is disjoint from C");
        }

        [Test]
        public void TopoSortSimple()
        {
            var aSorted = string.Join("", A.TopologicalSortApprox());
            aSorted.Should().Be("abcdef");

            //var fSorted = string.Join("", A.TopologicalSortApprox());
            //fSorted.Should().Be("f");

            //var cSorted = string.Join("", A.TopologicalSortApprox());
            //cSorted.Should().Be("cef");
        }
    }
}

ISearchOrder.cs

using System;
using System.Collections.Generic;

namespace AboditUnits.Graph
{
    public interface ISearchOrder<T>
    {
        int Count { get; }
        T Dequeue();
        void Enqueue(T value);
    }

    public class BreadthFirstSearch<T> : ISearchOrder<T>
    {
        private readonly Queue<T> queue = new Queue<T>();

        public int Count => queue.Count;

        public T Dequeue()
        {
            return queue.Dequeue();
        }

        public void Enqueue(T value)
        {
            queue.Enqueue(value);
        }
    }

    public class DepthFirstSearch<T> : ISearchOrder<T>
    {
        private readonly Stack<T> stack = new Stack<T>();

        public int Count => stack.Count;

        public T Dequeue()
        {
            return stack.Pop();
        }

        public void Enqueue(T value)
        {
            stack.Push(value);
        }
    }

    public class RandomFirstSearch<T> : ISearchOrder<T>
    {
        private readonly Random r = new Random();
        private readonly List<T> queue = new List<T>();

        public int Count => queue.Count;

        public T Dequeue()
        {
            int index = r.Next(queue.Count);
            var result = queue[index];
            queue.RemoveAt(index);
            return result;
        }

        public void Enqueue(T value)
        {
            queue.Add(value);
        }
    }
}

PredicateNext.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace AboditUnits.Graph
{
    public partial class Graph<TNode, TRelation>
    {
        /// <summary>
        /// A predicate, object pair pointing forwards (stored in a linked list)
        /// </summary>
        [DebuggerVisualizer("--{Predicate}-->{End}")]
        public class PredicateNext : IEnumerable<PredicateNext>
        {
            const int limit = 10000;

            public TRelation Predicate;
            public TNode End;
            public PredicateNext Next { get; set; }

            public PredicateNext(TRelation predicate, TNode end)
            {
                this.Predicate = predicate;
                this.End = end;
            }

            public IEnumerable<PredicateNext> Chain()
            {
                var current = this;
                int i = limit;
                while (current != null)
                {
                    yield return current;
                    current = current.Next;
                    if (i-- < 0) throw new Exception("Infinite loop possible");
                }
            }

            public IEnumerator<PredicateNext> GetEnumerator()
            {
                return this.Chain().GetEnumerator();
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return GetEnumerator();
            }
        }
    }
}

PredicatePrevious.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace AboditUnits.Graph
{
    public partial class Graph<TNode, TRelation>
    {
        /// <summary>
        /// A predicate, object pair pointing backwards (stored in a linked list)
        /// </summary>
        [DebuggerVisualizer("{Start}<--{Predicate}--")]
        public class PredicatePrevious : IEnumerable<PredicatePrevious>
        {
            const int limit = 10000;

            public TRelation Predicate;
            public TNode Start;
            public PredicatePrevious Next;

            public PredicatePrevious(TRelation predicate, TNode start)
            {
                this.Predicate = predicate;
                this.Start = start;
            }

            public IEnumerable<PredicatePrevious> Chain()
            {
                var current = this;
                int i = limit;
                while (current != null)
                {
                    yield return current;
                    current = current.Next;
                    if (i-- < 0) throw new Exception("Infinite loop possible");
                }
            }

            public IEnumerator<PredicatePrevious> GetEnumerator()
            {
                return this.Chain().GetEnumerator();
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return GetEnumerator();
            }
        }
    }
}

Relation.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace AboditUnits.Graph
{
    /// <summary>
    /// A relationship between two nodes in a graph, e.g. parent, child, antonym, synonym, ...
    /// </summary>
    [DebuggerDisplay("{name}")]
    public class Relation : IEquatable<Relation>
    {
        public string Name { get; }
        private Relation(string name) { this.Name = name; }

        private static readonly Dictionary<string, Relation> identityMap = new Dictionary<string, Relation>();

        public static Relation GetByName(string name)
        {
            Relation result;
            if (!identityMap.TryGetValue(name, out result))
            {
                result = new Relation(name);
                identityMap.Add(name, result);
            }
            return result;
        }

        public static readonly Relation Antonym = GetByName("antonym");
        public static readonly Relation Synonym = GetByName("synonym");
        
        public static readonly Relation MemberMeronymOf = GetByName("memberMeronymOf");        // mereonym
        public static readonly Relation PartMeronymOf = GetByName("partMeronymOf");        // mereonym
        public static readonly Relation HolonymOf = GetByName("holonymOf");      // holonym

        public static readonly Relation SimilarTo = GetByName("similarTo");

        public static readonly Relation ClassifiedByTopic = GetByName("classifiedByTopic");
        public static readonly Relation ClassifiedByRegion = GetByName("classifiedByRegion");
        public static readonly Relation ClassifiedByUsage = GetByName("classifiedByUsage");
        public static readonly Relation PertainsTo = GetByName("pertainsTo");
        public static readonly Relation DerivationallyRelated = GetByName("derivationallyRelated");
        public static readonly Relation Related = GetByName("related");
        public static readonly Relation Domain = GetByName("domain");
        public static readonly Relation Range = GetByName("range");

        public static readonly Relation WordFor = GetByName("wordFor");

        public static readonly Relation Superlative = GetByName("superlative");
        public static readonly Relation Comparative = GetByName("comparative");
        public static readonly Relation NounForm = GetByName("noun");
        public static readonly Relation VerbForm = GetByName("verb");
        public static readonly Relation AdjectiveForm = GetByName("adjective");
        public static readonly Relation AdverbForm = GetByName("adverb");
        public static readonly Relation PastTense = GetByName("pastTense");
        public static readonly Relation FutureTense = GetByName("futureTense");
        public static readonly Relation PastParticiple = GetByName("pastParticple");
        public static readonly Relation PresentParticiple = GetByName("presentParticiple");
        public static readonly Relation FirstPersonSingular = GetByName("firstPersonSingular");
        public static readonly Relation FirstPersonPlural = GetByName("firstPersonPlural");

        public static readonly Relation SingularForm = GetByName("singular");
        public static readonly Relation PluralForm = GetByName("plural");

        public static readonly Relation RDFSType = GetByName("type");

        public bool Equals(Relation other)
        {
            // Can use reference equals since identity mapped
            return ReferenceEquals(this, other);
        }

        public override string ToString()
        {
            return "--" + this.Name + "-->";
        }
    }
}