Grafieken in Java
1. Overzicht
In deze tutorial we zullen de basisconcepten van een grafiek als datastructuur begrijpen.
We zullen ook de implementatie ervan in Java onderzoeken, samen met verschillende bewerkingen die mogelijk zijn in een grafiek. We zullen ook de Java-bibliotheken bespreken die grafische implementaties aanbieden.
2. Grafiekgegevensstructuur
Een grafiek is een datastructuur voor het opslaan van verbonden data als een netwerk van mensen op een social media platform.
Een grafiek bestaat uit hoekpunten en randen. Een hoekpunt vertegenwoordigt de entiteit (bijvoorbeeld mensen) en een rand vertegenwoordigt de relatie tussen entiteiten (bijvoorbeeld de vriendschappen van een persoon).
Laten we een eenvoudige grafiek definiëren om dit beter te begrijpen:
Hier hebben we een eenvoudige grafiek gedefinieerd met vijf hoekpunten en zes randen. De cirkels zijn hoekpunten die mensen voorstellen en de lijnen die twee hoekpunten met elkaar verbinden, zijn randen die vrienden op een online portaal voorstellen.
Er zijn een paar variaties op deze eenvoudige grafiek, afhankelijk van de eigenschappen van de randen. Laten we ze in de volgende secties kort bespreken.
We zullen ons echter alleen concentreren op de eenvoudige grafiek die hier wordt gepresenteerd voor de Java-voorbeelden in deze tutorial.
2.1. Gerichte grafiek
De grafiek die we tot nu toe hebben gedefinieerd, heeft randen zonder enige richting. Als deze randen hebben een richting erinstaat de resulterende grafiek bekend als een gerichte grafiek.
Een voorbeeld hiervan kan de vertegenwoordiging zijn van wie het vriendschapsverzoek in een vriendschap op het online portaal heeft verzonden:
Hier kunnen we zien dat de randen een vaste richting hebben. De randen kunnen ook bidirectioneel zijn.
2.2. Gewogen grafiek
Nogmaals, onze eenvoudige grafiek heeft randen die onbevooroordeeld of ongewogen zijn. Als in plaats daarvan deze randen dragen relatief gewichtstaat deze grafiek bekend als een gewogen grafiek.
Een voorbeeld van een praktische toepassing hiervan kan zijn hoe relatief oud een vriendschap is op het online portaal:
Hier kunnen we zien dat aan de randen gewichten zijn gekoppeld. Dit geeft een relatieve betekenis aan deze randen.
3. Grafische representaties
Een grafiek kan in verschillende vormen worden weergegeven, zoals een aangrenzende matrix en een aangrenzende lijst. Elk heeft zijn voor- en nadelen in een andere opstelling.
We introduceren deze grafische weergaven in deze sectie.
3.1. Nabijheid Matrix
Een aangrenzende matrix is een vierkante matrix met afmetingen gelijk aan het aantal hoekpunten in de grafiek.
De elementen van de matrix hebben doorgaans de waarde '0' of '1'. Een waarde van ‘1’ geeft de nabijheid tussen de hoekpunten in de rij en kolom aan en anders een waarde van ‘0’.
Laten we eens kijken hoe de aangrenzende matrix eruitziet voor onze eenvoudige grafiek uit de vorige sectie:
Deze weergave is redelijk eenvoudiger te implementeren en efficiënt te bevragen ook. Het is echter minder efficiënt met betrekking tot de ingenomen ruimte.
3.2. Nabijheidslijst
Een aangrenzende lijst is niets anders dan een reeks lijsten. De grootte van de array is gelijk aan het aantal hoekpunten in de grafiek.
De lijst op een specifieke index van de array vertegenwoordigt de aangrenzende hoekpunten van het hoekpunt dat wordt vertegenwoordigd door die array-index.
Laten we eens kijken hoe de aangrenzende lijst eruitziet voor onze eenvoudige grafiek uit de vorige sectie:
Deze vertegenwoordiging is relatief moeilijk te maken en minder efficiënt om te doorzoeken. Het biedt echter betere ruimte-efficiëntie.
We zullen de aangrenzende lijst gebruiken om de grafiek in deze tutorial weer te geven.
4. Grafieken in Java
Java heeft geen standaardimplementatie van de grafiekgegevensstructuur.
We kunnen de grafiek echter implementeren met behulp van Java-verzamelingen.
Laten we beginnen met het definiëren van een hoekpunt:
class Vertex {String label; Vertex (String label) {this.label = label; } // is gelijk aan en hashCode}De bovenstaande definitie van vertex bevat alleen een label, maar dit kan elke mogelijke entiteit vertegenwoordigen, zoals Persoon of Stad.
Merk ook op dat we moeten de is gelijk aan () en hashCode () methoden, aangezien deze nodig zijn om met Java Collections te werken.
Zoals we eerder hebben besproken, is een grafiek niets anders dan een verzameling hoekpunten en randen die kunnen worden weergegeven als een aangrenzende matrix of een aangrenzende lijst.
Laten we eens kijken hoe we dit kunnen definiëren met behulp van een aangrenzende lijst hier:
klasse Grafiek {privékaart adjVertices; // standard constructor, getters, setters} Zoals we hier kunnen zien, de klas Grafiek gebruikt Kaart van Java Collections om de aangrenzende lijst te definiëren.
Er zijn verschillende bewerkingen mogelijk op een datastructuur van een grafiek, zoals aanmaken, bijwerken of zoeken door de grafiek.
We zullen enkele van de meest voorkomende bewerkingen doornemen en kijken hoe we deze in Java kunnen implementeren.
5. Grafiekmutatiebewerkingen
Om te beginnen zullen we enkele methoden definiëren om de datastructuur van de grafiek te muteren.
Laten we methoden definiëren om hoekpunten toe te voegen en te verwijderen:
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 (nieuw hoekpunt (label)); }Met deze methoden worden eenvoudig elementen toegevoegd aan en verwijderd uit het hoekpunten Set.
Laten we nu ook een methode definiëren om een rand toe te voegen:
void addEdge (String label1, String label2) {Vertex v1 = nieuw hoekpunt (label1); Vertex v2 = nieuwe Vertex (label2); adjVertices.get (v1) .add (v2); adjVertices.get (v2) .add (v1); }Deze methode creëert een nieuw Rand en werkt de aangrenzende hoekpunten bij Kaart.
Op een vergelijkbare manier zullen we de removeEdge () methode:
void removeEdge (String label1, String label2) {Vertex v1 = nieuw hoekpunt (label1); Vertex v2 = nieuwe Vertex (label2); Lijst eV1 = adjVertices.get (v1); Lijst eV2 = adjVertices.get (v2); if (eV1! = null) eV1.remove (v2); if (eV2! = null) eV2.remove (v1); }Laten we vervolgens kijken hoe we de eenvoudige grafiek kunnen maken die we eerder hebben getekend met behulp van de methoden die we tot nu toe hebben gedefinieerd:
Graph createGraph () {Graph graph = nieuwe 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"); terugkeer grafiek; }We zullen eindelijk een methode definiëren om de aangrenzende hoekpunten van een bepaald hoekpunt te krijgen:
List getAdjVertices (String label) {return adjVertices.get (new Vertex (label)); }6. Door een grafiek bladeren
Nu we de datastructuur en functies voor grafieken hebben om deze te maken en bij te werken, kunnen we enkele extra functies definiëren voor het doorlopen van de grafiek. We moeten een grafiek doorlopen om een zinvolle actie uit te voeren, zoals zoeken in de grafiek.
Er zijn twee mogelijke manieren om een grafiek te doorlopen, diepte-eerst doorlopen en breedte-eerst doorlopen.
6.1. Diepte-eerste verplaatsing
Een diepte-eerste traversal begint bij een willekeurig wortelpunt en verkent hoekpunten zo dieper mogelijk langs elke tak voordat hoekpunten op hetzelfde niveau worden verkend.
Laten we een methode definiëren om de diepte eerst door te lopen:
Set depthFirstTraversal (Graph-grafiek, String-root) {Set bezocht = nieuwe LinkedHashSet (); Stack stack = nieuwe Stack (); stack.push (root); while (! stack.isEmpty ()) {String vertex = stack.pop (); if (! bezocht.contains (hoekpunt)) {bezocht.add (hoekpunt); voor (Vertex v: graph.getAdjVertices (vertex)) {stack.push (v.label); }}} terugkeer bezocht; }Hier, we gebruiken een Stapel om de hoekpunten op te slaan die moeten worden doorlopen.
Laten we dit uitvoeren op de grafiek die we in de vorige subsectie hebben gemaakt:
assertEquals ("[Bob, Rob, Maria, Alice, Mark]", depthFirstTraversal (grafiek, "Bob"). toString ());Houd er rekening mee dat we hier hoekpunt "Bob" gebruiken als onze wortel voor traversal, maar dit kan elk ander hoekpunt zijn.
6.2. Breedte-eerste traversal
Relatief gezien begint een breedte-eerste traversal bij een willekeurig wortelpunt en verkent alle aangrenzende hoekpunten op hetzelfde niveau voordat hij dieper gaat in de grafiek.
Laten we nu een methode definiëren om de breedte-eerst-traversal uit te voeren:
Set breadthFirstTraversal (Graph-grafiek, String-root) {Set bezocht = nieuwe LinkedHashSet (); Wachtrij wachtrij = nieuwe LinkedList (); queue.add (root); bezocht.add (root); while (! queue.isEmpty ()) {String vertex = queue.poll (); voor (Vertex v: graph.getAdjVertices (vertex)) {if (! bezocht.contains (v.label)) {bezocht.add (v.label); queue.add (v.label); }}} terugkeer bezocht; }Merk op dat een breedte eerst traversal maakt gebruik van Wachtrij om de hoekpunten op te slaan die moeten worden doorlopen.
Laten we deze traversal opnieuw uitvoeren op dezelfde grafiek:
assertEquals ("[Bob, Alice, Rob, Mark, Maria]", breadthFirstTraversal (grafiek, "Bob"). toString ());Nogmaals, het wortelpunt dat hier "Bob" is, kan net zo goed elk ander hoekpunt zijn.
7. Java-bibliotheken voor grafieken
Het is niet nodig om de grafiek altijd vanuit het niets in Java te implementeren. Er zijn verschillende open source en volwassen bibliotheken beschikbaar die grafische implementaties bieden.
In de volgende subsecties zullen we enkele van deze bibliotheken doornemen.
7.1. JGraphT
JGraphT is een van de meest populaire bibliotheken in Java voor de datastructuur van grafieken. Het maakt het mogelijk om onder andere een eenvoudige grafiek, gerichte grafiek, gewogen grafiek te maken.
Bovendien biedt het veel mogelijke algoritmen voor de datastructuur van de grafiek. Een van onze vorige tutorials behandelt JGraphT veel gedetailleerder.
7.2. Google Guava
Google Guava is een reeks Java-bibliotheken die een reeks functies bieden, waaronder de datastructuur van grafieken en de bijbehorende algoritmen.
Het ondersteunt het creëren van eenvoudig Grafiek, Waardegrafiek, en Netwerk. Deze kunnen worden gedefinieerd als Veranderlijk of Onveranderlijk.
7.3. Apache Commons
Apache Commons is een Apache-project dat herbruikbare Java-componenten biedt. Dit omvat Commons Graph die een toolkit biedt om de datastructuur van grafieken te creëren en te beheren. Dit biedt ook algemene grafiekalgoritmen om op de datastructuur te werken.
7.4. Sourceforge JUNG
Java Universal Network / Graph (JUNG) is een Java-framework dat uitbreidbare taal biedt voor het modelleren, analyseren en visualiseren van alle gegevens die als een grafiek kunnen worden weergegeven.
JUNG ondersteunt een aantal algoritmen, waaronder routines zoals clustering, decompositie en optimalisatie.
Deze bibliotheken bieden een aantal implementaties op basis van de grafische datastructuur. Er zijn ook krachtigere kaders op basis van grafieken, zoals Apache Giraph, dat momenteel op Facebook wordt gebruikt om de grafiek te analyseren die door hun gebruikers wordt gevormd, en Apache TinkerPop, dat vaak wordt gebruikt bovenop grafische databases.
8. Conclusie
In dit artikel hebben we de grafiek besproken als een datastructuur, samen met zijn weergaven. We hebben een heel eenvoudige grafiek in Java gedefinieerd met behulp van Java Collections en we hebben ook algemene traversals voor de grafiek gedefinieerd.
We hebben ook kort gesproken over verschillende bibliotheken die in Java beschikbaar zijn buiten het Java-platform dat grafische implementaties biedt.
Zoals altijd is de code voor de voorbeelden beschikbaar op GitHub.
