Magi med Generiske klasser

Den mest logiske kosntruktion er vel at man starter med at opbygge en graf ved først at definere noderene, og så i anden omgang at koble dem sammen 2-og-2 med edges.

Men er Noder og Edges generiske i denne sammenhæng? Har du behov for at kunne sætte forskellige typer Node'r og Edge's ind i din graf?

Måske noget i denne stil?

    class Graph<TTime, TPlace>
    {
        private List<Node<TTime, TPlace>> nodes;
        private List<Edge<TTime, TPlace>> edges;

        public Graph()
        {
            nodes = new List<Node<TTime, TPlace>>();
            edges = new List<Edge<TTime,TPlace>>();
        }

        public int AddNode(Node<TTime, TPlace> node)
        {
            nodes.Add(node);
            return nodes.IndexOf(node);
        }

        public int AddEdge(Edge<TTime, TPlace> edge, int nodeId1, int nodeId2)
        {
            edge.node1 = nodes[nodeId1];
            edge.node2 = nodes[nodeId2];           

            edges.Add(edge);
            return edges.IndexOf(edge);
        }
    }

    class Node<TTime, TPlace>
    {
    }

    class Edge<TTime, TPlace>
    {
        public Node<TTime, TPlace> node1;
        public Node<TTime, TPlace> node2;
    }

Jeg har leget med en idé tilsvarende dit forslag. Grunden til at jeg gerne vil "udskifte", hvilke Nodes og Edges grafen bruger et for at undgå typecasting.

Jeg vil eksempelvis gerne understøtte CapacitatedEdges. Denne type er helt magen til Edge, men tilføjer instans variablen, double capacity.

Den oplagte løsning er derfor at lade CapacitatedEdge nedarve fra Edge.

Graf klassen vil godt kunne sluge CapacitatedEdge klassen som input til AddEdge metoden, men når en Algoritme skal til at køre på en graf instans, så skal der typecastes, hver gang man skal have fat i en Edge med en accesor. Ellers kan man ikke få fat i capacitets variablen i den nedarvede klasse.

Kan du se mit problem. Det er derfor jeg gerne vil bruge generics til at vælge ved compile time hvilken slags nodes og edges, der skal bruges.

Så sådan?

    class Program
    {
        static void Main(string[] args)
        {
            Graph<T1, T2, MyEdge<T1, T2>, MyNode<T1, T2>> graph =
                new Graph<T1, T2, MyEdge<T1, T2>, MyNode<T1, T2>>();

            MyNode<T1, T2> node = new MyNode<T1, T2>();
            int nodeId1 = graph.AddNode(node);

            node = new MyNode<T1,T2>();
            int nodeId2 = graph.AddNode(node);

            MyEdge<T1, T2> edge = new MyEdge<T1, T2>();
            int edgeId = graph.AddEdge(edge, nodeId1, nodeId2);
        }
    }

    struct T1 { }
    struct T2 { }

    class Graph<TTime, TPlace, TEdge, TNode>
        where TEdge : Edge<TTime, TPlace>
        where TNode : Node<TTime, TPlace>
    {
        private List<TNode> nodes;
        private List<TEdge> edges;

        public Graph()
        {
            nodes = new List<TNode>();
            edges = new List<TEdge>();
        }

        public int AddNode(TNode node)
        {
            nodes.Add(node);
            return nodes.IndexOf(node);
        }

        public int AddEdge(TEdge edge, int nodeId1, int nodeId2)
        {
            edge.node1 = nodes[nodeId1];
            edge.node2 = nodes[nodeId2];           

            edges.Add(edge);
            return edges.IndexOf(edge);
        }
    }

    class Node<TTime, TPlace>
    {
    }

    class MyNode<TTime, TPlace> : Node<TTime, TPlace>
    {
    }

    class Edge<TTime, TPlace>
    {
        public Node<TTime, TPlace> node1;
        public Node<TTime, TPlace> node2;
    }

    class MyEdge<TTime, TPlace> : Edge<TTime, TPlace>
    {
        public Node<TTime, TPlace> node1;
        public Node<TTime, TPlace> node2;
    }

