Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Interdependent Generic Classes?

At the bottom of this post is an example of how a solution might look, although clearly the example is invalid because it used BaseNode and BaseEdge without providing types when inheriting.

I'm trying to create an abstract graph class, where both the node class and the edge class must also be abstract. Individual implementations of each class will add methods and properties as well as implementing abstract methods from the base classes.

I have an existing solution that merely uses the base types for everything, however I quickly found myself in a mess of casting.

Only the graph class must be publicly exposed, although the others can be, so solutions involving node and edge classes being nested within the graph class are acceptable.

Is there any way in which this can be structured such that all properties are of the proper types without expensive casts anywhere in the system? It's more important that implementing classes don't have to cast everywhere, but performance is definitely a concern in this case (it actually is) so I would rather avoid casting altogether.

abstract class Graph<TNode, TEdge>
    where TNode : BaseNode<TEdge>
    where TEdge : BaseEdge<TNode>
{
    TNode root;
    List<TNode> nodes;
    List<TEdge> edges;

    public abstract float process();
}

abstract class BaseNode<TEdge>
    // THIS HERE IS THE PROBLEM
    where TEdge : BaseEdge
{
    List<TEdge> inputs;

    public List<TEdge> Inputs
    {
        get
        {
            return inputs;
        }
    }

    public abstract float process();
}

abstract class BaseEdge<TNode>
    // THIS HERE IS THE PROBLEM
    where TNode : BaseNode
{
    TNode from;
    TNode to;

    public TNode To
    {
        get
        {
            return to;
        }
    }

    public TNode From
    {
        get
        {
            return from;
        }
    }

    public abstract float process();
}

@Marceln wanted to see a my existing implementation, so here it is. It's just the same thing without the generics.

abstract class Graph
{
    BaseNode root;
    List<BaseNode> nodes;
    List<BaseEdge> edges;

    public abstract float process();
}

abstract class BaseNode
{
    List<BaseEdge> inputs;

    public List<BaseEdge> Inputs
    {
        get
        {
            return inputs;
        }
    }

    public abstract float process();
}

abstract class BaseEdge
{
    BaseNode from;
    BaseNode to;

    public BaseNode To
    {
        get
        {
            return to;
        }
    }

    public BaseNode From
    {
        get
        {
            return from;
        }
    }

    public abstract float process();
}

Where an implementation of a Node might look like this:

class ImplementedNode : BaseNode
{
    public override float process()
    {
        foreach (ImplementedEdge edge in this.Inputs)
        {
            // Something
        }
    }

    public bool getImplementationSpecificInfo()
    {
        return true;
    }
}
like image 527
NodeDear Avatar asked Oct 20 '22 04:10

NodeDear


2 Answers

If you are willing to loosen up the constraints on BaseEdge and BaseNode then you could do something like in the example below.

I have introduced the interfaces INode and IEdge just so whoever works with this isn't allowed to create concrete subclasses of BaseEdge and BaseNode with any type.

public interface INode
{

}

public interface IEdge
{

}

public abstract class Graph<TNode, TEdge>
    where TNode : BaseNode<TEdge>
    where TEdge : BaseEdge<TNode>
{
    public TNode Root { get; set; }
    public List<TNode> Nodes { get; set; }
    public List<TEdge> Edges { get; set; }
}

public abstract class BaseNode<TEdge> : INode where TEdge: IEdge
{
    List<TEdge> inputs;

    public List<TEdge> Inputs
    {
        get
        {
            return inputs;
        }
    }

    public abstract float process();
}

public abstract class BaseEdge<TNode> : IEdge where TNode: INode
{
    TNode from;
    TNode to;

    public TNode To
    {
        get
        {
            return to;
        }
    }

    public TNode From
    {
        get
        {
            return from;
        }
    }

    public abstract float process();
}


public class ConcreteNode : BaseNode<ConcreteEdge>
{
    public override float process()
    {
        return 0;
    }
}

public class ConcreteEdge : BaseEdge<ConcreteNode>
{
    public override float process()
    {
        return 0;
    }
}

public class ConcreteGraph : Graph<ConcreteNode, ConcreteEdge>
{

}
like image 85
Marcel N. Avatar answered Oct 22 '22 19:10

Marcel N.


UPDATE

Another answer, which provides for some type safety.

public interface IGraph<TNode, TEdge>
    where TNode : INode
    where TEdge : IEdge
{
    TNode Root { get; set }
    List<TNode> Nodes { get; set; }
    List<TEdge> Edges { get; set; }
}

public interface INode
{
    List<IEdge> Edges { get; set; }
}

public interface INode<TEdge> where TEdge : IEdge
{
    List<TEdge> Edges { get; set; }
}

public interface IEdge
{
    INode To { get; set; }
    INode From { get; set; }
}

public interface IEdge<TNode> where TNode : INode
{
    TNode To { get; set; }
    TNode From { get; set; }
}



public class MyGraph : IGraph<MyNode, MyEdge>
{
    public MyGraph(MyNode root)
    {
        Root = root;
    }

    public MyNode Root { get; set; }
    public List<MyNode> Nodes { get; set; }
    public List<MyEdge> Edges { get; set; }
}

public class MyNode : INode<MyEdge>, INode
{
    public List<MyEdge> Edges { get; set; }

    List<IEdge> INode.Edges
    {
        get { return this.Edges; }
        set { this.Edges = value; }
    }
}

public class MyEdge : IEdge<MyNode>, IEdge
{
    public MyNode To { get; set; }
    public MyNode From { get; set; }

    INode IEdge.To
    {
        get { return this.To; }
        set { this.To = value; }
    }

    INode IEdge.From
    {
        get { return this.From; }
        set { this.From = value; }
    }
}

This gave me no compile errors.

UPDATE

This answer does not work. But, I'm leaving it here for the comments that appear with it.


@NodeDear, I think your original example had it correct when Graph was generic:

Graph<TNode, TEdge> where TNode : BaseNode<TEdge>, TEdge : BaseEdge<TNode>

In the example you provided for @marceln, the Graph class is not generic. Therefore, you'll have to do all kinds of casting. with the generic version though:

public abstract Graph<TNode, TEdge>
    where TNode : BaseNode<TEdge>
    where TEdge : BaseEdge<TNode>
{
    public TNode Root { get; set; }
    public List<TNode> Nodes { get; set; }
    public List<TEdge> Edges { get; set; }
}

public abstract BaseNode<TEdge> where TEdge : BaseEdge<BaseNode<TEdge>>
{
    public List<TEdge> Edges { get; set; }
}

public abstract BaseEdge<TNode> where TNode : BaseNode<BaseEdge<TNode>>
{
    public TNode To { get; set; }
    public TNode From { get; set; }
}


public class MyNode : BaseNode<TEdge> where TEdge : BaseEdge<MyNode>
{
    ...
}

public class MyEdge : BaseEdge<TNode> where TNode : BaseNode<MyEdge>
{
    ...
}

public class MyGraph : Graph<MyNode, MyEdge>
{
    ...
}

public MyGraph<MyNode, MyEdge> g = new MyGraph<MyNode, MyEdge>();
List<MyEdge> edges = g.Nodes[0].Edges;
MyNode toNode = g.Edges[0].To;

This allows any type derived from Graph<TNode, TEdge> to have strongly-typed nodes and edges, which is what the OP is looking for.

like image 41
fourpastmidnight Avatar answered Oct 22 '22 19:10

fourpastmidnight