Eksempel på Java-graf
I dette eksempel vil vi demonstrere et Java-grafeksempel. Vi vil starte med at forklare teorien og begreberne bag grafer, dens typer, grafgennemgang, samt fordele og ulemper ved at bruge en graf. Vi vil gennemgå Java-kode, der implementerer en graf og modellerer dens egenskaber og adfærd. Til sidst vil vi tale om nogle eksterne biblioteker, der kan bruges til at implementere en graf.
1. Introduktion
Grafteori er et populært studieområde inden for matematik. Det har fundet sin anvendelse i forskellige fysiske videnskaber såsom kemi, biologi samt datalogi. Studiet af algoritmer og datastrukturer ville være ufuldstændigt uden omtale af grafer. I denne artikel vil vi definere en graf gennem objektorienteret programmerings øjne og ved hjælp af datastrukturer inden for Java Collections rammer såsom en List , Map og Set .
2. Hvad er en graf?
Fra objektorienteret programmerings perspektiv er en graf en datatype, der består af et sæt toppunkter (eller noder) og kanter. En graf har et begrænset sæt af hjørner og kanter. I figuren nedenfor, der repræsenterer en serverarkitektur, er hjørner repræsenteret af de blå cirkler, og forholdet mellem hjørnerne er repræsenteret af kanterne.
I ovenstående graf af en prøveserverarkitektur er der 12 noder og 12 kanter. Hver node repræsenterer en objekttype, som i dette tilfælde er serverkonfigurationen. Når en anmodning om at hente en HTML-fil kommer til webserveren, kan vi se, hvordan kanterne hjælper os med at følge stien fra det øverste hjørne til hjørnerne i bunden.
3. Typer af grafer
Grafer klassificeres baseret på egenskaberne af deres kanter, og hvordan de linker til hjørnerne. Vi vil dække de mest almindelige klassifikationer af grafer.
3.1 Direkte grafer
Kanterne, der forbinder grafens hjørner, kan være rettede eller urettede. Fig. 1 viser en rettet graf, hvor kanter fanger start- og slutknudepunktet. Dette er i modsætning til en urettet graf, hvor informationen om retningen af kanter ikke lagres. I fig. 2 nedenfor ser vi et eksempel på en urettet graf over et hjemmenetværk. 
3.2 Vægtet graf
Hver kant af en graf kan associeres med en værdi, der repræsenterer vægten af kanten. Denne egenskab kan være særlig nyttig til at bestemme den optimale vej, mens du krydser en graf. For eksempel, i en graf, der repræsenterer netværksforbindelser, kan en vægt tilknyttes til at bestemme styrken af netværkskablets forbindelse.
3.3 Cyklisk graf
En acyklisk graf er en rettet graf, hvor mindst et toppunkt ender med at have en forbindelse eller relation til sig selv.
4. Grafrepræsentation
Der er flere måder at repræsentere en grafdatatype på. Forskellene opstår i de datastrukturer, der bruges til at implementere sættet af toppunkter og kanter. Vi vil se 2 mest almindelige typer grafrepræsentationer.
4.1 Adjacency Matrix
I denne type grafrepræsentation bruges en matrix til at definere hjørnerne og kanterne. Forholdet mellem toppunkter er angivet med 1'er og 0'er. I tabel 1 nedenfor ser vi en tilstødende matrix, der repræsenterer hjemmenetværksgrafen i fig. 2. Da knudepunktet mærket "Basestation" er forbundet til knudepunktet "Hjemmenetværk", er der et 1 i cellen, der svarer til dem.
| Basestation | Hjemmenetværk | Skrivebord 1 | Bærbar computer 1 | Bærbar computer 2 | |
| Basestation | 0 | 1 | 0 | 0 | 0 |
| Hjemmenetværk | 1 | 0 | 1 | 1 | 1 |
| Skrivebord 1 | 0 | 1 | 0 | 0 | 0 |
| Bærbar computer 1 | 0 | 1 | 0 | 0 | 0 |
| Bærbar computer 2 | 0 | 1 | 0 | 0 | 0 |
4.2 Adjacency List
En tilstødende liste er en anden datastruktur, der bruges til at repræsentere listen over tilstødende hjørner i en graf. Vi kan forestille os, at dette er en Map med nøgle/værdi-par. Tasterne repræsenterer hjørnerne, og værdierne er en liste over tilstødende hjørner. I Fig. 3 ser vi, at knudepunktet, der repræsenterer "Hjemmenetværk", har en værdi, der er en liste over de hjørner, det er forbundet til. 
5. Custom Graph-klasse
I dette afsnit vil vi se implementeringen af en graf. Vi vil bruge den rettede graf i fig. 1 som et eksempel og bruge tilstødende listeimplementering til denne graf.
5.1 Anvendte værktøjer
Kodningseksemplerne i denne artikel blev bygget og kørt med følgende værktøjer:
- Java 11
- Maven 3.6.0
- Juni 4.13
- Intellij Idea Edu 2020.1
5.2 Maven Project
I dette afsnit vil vi oprette et Maven-projekt for at implementere en tilpasset Graph-klasse. Som et første skridt vil vi gennemgå pom.xml der indeholder Junit .pom.xml
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>jcg.ssowmya.demo</groupId>
<artifactId>graphExample</artifactId>
<version>1.0-SNAPSHOT</version>
<build>
<sourceDirectory>src</sourceDirectory>
<plugins>
<plugin>
<artifactId>maven-compiler-plugin</artifactId>
<version>3.8.0</version>
<configuration>
<release>11</release>
</configuration>
</plugin>
</plugins>
</build>
<dependencies>
<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>4.13</version>
</dependency>
</dependencies>
</project>
5.3 ServerConfig-klasse
I dette afsnit vil vi se implementeringen af ServerConfig-klassen. Denne klasse vil give hvert hjørne af grafen i fig. 1 mulighed for at indeholde flere oplysninger end blot etiketten.ServerConfig.java
package jcg.ssowmya.demo.graphExample;
public class ServerConfig {
private String name;
private String ipAddress;
private String serverType;
public ServerConfig(String name, String ipAddress, String serverType) {
this.name = name;
this.ipAddress = ipAddress;
this.serverType = serverType;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getIpAddress() {
return ipAddress;
}
public void setIpAddress(String ipAddress) {
this.ipAddress = ipAddress;
}
public String getServerType() {
return serverType;
}
public void setServerType(String serverType) {
this.serverType = serverType;
}
@Override
public String toString() {
return "ServerConfig{" +
"name='" + name + '\'' +
", ipAddress='" + ipAddress + '\'' +
", serverType='" + serverType + '\'' +
'}';
}
}
5.4 ServerVertex-klasse
I dette afsnit vil vi implementere en klasse til at repræsentere hvert hjørne af grafen i Fig. 1. Som vi kan se i denne implementering, tager konstruktøren 2 parametre ind, den ene er label og den anden er et objekt af ServerConfig klasse.ServerVertex.java
package jcg.ssowmya.demo.graphExample;
import java.util.Objects;
public class ServerVertex {
private String label;
private ServerConfig serverConfig;
public ServerVertex(String label,ServerConfig serverConfig) {
this.label = label;
this.serverConfig = serverConfig;
}
public String getLabel() {
return label;
}
public void setLabel(String label) {
this.label = label;
}
public ServerConfig getServerConfig() {
return serverConfig;
}
public void setServerConfig(ServerConfig serverConfig) {
this.serverConfig = serverConfig;
}
@Override
public String toString() {
return "Vertex{" +
"label='" + label + '\'' +
", serverConfig=" + serverConfig +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
ServerVertex serverVertex = (ServerVertex) o;
return getServerConfig().equals(serverVertex.getServerConfig());
}
@Override
public int hashCode() {
return Objects.hash(getServerConfig());
}
}
5.5 ServerEdge-klasse
Denne klasse vil blive brugt til at repræsentere kanterne på en graf. Da Fig. 1 repræsenterer en rettet graf, vil denne klasse have et startpunkt, et slutpunkt, en valgfri vægtegenskab.ServerEdge.java
package jcg.ssowmya.demo.graphExample;
public class ServerEdge {
private ServerVertex start;
private ServerVertex end;
private float weight;
public ServerEdge(ServerVertex start, ServerVertex end) {
this.start = start;
this.end = end;
}
public ServerEdge(ServerVertex start, ServerVertex end, float weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
public ServerVertex getStart() {
return start;
}
public void setStart(ServerVertex start) {
this.start = start;
}
public ServerVertex getEnd() {
return end;
}
public void setEnd(ServerVertex end) {
this.end = end;
}
public float getWeight() {
return weight;
}
public void setWeight(float weight) {
this.weight = weight;
}
@Override
public String toString() {
return "ServerEdge{" +
"start=" + start +
", end=" + end +
", weight=" + weight +
'}';
}
}
5.6 ServerGraph-klasse
Denne klasse vil kombinere objekter fra ovenstående klasser for at implementere en brugerdefineret graf. Denne klasse vil indeholde metoder til at tilføje hjørner og kanter, samt til at fjerne dem. Endelig har klassen metoder til at udføre 2 typer grafgennemgang, som vi vil se nærmere på i det kommende afsnit.ServerGraph.java
package jcg.ssowmya.demo.graphExample;
import java.util.*;
public class ServerGraph {
private Map<ServerVertex, List> adjServerVertices;
public ServerGraph() {
adjServerVertices = new LinkedHashMap();
}
public Map<ServerVertex, List> getAdjServerVertices() {
return adjServerVertices;
}
public void setAdjServerVertices(Map<ServerVertex, List> adjServerVertices) {
this.adjServerVertices = adjServerVertices;
}
public List getAdjVerticesForServerVertex(ServerVertex serverVertex) {
return adjServerVertices.get(serverVertex);
}
public void addServerVertex(ServerVertex serverVertex) {
adjServerVertices.putIfAbsent(serverVertex,new ArrayList());
}
public void removeServerVertexByIpAddress(String ipAddress) {
if(adjServerVertices.isEmpty())
return;
Optional serverVertexOptional = adjServerVertices.keySet().stream().filter(serverVertex -> ipAddress.equals(serverVertex.getServerConfig().getIpAddress())).findAny();
if(!serverVertexOptional.isPresent())
return;
ServerVertex serverVertexToBeRemoved = serverVertexOptional.get();
adjServerVertices.values().stream().forEach(serverVertexList-> {
serverVertexList.remove(serverVertexToBeRemoved);
});
adjServerVertices.remove(serverVertexToBeRemoved);
}
public void addEdge(ServerEdge edge){
adjServerVertices.get(edge.getStart()).add(edge.getEnd());
adjServerVertices.get(edge.getEnd()).add(edge.getStart());
}
public void removeEdge(ServerEdge edge) {
adjServerVertices.get(edge.getStart()).remove(edge.getEnd());
adjServerVertices.get(edge.getEnd()).remove(edge.getStart());
}
public List depthFirstTraversal(ServerVertex root) {
List visitedNodes = new ArrayList();
Stack serverVertexStack = new Stack();
serverVertexStack.push(root);
while(!serverVertexStack.isEmpty()) {
ServerVertex visitedElement = serverVertexStack.pop();
if(!visitedNodes.contains(visitedElement)) {
visitedNodes.add(visitedElement);
for(ServerVertex sv:getAdjVerticesForServerVertex(visitedElement))
serverVertexStack.push(sv);
}
}
return visitedNodes;
}
public List breadthFirstTraversal(ServerVertex root) {
List visitedNodes = new ArrayList();
Queue serverVertexQueue = new LinkedList();
serverVertexQueue.add(root);
visitedNodes.add(root);
while(!serverVertexQueue.isEmpty()) {
ServerVertex visitedElement = serverVertexQueue.poll();
for(ServerVertex sv:getAdjVerticesForServerVertex(visitedElement))
if(!visitedNodes.contains(sv)) {
visitedNodes.add(sv);
serverVertexQueue.add(sv);
}
}
return visitedNodes;
}
@Override
public String toString() {
return "ServerGraph{" +
"adjServerVertices=" + adjServerVertices +
'}';
}
}
5.7 ServerGraphTest-klasse
I dette afsnit vil vi se en Junit-testklasse for at verificere og validere vores tilpassede klasse ServerGraph .ServerGraphTest.java
package jcg.ssowmya.demo.graphExample;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
public class ServerGraphTest {
@Test
public void testGraphServerVertices() {
ServerGraph serverGraph = new ServerGraph();
assertNotNull(serverGraph.getAdjServerVertices());
serverGraph.addServerVertex(new ServerVertex("WS1:Web Server", new ServerConfig("JCG Web Server 1","1.2.3.4","Web")));
assertEquals(1,serverGraph.getAdjServerVertices().size());
serverGraph.removeServerVertexByIpAddress("1.2.3.4");
assertEquals(0,serverGraph.getAdjServerVertices().size());
}
@Test
public void testGraphServerEdges() {
ServerGraph serverGraph = new ServerGraph();
ServerVertex wsVertex= new ServerVertex("WS1:Web Server",new ServerConfig("JCG Web Server 1","1.2.3.4","Web"));
ServerVertex lb1Vertex = new ServerVertex("LB1:Load Balancer 1", new ServerConfig("JCG Load Balance Server 1","1.2.3.5","Load Balancer"));
serverGraph.addServerVertex(wsVertex);
serverGraph.addServerVertex(lb1Vertex);
assertEquals(2,serverGraph.getAdjServerVertices().size());
serverGraph.addEdge(new ServerEdge(wsVertex,lb1Vertex));
assertEquals(1,serverGraph.getAdjServerVertices().get(wsVertex).size());
assertEquals(1,serverGraph.getAdjServerVertices().get(lb1Vertex).size());
serverGraph.removeEdge(new ServerEdge(wsVertex,lb1Vertex));
assertEquals(0,serverGraph.getAdjServerVertices().get(wsVertex).size());
assertEquals(0,serverGraph.getAdjServerVertices().get(lb1Vertex).size());
}
}
6. Grafgennemgang
Der er 2 måder, hvorpå en graf kan krydses:Bredde-først og Dybde-først. Vi vil ved hjælp af kode forstå, hvordan de begge adskiller sig.
6.1 ServerGraphTraversalTest-klasse
I dette afsnit vil vi implementere en klasse, der tester de 2 typer grafgennemgangsmetoder.ServerGraphTest.java
package jcg.ssowmya.demo.graphExample;
import org.junit.Before;
import org.junit.Test;
import java.util.List;
import static org.junit.Assert.assertNotNull;
public class ServerGraphTraversalTest {
private ServerGraph serverGraph;
private ServerVertex root;
@Before
public void initializeGraph() {
serverGraph = new ServerGraph();
ServerVertex wsVertex= new ServerVertex("WS1:Web Server",new ServerConfig("JCG Web Server 1","1.2.3.4","Web"));
ServerVertex lb1Vertex = new ServerVertex("LB1:Load Balancer 1", new ServerConfig("JCG Load Balance Server 1","1.2.3.5","Load Balancer"));
ServerVertex lb2Vertex = new ServerVertex("LB2:Load Balancer 2", new ServerConfig("JCG Load Balance Server 2","1.2.3.6","Load Balancer"));
ServerVertex ps1Vertex = new ServerVertex("PS1:Proxy Server Instance 1", new ServerConfig("Proxy Server Instance 1","1.2.3.7","Proxy Server"));
ServerVertex ps2Vertex = new ServerVertex("PS2:Proxy Server Instance 2", new ServerConfig("Proxy Server Instance 2","1.2.3.8","Proxy Server"));
ServerVertex ps3Vertex = new ServerVertex("PS3:Proxy Server Instance 3", new ServerConfig("Proxy Server Instance 3","1.2.3.9","Proxy Server"));
serverGraph.addServerVertex(wsVertex);
serverGraph.addServerVertex(lb1Vertex);
serverGraph.addServerVertex(lb2Vertex);
serverGraph.addServerVertex(ps1Vertex);
serverGraph.addServerVertex(ps2Vertex);
serverGraph.addServerVertex(ps3Vertex);
serverGraph.addEdge(new ServerEdge(wsVertex,lb1Vertex));
serverGraph.addEdge(new ServerEdge(wsVertex,lb2Vertex));
serverGraph.addEdge(new ServerEdge(lb1Vertex,ps1Vertex));
serverGraph.addEdge(new ServerEdge(lb1Vertex,ps2Vertex));
serverGraph.addEdge(new ServerEdge(lb2Vertex,ps3Vertex));
root = wsVertex;
}
@Test
public void testBreadthFirstTraversal() {
List visitedList = serverGraph.breadthFirstTraversal(root);
assertNotNull(visitedList);
System.out.println("Breadth first traversal search path : ");
visitedList.stream().forEach(sv->System.out.println(sv.getLabel()));
}
@Test
public void testDepthFirstTraversal() {
List visitedList = serverGraph.depthFirstTraversal(root);
assertNotNull(visitedList);
System.out.println("Depth first traversal search path : ");
visitedList.stream().forEach(sv->System.out.println(sv.getLabel()));
}
}
6.2 Breadth First Traversal
Bredth-first traversal, som navnet antyder, betyder, at alle noderne på et bestemt niveau på grafen først besøges, før man fortsætter ned til næste niveau. Så det involverer at besøge alle noder på tværs af grafens bredde, før du fortsætter med at gå ned.
Når vi kører metoden testBreadthFirstTraversal() ved at køre kommandoen mvn -Dtest=ServerGraphTraversalTest#testBreadthFirstTraversal test fra projektkildemappen ser vi følgende output:Output af ServerGraphTraversalTest#testBreadthFirstTraversal()-metoden
~/IdeaProjects/graphExample$ mvn -Dtest=ServerGraphTraversalTest#testBreadthFirstTraversal test WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.google.inject.internal.cglib.core.$ReflectUtils$1 (file:/usr/share/maven/lib/guice.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int,java.security.ProtectionDomain) WARNING: Please consider reporting this to the maintainers of com.google.inject.internal.cglib.core.$ReflectUtils$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release [INFO] Scanning for projects... [INFO] [INFO] --------------------------------------- [INFO] Building graphExample 1.0-SNAPSHOT [INFO] --------------------------------[ jar ]--------------------------------- [INFO] [INFO] --- maven-resources-plugin:2.6:resources (default-resources) @ graphExample --- [WARNING] Using platform encoding (UTF-8 actually) to copy filtered resources, i.e. build is platform dependent! [INFO] Copying 0 resource [INFO] [INFO] --- maven-compiler-plugin:3.8.0:compile (default-compile) @ graphExample --- [INFO] Changes detected - recompiling the module! [WARNING] File encoding has not been set, using platform encoding UTF-8, i.e. build is platform dependent! [INFO] Compiling 6 source files to /home/vsowmya/IdeaProjects/graphExample/target/classes [INFO] [INFO] --- maven-resources-plugin:2.6:testResources (default-testResources) @ graphExample --- [WARNING] Using platform encoding (UTF-8 actually) to copy filtered resources, i.e. build is platform dependent! [INFO] skip non existing resourceDirectory /home/vsowmya/IdeaProjects/graphExample/src/test/resources [INFO] [INFO] --- maven-compiler-plugin:3.8.0:testCompile (default-testCompile) @ graphExample --- [INFO] Changes detected - recompiling the module! [WARNING] File encoding has not been set, using platform encoding UTF-8, i.e. build is platform dependent! [INFO] Compiling 2 source files to /home/vsowmya/IdeaProjects/graphExample/target/test-classes [INFO] [INFO] --- maven-surefire-plugin:2.12.4:test (default-test) @ graphExample --- [INFO] Surefire report directory: /home/vsowmya/IdeaProjects/graphExample/target/surefire-reports ------------------------------------------------------- T E S T S ------------------------------------------------------- Running jcg.ssowmya.demo.graphExample.ServerGraphTraversalTest Breadth first traversal search path : WS1:Web Server LB1:Load Balancer 1 LB2:Load Balancer 2 PS1:Proxy Server Instance 1 PS2:Proxy Server Instance 2 PS3:Proxy Server Instance 3 Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.089 sec Results : Tests run: 1, Failures: 0, Errors: 0, Skipped: 0 [INFO] ------------------------------------------------------------------------ [INFO] BUILD SUCCESS [INFO] ------------------------------------------------------------------------ [INFO] Total time: 3.470 s [INFO] Finished at: 2020-05-29T18:15:09-04:00 [INFO] ------------------------------------------------------------------------
Forudsat at vi starter med roden som knudepunktet med etiketten "WS1:Web Server" som niveau 0. Fra outputtet ser vi, at alle noderne på niveau 1, med etiketterne "LB1:Load Balancer 1" og "LB2 :Load Balancer 2” besøges først. Tilsvarende med niveau 2. Ved at observere breadthFirstTraversal metode i ServerGraph klasse, ser vi, at vi gør brug af en Queue og en LinkedList implementering for at spore de besøgte noder.
6.3 Dybde første gennemløb
Dybdegående første gennemgang, søgningen starter med en rodknude og fortsætter helt ned til det laveste niveau, og kommer derefter op igen for at besøge de andre knudepunkter på et niveau. Med andre ord giver gennemkørslen prioritet til dybden end bredden af en node. For at forstå dette bedre, lad os se på, hvordan rækkefølgen af besøgte noder ser ud i testDepthFirstTraversal() metode til ServerGraphTraversalTest klasse. For at køre denne testmetode skal vi udføre mvn -Dtest=ServerGraphTraversalTest#testDepthFirstTraversal test fra projektets kildemappe på kommandolinjen.Output af ServerGraphTraversalTest#testDepthFirstTraversal()-metoden
~/IdeaProjects/graphExample$ mvn -Dtest=ServerGraphTraversalTest#testDepthFirstTraversal test WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.google.inject.internal.cglib.core.$ReflectUtils$1 (file:/usr/share/maven/lib/guice.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int,java.security.ProtectionDomain) WARNING: Please consider reporting this to the maintainers of com.google.inject.internal.cglib.core.$ReflectUtils$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release [INFO] Scanning for projects... [INFO] [INFO] --------------------------------------- [INFO] Building graphExample 1.0-SNAPSHOT [INFO] --------------------------------[ jar ]--------------------------------- [INFO] [INFO] --- maven-resources-plugin:2.6:resources (default-resources) @ graphExample --- [WARNING] Using platform encoding (UTF-8 actually) to copy filtered resources, i.e. build is platform dependent! [INFO] Copying 0 resource [INFO] [INFO] --- maven-compiler-plugin:3.8.0:compile (default-compile) @ graphExample --- [INFO] Changes detected - recompiling the module! [WARNING] File encoding has not been set, using platform encoding UTF-8, i.e. build is platform dependent! [INFO] Compiling 6 source files to /home/vsowmya/IdeaProjects/graphExample/target/classes [INFO] [INFO] --- maven-resources-plugin:2.6:testResources (default-testResources) @ graphExample --- [WARNING] Using platform encoding (UTF-8 actually) to copy filtered resources, i.e. build is platform dependent! [INFO] skip non existing resourceDirectory /home/vsowmya/IdeaProjects/graphExample/src/test/resources [INFO] [INFO] --- maven-compiler-plugin:3.8.0:testCompile (default-testCompile) @ graphExample --- [INFO] Nothing to compile - all classes are up to date [INFO] [INFO] --- maven-surefire-plugin:2.12.4:test (default-test) @ graphExample --- [INFO] Surefire report directory: /home/vsowmya/IdeaProjects/graphExample/target/surefire-reports ------------------------------------------------------- T E S T S ------------------------------------------------------- Running jcg.ssowmya.demo.graphExample.ServerGraphTraversalTest Depth first traversal search path : WS1:Web Server LB2:Load Balancer 2 PS3:Proxy Server Instance 3 LB1:Load Balancer 1 PS2:Proxy Server Instance 2 PS1:Proxy Server Instance 1 Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.081 sec Results : Tests run: 1, Failures: 0, Errors: 0, Skipped: 0 [INFO] ------------------------------------------------------------------------ [INFO] BUILD SUCCESS [INFO] ------------------------------------------------------------------------ [INFO] Total time: 3.404 s [INFO] Finished at: 2020-05-29T23:25:53-04:00 [INFO] ------------------------------------------------------------------------
Fra ovenstående output kan vi se, hvordan gennemgangen går helt ned til noden mærket "PS3:Proxy Server Instance 3", og derefter dækker de andre noder på niveau 1. Fra at se på implementeringen af depthFirstTraversal() metode i ServerGraph klasse, ser vi, at vi bruger en Stack at skubbe og pop besøgte noder.
7. Graf fordele og ulemper
Vi finder mange virkelige anvendelser af grafer. Kort, sociale netværkssider, trafik og transportsoftware er nogle applikationer, der er stærkt afhængige af grafer. Lad os se på fordele og ulemper ved grafer som datastrukturer.
7.1 Fordele
- Grafdatastrukturen gør det nemt at repræsentere forældre/barn- og søskendeforhold. Herigennem kan vi visualisere, hvordan vi gør dataene i vores applikationer hierarkiske.
- Graffer er nemme datastrukturer, der giver os mulighed for at opdele komplekse problemer i mindre, enklere dele. Det er ikke underligt, at grafer er fundamentet for kort/GPS-navigationssoftware, hvor gennemløbsalgoritmer kan optimeres til at finde den korteste vej mellem 2 noder.
- I operativsystemer bruges ressourceallokeringsgrafer til at studere processer og ressourcer, der er allokeret til dem, samt interaktionen mellem forskellige processer og disse ressourcer. Grafer hjælper med at identificere og forhindre dødvande.
- Sociale netværkswebsteder bruger grafteoriens begreber til at repræsentere mennesker og forholdet mellem dem.
7.2 Ulemper
- Graffer står over for begrænsninger, når det kommer til den måde, de implementeres på. Teorien og begreberne bag grafer kan ikke oversættes som de er med hukommelsens perspektiv. Derfor er den måde, vi visualiserer en graf på, forskellig fra, hvordan den faktisk er gemt i hukommelsen.
- De fleste programmeringssprog, inklusive Java, giver ikke en Graph-klasse. Derfor er der ingen standard måde at implementere denne datastruktur på.
8. Biblioteker, der implementerer Graphs
I dette afsnit vil vi se på nogle open source-biblioteker, der implementerer grafer i Java.
- JGraphT tilbyder en fleksibel, kraftfuld og effektiv API til implementering af grafer. Det dækker alle typer grafer, såvel som traversalalgoritmer, med mulighed for også at integrere med andre grafbiblioteker
- Googles Guava er et sæt grafbiblioteker, der tilbydes og bruges af Google.
- Apache Commons Graph er et sæt Graph API, der tilbydes af Apache Commons
- JUNG – Java Universal Network Graph-bibliotek er en anden open source API til grafvisualisering.
9. Resumé
For at opsummere er grafer en meget enkel og interessant datastruktur at udforske og bruge til at løse mange problemer. Gennem denne artikel har vi dækket de grundlæggende begreber i en graf og implementeret en brugerdefineret Java-graf.
10. Download kildekoden
Dette var et eksempel på Java Graph.