Notationen:

class Graph<TTime, TPlace, TEdge, TNode>
        where TEdge : Edge<TTime, TPlace>
        where TNode : Node<TTime, TPlace>
{
    ...

forcere at TTime og TEdge skal arve fra Edge og Node klasserne.

Det ser rigtig fornuftigt ud. Takker.

Mit problem med cirkulær gensidig afhængighed af Nodes og Edges skyldes en idé om, at man skulle sørge for, at brugere af graf biblioteket skulle forhindres i at benytte visse kombinationer af Nodes og Edges. Så hvis man lagde sig fast på 1 type Node, så giver det kun mening at oprette en tilsvarende bestemt delmængde af Edge instanserne.

Jeg er ikke længere overbevist om det giver mening, men for egen lærings skyld kunne det være sjovt at vide, hvordan man kunne begrænse, hvilke Node-Edge kombinationer, der var mulige at smide ind i grafen.

Men smid et svar Nielle. Jeg takker for input.

Svar :^)

Ups. Der var jeg vidst for hurtig.

Hvis grafen skal være en adjacency graph (Edges gemmes i Nodes), så skal Node klassen indeholde en liste af edges.

class Node<TTime, TPlace>
{
  List<Edge<TTime,Place>> adjacencylist;
  ...
  public void AddEdge(Edge<TTime,TPlace> edge) { ... }
}

Så jeg er stadig ikke sluppet af med typecasting. Jeg har defineret listen og add metoden til at acceptere base klassen for Edge. Så når jeg arbejder med MyEdges, og eksempelvis skal returnere en Enumerator eller bare adjacencylisten direkte fra Noden, så er jeg nødt til at typecaste for at få MyEdges ud.

Det samme gør sig gældende for Edges, der gemmer 2 x Node<TTime, TPlace>. Hvis jeg arbejder med MyNodes, så skal jeg igen caste.

Hvad dælan gør man så?

Det er i essensen den cirkulær gensidighed jeg nævnte i det oprindelige spørgsmål. Man kan ikke give Node typen, som argument til Edge og samtidig give Edge som argument til Node.

Så ender man nemlig i Graph<MyNode<MyEdge<MyNode<MyEdge<MyNode............

Dough. What to do. Jeg finder nogle flere point frem til gode forslag

Den ville jeg vælge at implementere sådan:

    class Program
    {
        static void Main(string[] args)
        {
            Graph<T1, T2, MyEdge<T1, T2>, MyNode<T1, T2>> graph =
                new Graph<T1, T2, MyEdge<T1, T2>, MyNode<T1, T2>>();

            MyNode<T1, T2> node = new MyNode<T1, T2>();
            int nodeId1 = graph.AddNode(node);

            node = new MyNode<T1,T2>();
            int nodeId2 = graph.AddNode(node);

            MyEdge<T1, T2> edge = new MyEdge<T1, T2>();
            int edgeId = graph.AddEdge(edge, nodeId1, nodeId2);
        }
    }

    struct T1 { }
    struct T2 { }

    class Graph<TTime, TPlace, TEdge, TNode>
        where TEdge : Edge<TTime, TPlace>
        where TNode : Node<TTime, TPlace>
    {
        private List<TNode> nodes;
        private List<TEdge> edges;

        public Graph()
        {
            nodes = new List<TNode>();
            edges = new List<TEdge>();
        }

        public int AddNode(TNode node)
        {
            nodes.Add(node);
            return nodes.IndexOf(node);
        }

        public int AddEdge(TEdge edge, int nodeId1, int nodeId2)
        {
            edge.Node1 = nodes[nodeId1];
            edge.Node2 = nodes[nodeId2];           

            edges.Add(edge);
            return edges.IndexOf(edge);
        }
    }

    class Node<TTime, TPlace>
    {
        private List<Edge<TTime, TPlace>> adjacencylist;

        public Node()
        {
            adjacencylist = new List<Edge<TTime, TPlace>>();
        }

        public void AddEdge(Edge<TTime, TPlace> edge)
        {
            adjacencylist.Add(edge);
        }
    }

    class MyNode<TTime, TPlace> : Node<TTime, TPlace>
    {
    }

    class Edge<TTime, TPlace>
    {
        private Node<TTime, TPlace> node1;
        public Node<TTime, TPlace> Node1
        {
            get { return node1; }
            set
            {
                node1 = value;
                node1.AddEdge(this);
            }
        }

        private Node<TTime, TPlace> node2;
        public Node<TTime, TPlace> Node2
        {
            get { return node2; }
            set
            {
                node2 = value;
                node2.AddEdge(this);
            }
        }
    }

    class MyEdge<TTime, TPlace> : Edge<TTime, TPlace>
    {
    }

