Bob the (Graph) Builder

Question

I'm starting a project in which I'll generate random graphs and use algorithms to solve them. The first necessary step is obviously to build a graph.

My graph has the following characteristics :

It can be directional or not, implying that the Edge between NodeA and NodeB can be traversed from B to A if the Graph is NonDirectional.
The Edge can be "weighted", meaning that there's an int value linked to an edge, which will be used for some graph algorithms.

At the moment, I have mostly tested the non directional weighted graph, so it's the one I'll put for review. I hav removed the header comments from the class/methods as I have multiple classes to show.

public class Node : IEquatable<Node>
{
    public string Name { get; }

    public Node(string name)
    {
        if (String.IsNullOrWhiteSpace(name)) throw new ArgumentException("Name cannot be null or empty", nameof(name));

        Name = name;
    }

    public override bool Equals(object obj)
    {
        return Equals(obj as Node);
    }

    public bool Equals(Node other)
    {
        return Name == other.Name;
    }

    public override int GetHashCode()
    {
        return Name.GetHashCode() * 23; 
    }

    public override string ToString()
    {
        return $"({this.GetType().Name}) - Name : {Name}";
    }
}

Note : The PriorityQueueNode base class is used in the algorithms, but it is not used anywhere in this review. The AssociationId is used in case of a non directional graph, it is used to see if two edges are from the same... association (A to B and B to A).

public class Edge : PriorityQueueNode, IEquatable<Edge>
{
    private readonly Lazy<int> computedHashCode;

    public Guid AssociationId { get; }
    public Node From { get; }
    public Node To { get; }

    public Edge(Node from, Node to, Guid associationId)
    {
        if (to == null) throw new ArgumentNullException(nameof(to));
        if (from == null) throw new ArgumentNullException(nameof(from));

        From = from;
        To = to;
        AssociationId = associationId;

        //Since Edge is immutable, hash can be computed once.
        computedHashCode = new Lazy<int>(() => (From.GetHashCode() * 17) ^ (To.GetHashCode() * 17) ^ (AssociationId.GetHashCode() * 17));
    }

    public bool ConnectsSameNode(Edge edge)
    {
        if (edge == null) throw new ArgumentNullException(nameof(edge));

        if (AssociationId == edge.AssociationId) return true;

        bool connectsSameFrom = edge.From.Equals(From) || edge.To.Equals(From);

        return connectsSameFrom && (edge.From.Equals(To) || edge.To.Equals(To));
    }

    public override bool Equals(object obj)
    {
        return Equals(obj as Edge);
    }

    public bool Equals(Edge edge)
    {
        if (edge == null) return false;

        return AssociationId == edge.AssociationId && From.Equals(edge.From) && To.Equals(edge.To);
    }

    public override int GetHashCode()
    {
        return computedHashCode.Value;
    }

    public override string ToString()
    {
        return $"({this.GetType().Name}) - From : {From.Name}, To : {To.Name}, AssociationId : {AssociationId}";
    }
}

public class WeightedEdge : Edge, IEquatable<WeightedEdge>, IComparable<WeightedEdge>
{
    public int Weight { get; }

    public WeightedEdge(Node from, Node to, int weight, Guid associationId)
        : base(from, to, associationId)
    {
        if (weight <= 0) throw new ArgumentException($"{nameof(weight)} must be higher than zero", nameof(weight));

        Weight = weight;
    }

    public int CompareTo(WeightedEdge other)
    {
        if (other == null) throw new ArgumentNullException("other");

        int compareValue = Math.Sign(Weight - other.Weight);

        //Compare AssociationId because something needs to decide the priority and it can't be random.
        return compareValue == 0 ? AssociationId.CompareTo(other.AssociationId) : compareValue;
    }

    public override bool Equals(object obj)
    {
        return Equals(obj as WeightedEdge);
    }

    public bool Equals(WeightedEdge edge)
    {
        return base.Equals(edge) && edge.Weight == Weight;
    }

    public override int GetHashCode()
    {
        return base.GetHashCode() ^ (Weight.GetHashCode() * 13);
    }

    public override string ToString()
    {
        return $"{base.ToString()}, Weight : {Weight}";
    }
}

