Grafer i Java

1. Översikt

I den här handledningen förstår vi de grundläggande begreppen i en graf som datastruktur .

Vi kommer också att undersöka dess implementering i Java tillsammans med olika möjliga operationer i en graf. Vi kommer också att diskutera Java-biblioteken som erbjuder grafimplementeringar.

2. Grafdatastruktur

En graf är en datastruktur för lagring av ansluten data som ett nätverk av människor på en social medieplattform.

En graf består av hörn och kanter. Ett toppunkt representerar enheten (till exempel människor) och en kant representerar förhållandet mellan enheter (till exempel en persons vänskap).

Låt oss definiera en enkel graf för att förstå detta bättre:

Här har vi definierat en enkel graf med fem hörn och sex kanter. Cirklarna är hörn som representerar människor och linjerna som förbinder två hörn är kanter som representerar vänner på en online-portal.

Det finns några varianter av denna enkla graf beroende på kanternas egenskaper. Låt oss gå igenom dem i nästa avsnitt.

Vi fokuserar dock bara på det enkla diagrammet som presenteras här för Java-exemplen i denna handledning.

2.1. Regisserad graf

Grafen vi hittills har definierat har kanter utan någon riktning. Om dessa kanter har en riktning i dem är den resulterande grafen känd som en riktad graf.

Ett exempel på detta kan vara att representera vem som skickar vänförfrågan i en vänskap på onlineportalen:

Här kan vi se att kanterna har en fast riktning. Kanterna kan också vara dubbelriktade.

2.2. Vägt diagram

Återigen har vår enkla graf kanter som är opartiska eller oviktade. Om dessa kanter istället har relativ vikt , är denna graf känd som ett viktat diagram.

Ett exempel på en praktisk tillämpning av detta kan vara att representera hur relativt gammal en vänskap är på onlineportalen:

Här kan vi se att kanterna har vikter förknippade med dem. Detta ger en relativ betydelse för dessa kanter.

3. Grafrepresentationer

En graf kan representeras i olika former som angränsande matris och angränsningslista. Var och en har sina för- och nackdelar i olika inställningar.

Vi presenterar dessa grafrepresentationer i detta avsnitt.

3.1. Adjacency matris

En angränsande matris är en kvadratmatris med dimensioner som motsvarar antalet hörn i diagrammet.

Elementen i matrisen har vanligtvis värdena '0' eller '1'. Värdet "1" anger närhet mellan hörn i raden och kolumnen och annars ett värde på "0".

Låt oss se hur närhetsmatrisen ser ut för vårt enkla diagram från föregående avsnitt:

Denna representation är ganska lättare att implementera och effektiv att fråga . Det är dock mindre effektivt med avseende på rymdupptagning .

3.2. Adjacency List

En angränsande lista är bara en rad listor . Storleken på matrisen motsvarar antalet hörn i diagrammet.

Listan vid ett specifikt index i matrisen representerar de intilliggande topparna i toppunkten som representeras av det matrisindexet.

Låt oss se hur angränsningslistan ser ut för vårt enkla diagram från föregående avsnitt:

Denna framställning är relativt svår att skapa och mindre effektiv att fråga . Det ger dock bättre rymdeffektivitet .

Vi använder angränsningslistan för att representera grafen i denna handledning.

4. Grafer i Java

Java har inte en standardimplementering av grafdatastrukturen.

Vi kan dock implementera grafen med hjälp av Java Collections.

Låt oss börja med att definiera en toppunkt:

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

Ovanstående definition av vertex har bara en etikett men det kan representera alla möjliga enheter som Person eller City.

Observera också att vi måste åsidosätta metoderna lika () och hashCode () eftersom dessa är nödvändiga för att arbeta med Java-samlingar.

Som vi diskuterade tidigare är en graf ingenting annat än en samling hörn och kanter som kan representeras antingen som en angränsningsmatris eller en angränsningslista.

Låt oss se hur vi kan definiera detta med hjälp av en angränsningslista här:

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

Som vi kan se här använder klassen Graph Map från Java Collections för att definiera närliggande listan.

Det finns flera operationer möjliga i en grafdatastruktur, som att skapa, uppdatera eller söka igenom diagrammet .

Vi går igenom några av de vanligaste operationerna och ser hur vi kan implementera dem i Java.

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.

Dessa bibliotek tillhandahåller ett antal implementeringar baserat på grafdatastrukturen. Det finns också mer kraftfulla ramar baserade på grafer , som Apache Giraph, som för närvarande används på Facebook för att analysera grafen som bildats av sina användare, och Apache TinkerPop, som ofta används ovanpå grafdatabaser.

8. Slutsats

I den här artikeln diskuterade vi grafen som en datastruktur tillsammans med dess representationer. Vi definierade en mycket enkel graf i Java med Java-samlingar och definierade också vanliga traversaler för grafen.

Vi pratade också kort om olika bibliotek tillgängliga i Java utanför Java-plattformen som tillhandahåller grafimplementeringar.

Som alltid finns koden för exemplen tillgänglig på GitHub.