Prøv at smide en indexer ind i Node klassen:

class Node
{
  ...
  public Edge<TTime, TPlace> this[int index]
  {
      get { return adjacencyList[index]; }
  }
}

Og så prøv at oprette en fromNode og en toNode af typen MyNode fra main og forbind dem med en MyEdge. Da vi arbejeder med adjacencyList repræsentation, gemmes Edges i fra-Nodes. Så hvis du kalder fromNode[0] skal du få returneret din Edge.
 
static void Main(string[] args)
{
  Graph<T1, T2, MyEdge<T1, T2>, MyNode<T1, T2>> graph =
              new Graph<T1, T2, MyEdge<T1, T2>, MyNode<T1, T2>>();

  MyNode<T1, T2> fromNode = new MyNode<T1, T2>();
  int nodeId1 = graph.AddNode(node);

  MyNode<T1, T2> toNode = new MyNode<T1,T2>();
  int nodeId2 = graph.AddNode(node);

  MyEdge<T1, T2> edge = new MyEdge<T1, T2>();
  int edgeId = graph.AddEdge(edge, nodeId1, nodeId2);

  // retrieve and cast the edge... Nooooooooo
  MyEdge<TTime, TPlace> accesedToNode = (MyEdge<TTime, TPlace>)fromNode[0];
}

Mit problem er, at jeg ikke er interesseret i at skulle caste i indexer kaldet eller andre accesor metoder.

Og til evt undrende folk, så skal accesedToNode nok hedde accesedEdge før det er kongruens i tingene.

Har du givet fortabt Nielle?

Kan det ikke lade sig gøre eller skal jeg oprette et nyt spørgsmål.

Nej, jeg har b3estem ikke givet fortabt - det er faktisk et interessant problem at arbejde med. Men jeg begynder at tro at det er umuligt. Uanset hvordan jeg drejer og vender den er jeg altid endt tilbage med en cirkulær reference. Jeg har dog endnu ikke kunnet gennemskue om det nødvendigvis må være sådan, eller om der er en eller anden lille smart variation som fixer det.

Det er ikke helt klart om du ønsker at have:

1) En Adjacency Graph som basis klasserne, sådan at alle klasser som beuger duine generics klasser automatisk også er en AG. Eller:
2) Du ønsker at have kunne indsætte en AG i din template.

Det nedenstående kode er et eksempel på hvordan dette kunne gøres. Der er godt nok en enkelt typecast, men den er  gemt inde i AddEdge() funktionen i MyNode klassen - jeg ved ikke om du mener at det er problematisk?