That is it for the structure of a Graph. Now, the Graph class. I use a ICollectionDictionary<Node,T> to hold my graph, the interface is defined as this :

public interface ICollectionDictionary<T,TK> : IDictionary<T, ICollection<TK>>
{
    void AddToCollection(T key, TK value);

    /// <summary>
    /// Creates a new empty ICollection for the T key.
    /// </summary>
    /// <param name="key">Key.</param>
    void InitializeKeyCollection(T key);
}

I'll leave the implementation out of the review as the question gets long already, but I'll add a link to the GitHub repo at the end.

public interface IGraph<T> where T : Edge
{
    bool IsDirectional { get; }
    int NodesCount { get; }
    int EdgesCount { get; }
    IEnumerable<Node> Nodes { get; }
    IEnumerable<T> GetEdges(Node node);
    IEnumerable<T> GetAllUniquesEdges();
}

public class Graph<T> : IGraph<T> where T : Edge
{
    private readonly ICollectionDictionary<Node, T> _map;
    private bool _isDirectional;

    public int NodesCount => _map.Keys.Count;
    public int EdgesCount => _map.Values.Count;

    public bool IsDirectional => _isDirectional;

    public IEnumerable<Node> Nodes => _map.Keys.ToList();

    internal Graph(ICollectionDictionary<Node, T> map, bool isDirectional)
    {
        if (map == null) throw new ArgumentNullException(nameof(map));
        _map = map;
        _isDirectional = isDirectional;
    }

    public IEnumerable<T> GetEdges(Node node)
    {
        if (node == null) throw new ArgumentNullException("node");

        _map.InitializeKeyCollection(node);
        return _map[node];
    }

    public IEnumerable<T> GetAllUniquesEdges()
    {
        var associationIds = new HashSet<Guid>();
        foreach (var item in _map.Values.SelectMany(v => v)) 
        {
            //If graph is non directional, we don't want the two edges A->B & B->A.
            if (!associationIds.Add(item.AssociationId)) continue;

            yield return item;
        }
    }
}

The creation of a Graph is somehow complex, so I created a IGraphBuilder<T>.

public interface IGraphBuilder<T> where T : Edge
{
    IEnumerable<Node> NodesInGraph { get; }
    IGraph<T> Build();
}

public interface IWeightedGraphBuilder : IGraphBuilder<WeightedEdge>
{
    IWeightedGraphBuilder AddEdge(Node a, Node b, int weight);
}

public class WeightedGraphBuilder : IWeightedGraphBuilder
{
    private ICollectionDictionary<Node, WeightedEdge> _map;
    private bool _hasBeenBuilt;
    private bool _isDirectional;

    public IEnumerable<Node> NodesInGraph => _map.Keys.ToList();
    public bool GeneratedGraphIsDirectional => _isDirectional;

    public WeightedGraphBuilder(bool isDirectional)
    {
        _isDirectional = isDirectional;
        _map = new CollectionDictionary<Node, WeightedEdge>();
        _hasBeenBuilt = false;
    }

    public IWeightedGraphBuilder AddEdge(Node nodeA, Node nodeB, int weight)
    {
        if (nodeA == null) throw new ArgumentNullException("a");

        _map.InitializeKeyCollection(nodeA);

        if (nodeB == null) { return this; }

        _map.InitializeKeyCollection(nodeB);

        ICollection<WeightedEdge> edgesA = _map[nodeA];

        var associationId = Guid.NewGuid();
        var edgeAToB = new WeightedEdge(nodeA, nodeB, weight, associationId);

        edgesA.Add(edgeAToB);

        if (!_isDirectional)
        {
            var edgesB = _map[nodeB];
            var edgeBToA = new WeightedEdge(nodeB, nodeA, weight, associationId);
            edgesB.Add(edgeBToA);
        }

        return this;
    }

    public IGraph<WeightedEdge> Build()
    {
        if (_hasBeenBuilt) throw new InvalidOperationException("Graph has already been built using this builder");
        _hasBeenBuilt = true;

        return new Graph<WeightedEdge>(_map, _isDirectional);
    }
}

An example use would be :

