graphs

Graphs

Ein tolles Tool für und mit Graphen. Mit diesem Tool können verschiedene Eigenschaften von Graphen ermittelt und ausgegeben werden. Die Ergebnisse werden übersichtlich dargestellt und können in verschiedenen Ausgabeformaten ausgegeben werden. Achte bei den Optionen auf Groß- und Kleinschreibung.

Funktionen

OPTIONS EINGABE -i --input-csv (1) Liest die Adjazenzmatrix des Graphen aus der angegebenen CSV-Datei aus. -iml --input-matlab (1) Erzeugt einen Graphen aus der in Matlab-Notation angegebenen Adjazenzmatrix. -ima --input-mathematica (1) Erzeugt einen Graphen aus der in Mathematica-Notation angegebenen Adjazenzmatrix. -ivn --input-vertices-name (1) Übergibt Namen der Knoten. Diese werden bei der Ausgabe anstelle der Knotennummer angegeben. AUSGABE -o --output-csv (1) Speichert die Adjazenzmatrix des Graphen in der angegebenen Datei -oj --output-json (1) Speichert den Graphen - als JSON im Format von sigmajs.org - in der angegebenen Datei. -og --output-graphviz (1) Speichert den Graphen in der angegebenen Datei im Format von Graphviz (hier: DOT). -v --verbose (1) Aktiviert den wortreichen Modus FUNKTIONEN OHNE ARGUMENTE -h --help (0) Zeigt die Hilfe an. -na --no-args (0) Ruft alle Funktionen auf, die keine Argumente benötigen und gibt die Ergebnisse aus. -V --vertices-count (0) Gibt die Anzahl der Knoten |V| aus. -E --edges-count (0) Gibt die Anzahl der Kanten |E| aus. -d --is-directed (0) Gibt an, ob der Graph gerichtet ist. -c --is-complete (0) Gibt an, ob der Graph vollstaendig ist. Ein vollständiger Graph ist ein Begriff aus der Graphentheorie und bezeichnet einen einfachen Graph, in dem jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist (Wikipedia). -mg --is-multigraph (0) Gibt an, ob der Graph ein Multigraph ist. In sogenannten Multigraphen können zwei Knoten auch durch mehrere Kanten verbunden sein, was in einfachen Graphen nicht erlaubt ist(Wikipedia). -r --is-regular (0) Gibt an, ob der Graph regulaer ist. 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 (Wikipedia). -s --is-simple (0) Gibt an, ob der Graph einfach ist. Ein einfacher Graph (auch schlichter Graph) ist in der Graphentheorie ein ungerichteter Graph ohne Mehrfachkanten und ohne Schleifen (Wikipedia). -cy --has-cycle (0) Gibt an, ob der gerichtete Graph einen Kreis hat. -fol --is-free-of-loops (0) Gibt an, ob der Graph schleifenfrei ist (z.B. von Knoten 1 zu Knoten 1). -for --is-directed-forest (0) Gibt an, ob der Graph ein gerichteter Wald ist. Als Wald bezeichnet man in der Graphentheorie einen ungerichteten Graphen ohne Zyklus. Ist dieser zusammenhängend, so spricht man von einem (ungerichteten) Baum. Jede Zusammenhangskomponente eines Waldes ist ein Baum. Eine Verallgemeinerung auf gerichtete Graphen kann man erklären, indem man diese auf die zugrundeliegenden Ungerichteten zurückführt (Wikipedia). FUNKTIONEN MIT ARGUMENTEN -ideg --indegree (1) Gibt die Anzahl der eingehenden Kanten eines Knoten (Parameter = Nummern zwischen 0 und |V| - 1) aus. -odeg --outdegree (1) Gibt die Anzahl der ausgehenden Kanten eines Knoten (Parameter = Nummern zwischen 0 und |V| - 1) aus. -an --are-neighbours (2) Gibt an, ob zwei Knoten (Parameter = Nummern zwischen 0 und |V| - 1) Nachbarn sind. -hc --has-connectivity (2) Gibt an, ob es zwischen den beiden Knoten (Parameter = Nummern zwischen 0 und |V| - 1) einen Weg gibt. -he --has-edge (2) Gibt an, ob es den Knoten mit der gegebenen Nummer zwischen 0 und |V| - 1 gibt. -hp --has-path (1) Gibt an, ob die übergebene Kantenfolge (Mindestens ein Parameter = Nummern zwischen 0 und |V| - 1) im Graph existiert.