Koden:

        static void Main(string[] args)
        {
            Graph<T1, T2, MyEdge, MyNode> graph =
              new Graph<T1, T2, MyEdge, MyNode>();

            MyNode fromNode = new MyNode();
            int nodeId1 = graph.AddNode(fromNode);

            MyNode toNode = new MyNode();
            int nodeId2 = graph.AddNode(toNode);

            MyEdge edge = new MyEdge();
            int edgeId = graph.AddEdge(edge, nodeId1, nodeId2);

            MyEdge accesedToNode = fromNode[0];
        }

        class Graph<TTime, TPlace, TEdge, TNode>
            where TEdge : Edge<TEdge, TTime, TPlace>
            where TNode : Node<TEdge, TTime, TPlace>
        {
            private List<TNode> nodes;
            private List<TEdge> edges;

            public Graph()
            {
                nodes = new List<TNode>();
                edges = new List<TEdge>();
            }

            public int AddNode(TNode node)
            {
                nodes.Add(node);
                return nodes.IndexOf(node);
            }

            public int AddEdge(TEdge edge, int nodeId1, int nodeId2)
            {
                edge.Node1 = nodes[nodeId1];
                edge.Node2 = nodes[nodeId2];

                edges.Add(edge);
                return edges.IndexOf(edge);
            }
        }

        class Node<TEdge, TTime, TPlace>
        {
            public virtual void AddEdge(Edge<TEdge, TTime, TPlace> edge)
            {
            }
        }

        class Edge<TEdge, TTime, TPlace>
        {
            private Node<TEdge, TTime, TPlace> node1;
            public Node<TEdge, TTime, TPlace> Node1
            {
                get { return node1; }
                set
                {
                    node1 = value;
                    node1.AddEdge(this);
                }
            }

            private Node<TEdge, TTime, TPlace> node2;
            public Node<TEdge, TTime, TPlace> Node2
            {
                get { return node2; }
                set
                {
                    node2 = value;
                    node2.AddEdge(this);
                }
            }
        }

        // ------------------------

        struct T1 { }
        struct T2 { }

        class MyNode : Node<MyEdge, T1, T2>
        {
            private List<MyEdge> adjacencyList;

            public MyEdge this[int index]
            {
                get { return adjacencyList[index]; }
            }

            public MyNode()
            {
                adjacencyList = new List<MyEdge>();
            }

            public override void AddEdge(Edge<MyEdge, T1, T2> edge)
            {
                base.AddEdge(edge);
                adjacencyList.Add((MyEdge)edge);
            }
        }

        class MyEdge : Edge<MyEdge, T1, T2>
        {
        }

Jeg er nødt til at kigge mere på din kode før jeg kan melde tilbage. Der er desværre ikke tid til det før søndag aften.

Hvis man kan begrænse typecast situationer til sine add metoder og holde accessors og indexers fri for typecasts, så er jeg fint tilfreds.

Angående dine 2 spørgsmål, så er jeg ikke helt 100 % med på hvad du spørger om.

1) Det er naturligvis kun Adjacency Graphs og evt. klasser, der nedarver fra AdjacencyGraph, der skal beytte Nodes, der internt gemmer adjacencylister. Hvis man vil bruge matrix repræsentation til sin graph, så skal man have fat i en anden type Graph og dermed en anden variant af Node.

Edge som jeg ser det er uafhængig af Node / Graph repræsentationen. Den skal bare udtrykke en sammenhæng mellem 2 nodes og er ligeglad med om man gemmer den i graph klassen eller i Node klassen.

Det må altså kræves, at basis funktionaliteten for AdjacencyGraph og AdjacencyNode passer sammen. AddEdge metoden i graph skal vide, at den skal gemme en Edge i Noden og Noden skal understøtte en sådan liste.

Edge er taget ud af den sammenhæng. En edge skal bare kende en from og toNode.

Man burde nok rettere have et hierarki som følger:

Node { id, place }
MatrixNode : Node { } // For other graph type
AdjacencyNode : Node { adjacencyList }
TimePlaceNode : AdjacencyNode { time }

Edge { fromNode, toNode }
CapacitatedEdge : Edge { capacity }

