2 Graphen auf Gleichheit prüfen

Einen wunderschönen guten Abend,

ich habe mit der Bibliothek ILNumerics zwei Graphen erstellt

/********************************************************************/
        private void Form1_Load(object sender, EventArgs e)
        {
            m_panel = ILPanel.Create();
            Controls.Add(m_panel);

            ILArray<double> data1 = { 0.0, 3.0, 10.0, 18.0 };
            ILArray<double> data2 = { 0.0, 6.0, 10.0, 1.0 };
            ILPlot2DGraph[] a = m_panel.Graphs.AddLineGraph(data1, data2);


            ILArray<double> data3 = { 0.0, 3.0, 10.0, 18.0 };
            ILArray<double> data4 = { 0.0, 6.0, 10.0, 5.0 };
            ILPlot2DGraph[] b = m_panel.Graphs.AddLineGraph(data3, data4);

            m_panel.Legend.Visible = true;
            m_panel.Legend.Location = new PointF(0.12f, 0.09f);

            a[0].Label.Text = "Vorgabe";
            a[0].Line.Width = 8;
            a[0].Line.Color = Color.Blue;

            b[0].Label.Text = "Versuch";
            b[0].Line.Color = Color.Red;

\********************************************************************/

wie kann ich Vorgabe nun mit Versuch vergleichen und gucken ob es komplett in der vorgegebenen Linie liegt!?

Mit freundlichen Grüßen,
ShaThaL

Ich würd einmal annehmen, dass der Graph identisch ist, wenn alle Knoten identisch sind. Wo ist das Problem dabei den Graphen Knoten für Knoten zu vergleichen und auf unterschiede zu prüfen? Evt. musst du in unterschiedliche Richtungen suchen und bei einem Kreis dir merken, welche Knoten du schon geprüft hast.

Wenn du technische Probleme bei der Umsetzung hast, zeig was du bisher probiert hast und erklär woran du scheiterst.

Lg, XXX

Hallo xxxprod,

wenn alle Knoten identisch wären, hätte man nicht zwei Graphen, sondern nur einen. 😃

Also sollte man schon auf Gleichheit prüfen. Doch da fängt das Problem an. Wann sind denn zwei Knoten gleich? Wenn sie die gleiche Anzahl von Kanten haben? Nein, es kommt ja darauf an, zu welchen Knoten die Kanten laufen. Sie müssten als zu Knoten laufen, die wieder gleich zueinander sind. Nur ist man dann schon munter in der Rekursion drin. Mal abgesehen davon, dass man irgendwie herauskriegen muss, welche Knoten man überhaupt als gleich vermutet. Was für den Menschen einfach zu sehen ist, bleibt dem Computer verborgen. Wenn man da naiv ran geht, bleibt einem kaum was anders als jeden Knoten mit jedem anderen zu vergleichen und das nicht nur auf der ersten Ebene, sondern wieder neu auf jeder folgenden Ebene. Das wäre ein Overkill. Also, so einfach, wie es bei dir klingt, ist es sicher nicht.

Hallo SHaThaL,

auf der anderen Seite gibt es für Graphenvergleiche fertige Algorithmen. Bevor du überlegt, wie du es anfängst, solltest du also erstmal schauen, was es da schon gibt.

herbivore

Hallo herbivore,

stimmt, natürlich ist das Thema komplexer. Ich hab mir bei meiner Antwort nur die Zahlenwerte und das eine ungleiche Paar angesehen und hab daraus geschlossen, dass die Suche nach solch einem Unterschied recht einfach zu implementieren sei. Wenn man andere Kriterien für die Gleichheit heranzieht, funktioniert dieser Ansatz vermutlich nicht mehr so gut.

Lg, XXX

Hallo xxxprod,

Ich hab mir bei meiner Antwort nur die Zahlenwerte und das eine ungleiche Paar angesehen und hab daraus geschlossen, dass die Suche nach solch einem Unterschied recht einfach zu implementieren sei.

ich habe zugegeben den allgemeinen/allgemeinsten Fall beschrieben. Wenn die Knoten durch eine ID oder ihre Koordinaten oder auch nur durch besondere Werte eindeutig identifizierbar sind, sieht es natürlich ganz anders aus. Das vereinfacht die Sache enorm. Wobei selbst dann fraglich ist, ob es reicht, die nur Knoten zu vergleichen, denn ein Graph besteht aus Knoten und Kanten. Mit anderen Worten, selbst wenn die Menge der Knoten gleich ist, bedeutet das automatisch nicht, dass die Menge der Kanten auch gleich ist.

Aber im Grund kann uns nur SHaThaL sagen, wie die Aufgabe zu interpretieren ist, also was eigentlich genau verglichen werden soll und wann zwei Graphen als gleich anzusehen sind und wann nicht.

herbivore

Spontan würd ich sagen:

1. Test auf Knotenzahl -> wenn unterschiedlich break

2. Test auf Kantenzahl -> wenn unterschiedlich break

3. Sortieren aller Knoten nach Grad (Eingangsgrad, Ausgangsgrad) -> wenn da nicht alles identisch -> break

4. Jeder Knoten aus Graph1 bekommt eine ID. Zuweisen eindeutiger IDs auf Graph 2 (Wenn es nur 1 Knoten mit Grad (3,2) gibt -> ID übernehmen)

5. Suchen kürzester "Wege zwischen Knoten mit IDs".
   Hat zb Graph2: ID0 -> XXX -> ID1 muss auch in Graph 1 ein Weg über 2 Kanten zwischen ID0 und ID1 existieren (wenn nicht - break). Gibt es 1 Weg ist der Knoten auf diesem Weg XXX. Gibt es mehrere vergleiche hier wieder die Grade bzw. Nachbarn.

6. 5. machst du nun solange bis keine ID freien Knoten mehr da sind. Bist du am Ende und konntest jede ID zuweisen, sind die Graphen identisch

Du könntest für jeden Knoten speichern: ID, Grad, Liste mit Nachbarn entweder als ID oder wiederum als Grad.

Möglichkeit 2: Schau dir mal Dijkstra genau an - ich bin mir sicher der lässt sich umbauen/erweitern - stellt sich natürlich generell die Frage was für ein Graph es ist. Bei einem Baum isses simpel...

Was kam raus bei deinem Graphenvergleich? Würde mich interessieren!