Beispiel 1

Eine Matrix in Matlab-Notation und alle Funktionen ausführt, die keine Argumente benötigen:

`graphs -iml "[1 1 0; 1 0 1; 1 1 0]" -na -oj example.json

Eigenschaften


                    
                        
                            Eigenschaft
                            Wert

json-Ausgabe


{
    "graph": {
        "nodes": [{
                "id": "0",
                "label": "0",
                "x": "7",
                "y": "9",
                "size": "1"
            },
            {
                "id": "1",
                "label": "1",
                "x": "3",
                "y": "8",
                "size": "1"
            },
            {
                "id": "2",
                "label": "2",
                "x": "0",
                "y": "2",
                "size": "1"
            }
        ],
        "edges": [{
                "id": "0",
                "source": "0",
                "target": "0",
                "type": "arrow",
                "size": "1"
            },
            {
                "id": "1",
                "source": "0",
                "target": "1",
                "type": "arrow",
                "size": "1"
            },
            {
                "id": "2",
                "source": "1",
                "target": "0",
                "type": "arrow",
                "size": "1"
            },
            {
                "id": "3",
                "source": "1",
                "target": "2",
                "type": "arrow",
                "size": "1"
            },
            {
                "id": "4",
                "source": "2",
                "target": "0",
                "type": "arrow",
                "size": "1"
            },
            {
                "id": "5",
                "source": "2",
                "target": "1",
                "type": "arrow",
                "size": "1"
            }
        ]
    },
    "properties": {
        "isDirected": true,
        "isComplete": false,
        "isMultigraph": false,
        "isRegular": false,
        "isSimple": false,
        "hasCycle": true,
        "isFreeOfLoops": false
    }
}

Sigma Graph

Beispiel 2

graphs -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]" "[0 1 1 1 1 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 1 1 1 0; 0 0 0 0 0 1 1 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 0 0 ]" "[0 0 1 0 0; 1 0 0 0 0; 0 0 0 1 0; 0 0 0 0 1; 1 0 0 0 0]" -na -ideg 0 -odeg 0 -an 0 3 -hc 1 3 -hp 0 2 3 4 0 -oj example.json -og example.dot

Optionen

Drei Matrizen in Matlab-Notation.
Ausführen aller Funktionen, die keine Argumente benötigen.
Knoten 0: Anzahl der eingehenden Kanten
Knoten 0: Anzahl der ausgehenden Kanten
Überprüfung, ob Knoten 0 und 3 Nachbarn sind
Überprüfung, ob zwischen 1 und 3 ein Weg existiert
Überprüfung, ob es den Pfad 0 2 3 4 0 gibt.
Erzeugt die Dateien example.json (SigmaJS) und example.dot (GraphViz)

Eigenschaften

Eigenschaft	Graph 0	Graph 1	Graph 2
Anzahl Knoten	11	11	5
Anzahl Kanten	10	10	5
Ist gerichtet	nein	ja	ja
Ist vollstaendig	nein	nein	nein
Ist ein Multigraph	nein	nein	nein
Ist regulaer	nein	nein	nein
Ist einfach	ja	nein	nein
Hat einen Kreis	Bisher nur für Digraphen implementiert.	nein	ja
Ist schleifenfrei	ja	ja	ja
Ist Wald	Bisher nur für Digraphen implementiert.	ja	nein
in degree(0)	4	0	2
out degree(0)	4	4	1
Sind 0 und 3 Nachbarn	ja	ja	nein
Weg zw. 1 und 3 existiert	ja	nein	ja
Pfad {0, 2, 3, 4, 0} existiert	nein	nein	ja

Graphen mit GraphViz visualisieren

neato -Tpng 0_example.dot > 0_output.png; neato -Tpng 1_example.dot > 1_output.png; neato -Tpng 2_example.dot > 2_output.png