Graph { AddNode, AddEdge }
MatrixGraph : Graph
AdjacencyGraph : Graph

Så fik jeg aligevel kigget på dit seneste foreslag. Du har undgået det cirkulære ved at indføre, at Nodes og Edges passer sammen i par.

Så hvis man vil bruge en MyNode, skal man også bruge en MyEdge. Dermed er Node-Edge valget fastlagt ved initialiseringen af grafen.

Det er bestemt en løsning, men fjerner desværre også smidigheden i opbygningen.

Om man benytter en Edge, MyEdge eller en CapacitatedEdge er underordnet for valget af Node. Jeg vil gerne understøtte muligheden for at tilføje flere properties på både Edge og Node og det ideelle design vil være, at graph klassen begrænser, hvilke klasser man kan nedarve fra mht. både Nodes og Edges, men ellers åbner for frit slag indenfor under træerne i hierarkiet.

Så en Adjacency Graph kan udgøres af Nodes, der kun har et navn og et id(+ adjacency List), mens Edges kan være specialiserede Edges, med mange ekstra properties, som ligger længere nede i hierarkiet.

Tilsvarende kan en graph også være en meget specialiseret Node, der kun kædes med simple base Edges uden ekstra properties.

Til test/udvikling af algoritmer vil det være smart at kunne teste grafen med forskellige Node - Edge kombinationer og dermed forskellige måder at gemme data på.

Jeg havde håbet på stor smidighed i strukturen, men er måske nødt til at gå på kompromis.

Det hele kommer ned til hvordan man lavet en generisk struktur, hvor Node skal kende Edge typen og Edge skal kende Node typen.

Kunne man bare komme over den hurdle, så ville man kunne sende Edge og Node typen ind i graph og derfra videre ind i den valgte Node og Edge type.