class Example
{
    void Test()
    {
        IWeightedGraphBuilder bob = new WeightedGraphBuilder(false);
        bob.AddEdge(new Node("a"), new Node("b"), 3);
        bob.AddEdge(new Node("a"), new Node("c"), 2);
        bob.AddEdge(new Node("b"), new Node("d"), 10);

        IGraph<WeightedEdge> graph = bob.Build();
    }
}

I've unit tested this code (except the builder, but it works according to the unit test that uses it, tests will come later, oops). I want to know if there's anything smelly in there or things that could be optimized.

The full code can be found on https://github.com/topinfrassi01/GraphTheories

Martin · Accepted Answer · 2016-01-01 00:23:06Z

3

Node:

Equals(Node other) will throw NullReferenceException when called with null
GetHashCode() should only return Name.GetHashCode() - the multiplication can cause an overflow and two distinct values of the original hash can get mapped to the same value
ToString() instead of this.GetType().Name for the name of the type you can use nameof(Node) which is actually a string literal

Edge:

If I understand correctly that the point of having Guid AssociationId that is set on creation is to label directed edges x -> y and y -> x with the same Guid then I would suggest an alternative implementation:

public bool ConnectsSameNodes(Edge edge)
{
    if (edge == null)
    {
        throw new ArgumentNullException(nameof(edge));
    }

    return (From.Equals(edge.From) && To.Equals(edge.To)) ||
           (From.Equals(edge.To) && To.Equals(edge.From));
}

This way, Guid AssociationId can be removed from the class completely.

answered Jan 1, 2016 at 0:23

Martin

4483 silver badges9 bronze badges

\$\begingroup\$ I use this.GetType().Name to deal with the inheritance. The hashcode is explained here and the AssociationId is used to deal with cases where two distinct edges connect the same nodes : A->B and A->B would be possible. \$\endgroup\$

IEatBagels
– IEatBagels

2016-01-01 19:42:02 +00:00
Commented Jan 1, 2016 at 19:42
\$\begingroup\$ Regarding the GetHashCode(), the link only explains why multiplication by primes is used to combine multiple hash codes of multiple fields into one hash code. When you are using only one hash code of a single field, it is better to just return it. You achieve better performance and better distribution that way. \$\endgroup\$

Martin
– Martin

2016-01-01 20:17:56 +00:00
Commented Jan 1, 2016 at 20:17
\$\begingroup\$ Fine by me, you're right! :) \$\endgroup\$

IEatBagels
– IEatBagels

2016-01-01 20:19:08 +00:00
Commented Jan 1, 2016 at 20:19
\$\begingroup\$ @Martin mind elaborating on what you mean by "nameof() is actually a string literal"? \$\endgroup\$

RubberDuck
– RubberDuck

2016-01-02 12:07:24 +00:00
Commented Jan 2, 2016 at 12:07
3

\$\begingroup\$ @RubberDuck Sure, when you write nameof(Node) what actually gets compiled into your assembly is just the string literal "Node". You can check this by using a tool like ILSpy for decompiling IL. When you decompile an assembly that used nameof(Node) in C# code, you will only see "Node". \$\endgroup\$

Martin
– Martin

2016-01-02 15:47:47 +00:00
Commented Jan 2, 2016 at 15:47

| Show 1 more comment

IEatBagels · Accepted Answer · 2016-01-01 20:21:00Z

Was I so naive in 2015! I had a flash during my sleep. Why would AddEdge have the possibility to add a single Node? That seems to break the Single Responsibility Principle. To fix this problem, I added an AddNode method, which initializes an empty collection for the _map's Node. The AddEdge method then calls AddNode on both the nodes of the new Edge.

public IWeightedGraphBuilder AddNode(Node node)
{
    if (node == null) throw new ArgumentNullException(nameof(node));

    _map.InitializeKeyCollection(node);

    return this;
}

public IWeightedGraphBuilder AddEdge(Node nodeA, Node nodeB, int weight)
{
    if (nodeA == null) throw new ArgumentNullException(nameof(nodeA));
    if (nodeB == null) throw new ArgumentNullException(nameof(nodeB));

    AddNode(nodeA);
    AddNode(nodeB);

    //The rest is the same
}

This way, the AddEdge method cannot add a single node like it's done in the previous implementation, this keeps this method's responsibility count to one.

Stack Exchange Network

Bob the (Graph) Builder

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Bob the (Graph) Builder

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions