089 / graphs Goto Github PK

Wiki DE

Mehrfachkante/Multikante: Zwischen zwei Knoten verlaufen in einem Multigraphen mehrere gleichartige Kanten. Die einzelnen Kanten werden als parallele Kanten bezeichnet.

Wiki EN

Multiple edges are two or more edges that connect the same two vertices. A loop is an edge (directed or undirected) that connects a vertex to itself; it may be permitted or not, according to the application. In this context, an edge with two different ends is called a link.
A multigraph, as opposed to a simple graph, is an undirected graph in which multiple edges (and sometimes loops) are allowed.
Where graphs are defined so as to disallow both multiple edges and loops, a multigraph is often defined to mean a graph which can have both multiple edges and loops,[6] although many use the term pseudograph for this meaning.[7] Where graphs are defined so as to allow both multiple edges and loops, a multigraph is often defined to mean a graph without loops.[8]

Links mit Infos und Format

1. https://de.wikipedia.org/wiki/DOT_(GraphViz)
2. http://www.graphviz.org/Documentation/dotguide.pdf

Aufgaben

1. Graphen-Objekt ausgeben für graphviz/dot
2. Es wird berücksichtigt, ob es sich um einen gerichteten oder ungerichteten Graphen handelt
3. Die Bezeichnung wird aus dem "node name" String Array geladen

Beispiel wget

user@computer:~$ wget
wget: URL fehlt
Syntax: wget [OPTION]... [URL]...

»wget --help« gibt weitere Informationen.
user@computer:~$ wget --help
GNU Wget 1.17.1, ein nicht-interaktives Netz-Werkzeug zum Download von Dateien.
Syntax: wget [OPTION]... [URL]...

Erforderliche Argumente zu langen Optionen sind auch bei kurzen Optionen erforderlich.

Beim Start:
  -V,  --version                   Programmversion von Wget anzeigen und beenden
  -h,  --help                      diese Hilfe anzeigen
  -b,  --background                nach dem Starten in den Hintergrund gehen
  -e,  --execute=BEFEHL            einen ».wgetrc«-artigen Befehl ausführen

Log-Datei schreiben und Eingabe-Datei:
  -o,  --output-file=DATEI         Protokoll-Meldungen in DATEI schreiben
  -a,  --append-output=DATEI       Meldungen an DATEI anhängen
  -d,  --debug                     Debug-Ausgabe anzeigen
  -q,  --quiet                     keine Ausgabe von Meldungen
  -v,  --verbose                   ausführliche Meldungen (Vorgabe)
  -nv, --no-verbose                weniger Meldungen, aber nicht stumm

[...]
Fehlerberichte und Verbesserungsvorschläge bitte an <[email protected]>
schicken.

Für die deutsche Übersetzung ist die Mailingliste
<[email protected]> zuständig.

1. Der aktuelle Zustand des Graphenobjekts ausgeben
2. als Adjazenzmatrix im CSV-Format

1. Tool von graphtool(Gui) in graphs umbenennen
2. CMake und Co entsprechend anpassen
3. Testen, dass nichts kaputt gegangen ist

Bitte fixen, falls noch Zeit und Lust:

Für graphtoolGui -iml "[0 1 1 1 1 0 0 0 0 0 0; 1 0 0 0 0 0 0 0 0 0 0; 1 0 0 0 0 0 0 0 0 0 0; 1 0 0 0 0 0 0 1 1 1 0; 1 0 0 0 0 1 1 0 0 0 0; 0 0 0 0 1 0 0 0 0 0 0; 0 0 0 0 1 0 0 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 1 0]" -na gibt die Function hasCycle() true statt false aus (siehe #57. Das führt dazu, dass auch deine Funktion nicht gut funktioniert.

Im Codeteil

    if(hasCycle() || !isDirected()) {
        isForestFlag = false;
        return false;
    }

bin ich mir nicht ganz sicher, ob !isDirected() an der Stelle richtig ist. Warum sollte ein ungerichteter Graph ohne weitere Überprüfung kein Wald sein (siehe Beispiel oben)?

Überprüft, ob der gefundene Weg ein einfacher Weg ist.

Der Graph wird in einer HTML-Seite mit Hilfe von Sigma JS angezeigt. Als Grundlage dazu dient der Export des Graphen im JSON Format.

Auch die Eigenschaften des Graphen werden dort angezeigt.

1. Die interne Adjazenzmatrix wird als JSON ausgegeben
2. Format siehe http://sigmajs.org/ : "id" entspricht dabei dem Arrayindex der Adjazenzmatrix und Label aus dem "node name" Stringarray

Ermittelt die Anzahl der Knoten des Graphen und gibt diese Zurück.

Überprüft ob der gegebene Graph einen bestimmten Weg hat.
Der zu überprüfende Weg wird als Parameter übergeben

Überprüft den gegebenen Graphen auf einen Zyklus.
Sobald der erste Zyklus gefunden wurde, wird true zurück gegeben.
Falls kein Zyklus gefunden wurde, wird false zurück gegeben.

1. https://de.wikipedia.org/wiki/Adjazenzmatrix
2. ermöglicht schnellen/einfachen Import von Daten in unsere Library

Jeder Entwickler schreibt für seine Methoden und Klassen sinnvolle Doxygen-Kommentare und erläutert in diesen etwaige nicht-triviale Algorithmen

1. https://de.wikipedia.org/wiki/Adjazenzmatrix#Erreichbare_Knoten_ermitteln
2. https://de.wikipedia.org/wiki/Adjazenzmatrix#Pfadl.C3.A4nge_in_Graphen_berechnen

Aus der Aufgabenstellung

1. Anbindung an Travis CI (https://travis-ci.org/)
2. Projekt übersetzen
3. Unittests ausführen
4. evtl. Website für das Projekt bauen

[...] bezeichnet einen einfachen Graph, in dem jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist. Der vollständige Graph mit n Knoten ist (bis auf Isomorphie) eindeutig bestimmt und wird mit K_n bezeichnet.

areNeighbours gibt abhängig von der "Gerichtetheit" an ob zwei Knoten eines Graphen Nachbarn sind.

Ein einfacher Graph (auch schlichter Graph) ist in der Graphentheorie ein ungerichteter Graph ohne Mehrfachkanten und ohne Schleifen.

1. muss in "isSquareMatrix" umbenannt werden. Eine Adjazenzmatrix muss quadratisch sein, nicht symmetrisch.
2. Doku in .h-Datei ergänzen
3. erst nach den pull requests #39 #43

Ermittelt die Länge des Weges und gibt diese zurück.

(boolean) gibt an, ob Graph schleifenfrei ist (keine Werte auf der Hauptdiagonalen)

• Hilfsfunktion für isSimpleGraph #28

Ich habe Ihnen Admin-Rechte in diesem Repo gegeben.

Sie können damit das Repo in ihren eigenen Account oder eine andere Organisation übernehmen.

Gehen Sie dazu auf Settings und scrollen Sie ganz nach unten. In der "Danger Zone" finden Sie "Transfer ownership".

Wenn Sie das Repo nicht übernehmen wollen, werde ich es Ende Juli löschen.

1. Für die Berechnung des jeweiligen Grades reicht es, bezogen auf die Adjazenzmatrix, wenn für
   • outdeg: alle Werte > 0 in der Zeile des jeweiligen Knotens gezählt werden.
   • indeg: alle Werte > 0 in der Spalte des jeweiligen Knotens gezählt werden.
2. Für ungerichtete Graphen gilt: indeg = outdeg
3. Aus Wikipedia:

Der Grad d_G(v) in einem Graphen ist die Anzahl der Kanten, die den Knoten v mit anderen Knoten verbinden. Eine Schlinge wird dabei doppelt gezählt. Oft wird auch die Notation \deg _G(v) (engl. degree) verwendet.

Ermittelt die Anzahl der Kanten im Graph und gibt diese zurück.

1. Anforderung aus Aufgabenstellung
2. Hinweis: https://pages.github.com/#project-site
3. Jeder Entwickler schreibt für seine Methoden und Klassen sinnvolle Doxygen-Kommentare und erläutert in diesen etwaige nicht-triviale Algorithmen

Anforderung aus Aufgabenstellung

• Matrizen, die im o.g. Format an das Programm übergeben werden, sollen in der internen Adjazenzmatrix gespeichert werden
• o.g.-Format: {{1, 0, 0},{0, 0, 0},{1, 0, 1}}
• Vorschlag: Neuer Konstruktor, der dieses Format entgegen nimmt.

Derzeit wird die Systemeigene Boost-Version verwendet. Dies führ zu Inkompatibilität und Komplexität beim kompilieren (Windows). Boost sollte als ExternalProject in der CMake definiert werden.

1. Bei der Implementierung eines Features ist der bearbeitende Entwickler für den Unittest verantwortlich
2. Wir schauen aber auch mit wachem Auge auf den Code der Kollegen und überprüfen insbesondere kompliziertere Algorithmen/Programmkonstrukte gemeinsam

Aus der Aufgabenstellung

Unittests mit “vernünftiger” Code-Abdeckung

Bitte fixen, falls noch Zeit und Lust (Wäre gut, weil isForest abhängt):

Für graphtoolGui -iml "[0 1 1 1 1 0 0 0 0 0 0; 1 0 0 0 0 0 0 0 0 0 0; 1 0 0 0 0 0 0 0 0 0 0; 1 0 0 0 0 0 0 1 1 1 0; 1 0 0 0 0 1 1 0 0 0 0; 0 0 0 0 1 0 0 0 0 0 0; 0 0 0 0 1 0 0 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 1 0]" -na gibt die Function hasCycle() true statt false aus, was der graphischen Darstellung widerspricht.

1. Dafür sollten wir uns persönlich oder in Hangouts treffen
2. Benötigte Klassen
3. Wie sollen die Daten abgelegt werden (Datenstruktur)

Der Branch GH-Pages dient als GitHub-Branch für die die Webseite. Somit können alle Dateien, welche in diesen Branch abgelegt werden, live betrachtet werden.
Die vorhandene Dokumentation für Doxygen bleibt dabei unberührt.

In der Graphentheorie heißt ein Graph regulär, falls alle seine Knoten gleich viele Nachbarn haben, also den gleichen Grad besitzen. Bei einem regulären gerichteten Graphen muss weiter die stärkere Bedingung gelten, dass alle Knoten den gleichen Eingangs- und Ausgangsgrad besitzen.[1] Ein regulärer Graph mit Knoten vom Grad k wird k-regulär oder regulärer Graph vom Grad k genannt.

Angabe, ob der Graph ein gerichteter Wald ist (siehe Folien)

Überprüft, ob ein Übergebenes Paar (v, v') eine Kante im Graph ist.

Folgende Features sind derzeit geplant. Wenn du eines bearbeiten möchtest, hake es ab und erstelle ein Issue mit dem Bezeichnungsschema "Feature: Graph hat Kreis" und einer kurzen, aber guten Beschreibung für genau dieses Feature. Ordne dir das Feature bitte selbst zu. Nicht aufgeführte Features bitte mir mitteilen, damit ich sie aufnehmen kann.

Evtl. ist es sinnvoll den Ergebnissen noch Begründungen mitzuliefern, die als Log oder dergleichen ausgegeben werden (z.B. Graph ist regulär weil alle Knoten gleich viele Nachbarn haben)

Bezogen auf einen Graph G = (V, E) (gewünschte/mögliche Rückgabewerte stehen in Klammern):

• hat Kreis (boolean)
• hat Kreis (Teilgraph)
• hat Zyklus (boolean)
• hat Hamiltonkreis (boolean)
• hat Hamiltonkreis (Teilgraph/Graph)
• hat Eulerkreis (boolean)
• hat Eulerkreis (Teilgraph/Graph)
• hat offenen Eulerzug/-pfad/-weg (boolean)
• hat offenen Eulerzug/-pfad/-weg (Teilgraph/Graph)
• ist Kreis (boolean) überprüft ob übergebener Parameter ein Kreis in G ist
• ist Zyklus (boolean) überprüft ob übergebener Parameter ein Zyklus in G ist
• ist Hamiltonkreis (boolean) überprüft ob übergebener Parameter ein Hamiltonkreis in G ist
• ist Eulerkreis (boolean) überprüft ob übergebener Parameter ein Eulerkreis in G ist
• ist offenen Eulerzug/-pfad/-weg (boolean) überprüft ob übergebener Parameter ein offener Eulerzug in G ist
• ist Baum
• ist vollständig
• ist regulär (boolean)
• Anzahl Knoten (int)
• Anzahl Kanten (int)
• hat Weg (boolean), überprüft, ob G einen bestimmten Weg (Parameter) hat
• Länge des Weges (int)
• Ist einfacher Weg (boolean)
• v_1 ist Nachbar von v_2 (boolean), nach Übergabe von zwei Parametern; abhängig von (Un-)Gerichtetheit von G
• get Adjazenzmatrix (Array/BitSet oder dergleichen mit geeignetem Datentyp)
• get Inzidenzmatrix (Array/BitSet oder dergleichen mit geeignetem Datentyp)
• v_1 ist erreichbar von v_2 (boolean), gibt an ob es einen Weg von v_1 nach v_2 gibt
• indeg/outdeg (Grad) von Knoten v_1 ist (int)
• hat x Zusammenhangskomponenten (int)
• ist planar (boolean)
• ist isomorph (boolean) überprüft ob der als Parameter übergebene Graph G_1 isomorph zu G ist
• ist Wald (boolean)
• ist bipartit (boolean)
• get Spannbaum (Teilgraph)
• ist Clique (boolean) überprüft, ob der als Parameter übergebene Teilgraph ein eine Clique ist
• hat Clique (Teigraph) mithilfe Greedy-Algorithmus (! NP-vollständig)
• ist Kante im Graphen (boolean), als Parameter ein Paar ((v, v′ ), (v′ , v)) übergeben
• Graph ist gerichtet (bool == true), ungerichtet (bool = false)
• isFreeOfLoops, (boolean) gibt an, ob Graph schleifenfrei ist (keine Werte auf der Hauptdiagonalen)
• isSimpleGraph (boolean), "ein ungerichteter Graph ohne Mehrfachkanten und ohne Schleifen." (wikipedia)
• isMultigraph, (boolean) "Zwischen zwei Knoten verlaufen in einem Multigraphen mehrere gleichartige Kanten."

1. Github-Repo anlegen/befüllen
2. Clion sinnvoll einrichten
   1. moderner C++-Code (C++11, C++14)
   2. Einrückung festlegen (Tab oder Spaces)
3. .gitignore erstellen
4. Ergebnis pushen

Ziel: Einer legt die gemeinsamen Einstellungen der Entwicklungsumgebung fest. Die anderen können mit diesem Stand mit ihrer Arbeit beginnen.

Überprüfung der Adjazenzmatrix auf symmetrische Einträge ==> ungerichtet

• Matrizen, die im Matlab-Format an das Programm übergeben werden, sollen in der internen Adjazenzmatrix gespeichert werden
• Matlab-Format: https://de.mathworks.com/help/matlab/math/creating-and-concatenating-matrices.html#f1-84906: [1 0 0; 0 1 1; 0 0 1]