I denne version går det forholdsvist smertefrit at kombinere forskellige implementationer af Node og Edge:

    // Aliaser - se koden for graph4 nedenfor.
    using CEstring = CapacityEdge<string>;
    using ACEstring = AdjacencyNode<CapacityEdge<string>>;

    class Program
    {
        static void Main(string[] args)
        {
            // Graf baseret på BaseNode og BaseEdge

            BaseGraph<BaseNode<BaseEdge>, BaseEdge> graph1 =
                new BaseGraph<BaseNode<BaseEdge>, BaseEdge>();

            BaseNode<BaseEdge> fromNode1 = new BaseNode<BaseEdge>();
            graph1.AddNode(fromNode1);

            BaseNode<BaseEdge> toNode1 = new BaseNode<BaseEdge>();
            graph1.AddNode(toNode1);

            BaseEdge edge1 = new BaseEdge();
            graph1.AddEdge(edge1, fromNode1, toNode1);


            // Graf baseret på AdjacencyNode og BaseEdge

            AdjacencyGraph<BaseEdge> graph2 = new AdjacencyGraph<BaseEdge>();

            AdjacencyNode<BaseEdge> fromNode2 = new AdjacencyNode<BaseEdge>();
            graph2.AddNode(fromNode2);

            AdjacencyNode<BaseEdge> toNode2 = new AdjacencyNode<BaseEdge>();
            graph2.AddNode(toNode2);

            BaseEdge edge2 = new BaseEdge();
            graph2.AddEdge(edge2, fromNode2, toNode2);

            BaseEdge accesedToNode = fromNode2[0];


            // Graf baseret på BaseNode og CapacityEdge

            BaseGraph<BaseNode<CapacityEdge<int>>, CapacityEdge<int>> graph3 =
                new BaseGraph<BaseNode<CapacityEdge<int>>, CapacityEdge<int>>();

            BaseNode<CapacityEdge<int>> fromNode3 = new BaseNode<CapacityEdge<int>>();
            graph3.AddNode(fromNode3);

            BaseNode<CapacityEdge<int>> toNode3 = new BaseNode<CapacityEdge<int>>();
            graph3.AddNode(toNode3);

            CapacityEdge<int> edge3 = new CapacityEdge<int>(42);
            graph3.AddEdge(edge3, fromNode3, toNode3);


            // Graf baseret på AdjacencyNode og CapacityEdge
            // Notationen simplificeret ved brug af using.

            AdjacencyGraph<CEstring> graph4
                = new AdjacencyGraph<CEstring>();

            ACEstring fromNode4 = new ACEstring();
            graph4.AddNode(fromNode4);

            ACEstring toNode4 = new ACEstring();
            graph4.AddNode(toNode4);

            CEstring edge4 = new CEstring("Hallo, generics");
            graph4.AddEdge(edge4, fromNode4, toNode4);
        }
    }

    // Base generics

    class BaseGraph<TNode, TEdge>
        where TNode : BaseNode<TEdge>
        where TEdge : BaseEdge
    {
        protected List<TNode> nodes;
        protected List<TEdge> edges;

        public BaseGraph()
        {
            nodes = new List<TNode>();
            edges = new List<TEdge>();
        }

        public virtual void AddNode(TNode node)
        {
            nodes.Add(node);
        }

        public virtual void AddEdge(TEdge edge, TNode node1, TNode node2)
        {
            node1.AddEdge(edge);
            node2.AddEdge(edge);

            edges.Add(edge);
        }
    }

    class BaseNode<TEdge>
    {
        protected List<TEdge> edges;

        public BaseNode()
        {
            edges = new List<TEdge>();
        }

        public void AddEdge(TEdge edge)
        {
            edges.Add(edge);
        }
    }

    class BaseEdge
    {
    }

    // Adjacency generics

    class AdjacencyGraph<TEdge> : BaseGraph<AdjacencyNode<TEdge>, BaseEdge>
        where TEdge : BaseEdge
    {
        public override void AddEdge(BaseEdge edge, AdjacencyNode<TEdge> node1, AdjacencyNode<TEdge> node2)
        {
            node1.AddEdge(edge);

            edges.Add(edge);
        }
    }

    class AdjacencyNode<TEdge> : BaseNode<BaseEdge>
        where TEdge : BaseEdge
    {
        public TEdge this[int index]
        {
            get { return (TEdge)edges[index]; }
        }
    }

    // Capacity generics

    class CapacityEdge<TCapacity> : BaseEdge
    {
        protected TCapacity capacity;

        public CapacityEdge(TCapacity capacity)
        {
            this.capacity = capacity;
        }
    }

Hej Nielle

Tak for dine seneste input.

Jeg er bange for, at du "snyder" lidt i din seneste løsning. En BaseEdge kan ingenting = har ingen properties. Den skulle gerne gemme en fra og til Node af den korrekte type. Ellers kan man ikke søge igennem grafen.

Det er nødvendigt, at kunne se hvor neighbour edges ender ellers vil en query på en node's adjacency/neighbour edges bare give dig en masse edge instanser, der ikke fortæller dig noget.

Hvis du indfører en From og ToNode i BaseEdge klassen, så er man tilbage til det oprindelige problem. BaseEdge afhænger af BaseNode og BaseNode afhænger af BaseEdge.

Hvad hedder problemstillingen? Nogle idéer. Jeg er vel ikke den første i verden, der har dette problem. Synes bare, at alt hvad jeg kan finde i Google er noget med cykliske referencer til projekter i Visual Studio. Men kan ikke rigtig finde nogen hits på noget med generics.

Læste et svar til en gut, der havde problemer med cykliske referencer mellem sine projekter og han fik at vide, at cykliske referencer opstod pga. dårligt design. Det er vel også mit problem, dårligt design? Ellers må man jo leve med de typecasts. Ved ikke hvor dyre de vil være, men det må jeg jo teste/acceptere.

Kan det være et design pattern man skal have gang i?