Grafiken in Java

1. Übersicht

In diesem Tutorial werden die grundlegenden Konzepte eines Diagramms als Datenstruktur verstanden .

Wir werden auch die Implementierung in Java sowie verschiedene Operationen untersuchen, die in einem Diagramm möglich sind. Wir werden auch die Java-Bibliotheken diskutieren, die Graph-Implementierungen anbieten.

2. Diagrammdatenstruktur

Ein Diagramm ist eine Datenstruktur zum Speichern verbundener Daten wie ein Netzwerk von Personen auf einer Social-Media-Plattform.

Ein Diagramm besteht aus Eckpunkten und Kanten. Ein Scheitelpunkt repräsentiert die Entität (zum Beispiel Personen) und eine Kante repräsentiert die Beziehung zwischen Entitäten (zum Beispiel die Freundschaften einer Person).

Definieren wir ein einfaches Diagramm, um dies besser zu verstehen:

Hier haben wir ein einfaches Diagramm mit fünf Eckpunkten und sechs Kanten definiert. Die Kreise sind Scheitelpunkte, die Personen darstellen, und die Linien, die zwei Scheitelpunkte verbinden, sind Kanten, die Freunde in einem Online-Portal darstellen.

Abhängig von den Eigenschaften der Kanten gibt es einige Variationen dieses einfachen Diagramms. Lassen Sie uns sie in den nächsten Abschnitten kurz durchgehen.

Wir konzentrieren uns jedoch nur auf das einfache Diagramm, das hier für die Java-Beispiele in diesem Lernprogramm dargestellt wird.

2.1. Gerichteter Graph

Das Diagramm, das wir bisher definiert haben, hat Kanten ohne Richtung. Wenn diese Kanten eine Richtung aufweisen , wird der resultierende Graph als gerichteter Graph bezeichnet.

Ein Beispiel hierfür kann die Darstellung sein, wer die Freundschaftsanfrage in einer Freundschaft auf dem Online-Portal sendet:

Hier können wir sehen, dass die Kanten eine feste Richtung haben. Die Kanten können auch bidirektional sein.

2.2. Gewichteter Graph

Auch hier hat unser einfaches Diagramm Kanten, die unvoreingenommen oder ungewichtet sind. Wenn diese Kanten stattdessen ein relatives Gewicht haben , wird dieses Diagramm als gewichtetes Diagramm bezeichnet.

Ein Beispiel für eine praktische Anwendung kann sein, wie relativ alt eine Freundschaft im Online-Portal ist:

Hier können wir sehen, dass den Kanten Gewichte zugeordnet sind. Dies gibt diesen Kanten eine relative Bedeutung.

3. Diagrammdarstellungen

Ein Diagramm kann in verschiedenen Formen wie Adjazenzmatrix und Adjazenzliste dargestellt werden. Jeder hat seine Vor- und Nachteile in einer anderen Konfiguration.

Wir werden diese Diagrammdarstellungen in diesem Abschnitt vorstellen.

3.1. Adjazenzmatrix

Eine Adjazenzmatrix ist eine quadratische Matrix mit Abmessungen, die der Anzahl der Scheitelpunkte im Diagramm entsprechen.

Die Elemente der Matrix haben typischerweise die Werte '0' oder '1'. Ein Wert von '1' gibt die Nachbarschaft zwischen den Eckpunkten in Zeile und Spalte an, andernfalls ein Wert von '0'.

Mal sehen, wie die Adjazenzmatrix für unser einfaches Diagramm aus dem vorherigen Abschnitt aussieht:

Diese Darstellung ist relativ einfach zu implementieren und auch effizient abzufragen . Es ist jedoch weniger effizient in Bezug auf den belegten Platz .

3.2. Adjazenzliste

Eine Adjazenzliste ist nichts anderes als eine Reihe von Listen . Die Größe des Arrays entspricht der Anzahl der Scheitelpunkte im Diagramm.

Die Liste an einem bestimmten Index des Arrays repräsentiert die benachbarten Scheitelpunkte des Scheitelpunkts, der durch diesen Array-Index dargestellt wird.

Mal sehen, wie die Adjazenzliste für unser einfaches Diagramm aus dem vorherigen Abschnitt aussieht:

Diese Darstellung ist vergleichsweise schwer zu erstellen und weniger effizient abzufragen . Es bietet jedoch eine bessere Raumeffizienz .

Wir werden die Adjazenzliste verwenden, um das Diagramm in diesem Tutorial darzustellen.

4. Grafiken in Java

Java hat keine Standardimplementierung der Diagrammdatenstruktur.

Wir können das Diagramm jedoch mithilfe von Java-Sammlungen implementieren.

Beginnen wir mit der Definition eines Scheitelpunkts:

class Vertex { String label; Vertex(String label) { this.label = label; } // equals and hashCode }

Die obige Definition des Scheitelpunkts enthält nur eine Beschriftung, diese kann jedoch jede mögliche Entität wie Person oder Stadt darstellen.

Beachten Sie außerdem, dass wir die Methoden equals () und hashCode () überschreiben müssen, da diese für die Arbeit mit Java-Sammlungen erforderlich sind.

Wie bereits erwähnt, ist ein Graph nichts anderes als eine Sammlung von Eckpunkten und Kanten, die entweder als Adjazenzmatrix oder als Adjazenzliste dargestellt werden können.

Mal sehen, wie wir dies anhand einer Adjazenzliste hier definieren können:

class Graph { private Map
    
