0

I'm trying to create a Graph data structure and sort it using Topological Sorting. My code is as below:

public class Node<T>
{
    // Private member-variables
    private T data;
    private NodeList<T> neighbors = null;

    public Node() { }
    public Node(T data) : this(data, null) { }
    public Node(T data, NodeList<T> neighbors)
    {
        this.data = data;
        this.neighbors = neighbors;
    }

    public T Value
    {
        get
        {
            return data;
        }
        set
        {
            data = value;
        }
    }

    protected NodeList<T> Neighbors
    {
        get
        {
            return neighbors;
        }
        set
        {
            neighbors = value;
        }
    }
}

public class NodeList<T> : List<Node<T>>
{
    public NodeList() : base() { }

    public Node<T> FindByValue(T value)
    {
        // search the list for the value
        foreach (Node<T> node in this)
            if (node.Value.Equals(value))
                return node;

        // if we reached here, we didn't find a matching node
        return null;
    }
}

public class GraphNode<T> : Node<T>
{
    private List<int> costs = null;

    public GraphNode() : base()
    {
    }

    public GraphNode(T value) : base(value)
    {
    }
    public GraphNode(T value, NodeList<T> neighbors) : base(value, neighbors)
    {
    }

    new public NodeList<T> Neighbors
    {
        get
        {
            if (base.Neighbors == null)
                base.Neighbors = new NodeList<T>();
            return base.Neighbors;
        }
    }

    public List<int> Costs
    {
        get
        {
            if (costs == null)
                costs = new List<int>();
            return costs;
        }
    }
}

public class Graph<T>
{
     private NodeList<T> nodeSet;
     public List<GraphNode<T>> Sort(Graph<T> graph, Func<GraphNode<T>, IEnumerable<GraphNode<T>>> neighBours)
    {
        var sorted = new List<GraphNode<T>>();
        var visited = new Dictionary<GraphNode<T>, bool>();

        foreach (var item in graph.Nodes)
        {
            var _tempItem = item as GraphNode<T>;
            Visit(_tempItem, neighBours, sorted, visited);
        }

        return sorted;
    }

    public void Visit(GraphNode<T> item, Func<GraphNode<T>, IEnumerable<GraphNode<T>>> neighBours, List<GraphNode<T>> sorted, Dictionary<GraphNode<T>, bool> visited)
    {
        bool inProcess = false;
        var alreadyVisited = visited.TryGetValue(item, out inProcess);

        if (alreadyVisited)
        {
            if (inProcess)
            {
                throw new Exception("Cyclic dependency found.");
            }
        }
        else
        {
            visited[item] = true;

            var dependencies = neighBours(item);
            if (dependencies != null)
            {
                foreach (var dependency in dependencies)
                {
                    Visit(dependency, neighBours, sorted, visited);
                }
            }

            visited[item] = false;
            sorted.Add(item);
        }
    }
}

The call to Sort method is made as below:

   List<GraphNode<string>> lstSorted = _graph.Sort(_graph, x => x.Neighbors);

But I'm getting below error in the call for x.Neighbors:

Cannot convert lambda expression to intended delegate type because some of the return types in the block are not implicitly convertible to the delegate return type

Can someone please tell me how to fix this?

Pratik Gaikwad
  • 1,526
  • 2
  • 21
  • 44
  • 1
    The error message is _very_ clear. What is it _specifically_ that you don't understand? It is explaining in precise detail that your `x.Neighbors` expression (i.e. which defines the return type of the lambda expression) is not implicitly convertible to the `IEnumerable` return type required by the method for that parameter's `Func` type. It's impossible to provide a specific answer without a good [mcve] that reliably reproduces the problem, but most likely your question is a duplicate of all the others that ask why inheritance doesn't apply to generic type parameters. – Peter Duniho Nov 12 '16 at 00:39
  • 4
    The basic issue here is that your parameter requires `IEnumerable>`, but the `Neighbors` property returns a `NodeList`, which implements `IEnumerable>` instead. `IEnumerable` does support covariance (you can pass `IEnumerable>` when the callee requires `IEnumerable>`), but not the contravariance that would be required to go the other way (i.e. to pass `IEnumerable>` when you require `IEnumerable>`). See the marked duplicate for a short answer to the issue. Search on "cast generic list" for more details. – Peter Duniho Nov 12 '16 at 00:50
  • Another good Q&A to read would be https://stackoverflow.com/questions/10479046/why-does-ienumerablet-only-have-the-out-covariant-flag-and-not-in-c – Peter Duniho Nov 12 '16 at 00:53
  • 1
    Basically, you can not replace inheriting class with inherited class, because it is considered that inheriting class complements inherited class and by replacing the child with the parent you may lose functionality, fields, props. – αNerd Nov 12 '16 at 01:01
  • @αNerd, Thank you for stating it in simple terms! – Pratik Gaikwad Nov 12 '16 at 01:17
  • @PeterDuniho, Thanks for pointing out the mistake. I was able to solve the issue.In case, I want to use property of Inherited class(in this case GraphNode), how can I do that? – Pratik Gaikwad Nov 12 '16 at 01:18
  • @αNerd, In case, I want to use property of Inherited class(in this case GraphNode), how can I do that? – Pratik Gaikwad Nov 12 '16 at 01:22
  • You can access it through the inherited class or any of its childs(in case it has any). GraphNode inherits Node which is the inherited class actually. GraphNode is child of Node. – αNerd Nov 12 '16 at 01:25
  • I think the simplest solution is to create GraphNodeList which inherits List> and Neighbours prop in GraphNode should return new GraphNodeList. Also I noticed that you don't initalize nodeSet in Graph class which will cause NullReferenceException later. – αNerd Nov 12 '16 at 01:44

0 Answers0