      adjVertices; // standard constructor, getters, setters }
    

Wie wir hier sehen können, die Klasse Graph wird mit Karte von Java Collections die Adjazenzliste definieren.

In einer Diagrammdatenstruktur sind verschiedene Vorgänge möglich, z. B. das Erstellen, Aktualisieren oder Durchsuchen des Diagramms .

Wir werden einige der gängigsten Operationen durchgehen und sehen, wie wir sie in Java implementieren können.

5. Graph Mutation Operations

To start with, we'll define some methods to mutate the graph data structure.

Let's define methods to add and remove vertices:

void addVertex(String label) { adjVertices.putIfAbsent(new Vertex(label), new ArrayList()); } void removeVertex(String label) { Vertex v = new Vertex(label); adjVertices.values().stream().forEach(e -> e.remove(v)); adjVertices.remove(new Vertex(label)); }

These methods simply add and remove elements from the vertices Set.

Now, let's also define a method to add an edge:

void addEdge(String label1, String label2) { Vertex v1 = new Vertex(label1); Vertex v2 = new Vertex(label2); adjVertices.get(v1).add(v2); adjVertices.get(v2).add(v1); }

This method creates a new Edge and updates the adjacent vertices Map.

In a similar way, we'll define the removeEdge() method:

void removeEdge(String label1, String label2) { Vertex v1 = new Vertex(label1); Vertex v2 = new Vertex(label2); List eV1 = adjVertices.get(v1); List eV2 = adjVertices.get(v2); if (eV1 != null) eV1.remove(v2); if (eV2 != null) eV2.remove(v1); }

Next, let's see how we can create the simple graph we have drawn earlier using the methods we've defined so far:

Graph createGraph() { Graph graph = new Graph(); graph.addVertex("Bob"); graph.addVertex("Alice"); graph.addVertex("Mark"); graph.addVertex("Rob"); graph.addVertex("Maria"); graph.addEdge("Bob", "Alice"); graph.addEdge("Bob", "Rob"); graph.addEdge("Alice", "Mark"); graph.addEdge("Rob", "Mark"); graph.addEdge("Alice", "Maria"); graph.addEdge("Rob", "Maria"); return graph; }

We'll finally define a method to get the adjacent vertices of a particular vertex:

List getAdjVertices(String label) { return adjVertices.get(new Vertex(label)); }

6. Traversing a Graph

Now that we have graph data structure and functions to create and update it defined, we can define some additional functions for traversing the graph. We need to traverse a graph to perform any meaningful action, like search within the graph.

There are two possible ways to traverse a graph, depth-first traversal and breadth-first traversal.

6.1. Depth-First Traversal

A depth-first traversal starts at an arbitrary root vertex and explores vertices as deeper as possible along each branch before exploring vertices at the same level.

Let's define a method to perform the depth-first traversal:

Set depthFirstTraversal(Graph graph, String root) { Set visited = new LinkedHashSet(); Stack stack = new Stack(); stack.push(root); while (!stack.isEmpty()) { String vertex = stack.pop(); if (!visited.contains(vertex)) { visited.add(vertex); for (Vertex v : graph.getAdjVertices(vertex)) { stack.push(v.label); } } } return visited; }

Here, we're using a Stack to store the vertices that need to be traversed.

Let's run this on the graph we created in the previous subsection:

assertEquals("[Bob, Rob, Maria, Alice, Mark]", depthFirstTraversal(graph, "Bob").toString());

Please note that we're using vertex “Bob” as our root for traversal here, but this can be any other vertex.

6.2. Breadth-First Traversal

Comparatively, a breadth-first traversal starts at an arbitrary root vertex and explores all neighboring vertices at the same level before going deeper in the graph.

Now let's define a method to perform the breadth-first traversal:

Set breadthFirstTraversal(Graph graph, String root) { Set visited = new LinkedHashSet(); Queue queue = new LinkedList(); queue.add(root); visited.add(root); while (!queue.isEmpty()) { String vertex = queue.poll(); for (Vertex v : graph.getAdjVertices(vertex)) { if (!visited.contains(v.label)) { visited.add(v.label); queue.add(v.label); } } } return visited; }

Note that a breadth-first traversal makes use of Queue to store the vertices which need to be traversed.

Let's again run this traversal on the same graph:

assertEquals( "[Bob, Alice, Rob, Mark, Maria]", breadthFirstTraversal(graph, "Bob").toString());

Again, the root vertex which is “Bob” here can as well be any other vertex.

7. Java Libraries for Graphs

It's not necessary to always implement the graph from scratch in Java. There are several open source and mature libraries available which offers graph implementations.

In the next few subsections, we'll go through some of these libraries.

7.1. JGraphT

JGraphT is one of the most popular libraries in Java for the graph data structure. It allows the creation of a simple graph, directed graph, weighted graph, amongst others.

Additionally, it offers many possible algorithms on the graph data structure. One of our previous tutorials covers JGraphT in much more detail.

7.2. Google Guava

Google Guava is a set of Java libraries that offer a range of functions including graph data structure and its algorithms.

It supports creating simple Graph, ValueGraph, and Network. These can be defined as Mutable or Immutable.

7.3. Apache Commons

Apache Commons is an Apache project that offers reusable Java components. This includes Commons Graph which offers a toolkit to create and manage graph data structure. This also provides common graph algorithms to operate on the data structure.

7.4. Sourceforge JUNG

Java Universal Network/Graph (JUNG) is a Java framework that provides extensible language for modeling, analysis, and visualization of any data that can be represented as a graph.

JUNG supports a number of algorithms which includes routines like clustering, decomposition, and optimization.

Diese Bibliotheken bieten eine Reihe von Implementierungen basierend auf der Diagrammdatenstruktur. Es gibt auch leistungsfähigere Frameworks, die auf Diagrammen basieren , wie Apache Giraph, das derzeit bei Facebook zur Analyse des von den Benutzern erstellten Diagramms verwendet wird, und Apache TinkerPop, das üblicherweise über Diagrammdatenbanken verwendet wird.

8. Fazit

In diesem Artikel haben wir das Diagramm als Datenstruktur zusammen mit seinen Darstellungen erläutert. Wir haben ein sehr einfaches Diagramm in Java mithilfe von Java-Sammlungen definiert und auch allgemeine Durchquerungen für das Diagramm definiert.

Wir haben auch kurz über verschiedene Bibliotheken gesprochen, die in Java außerhalb der Java-Plattform verfügbar sind und Graph-Implementierungen bereitstellen.

Wie immer ist der Code für die Beispiele auf GitHub verfügbar.