How do I print out the results of a breadth-first transversal using the example code from GitHub? where should I put the Main method? Thanks, here's the code link for the first class: https://github.com/eugenp/tutorials/blob/master/data-structures/src/main/java/com/baeldung/graph/Graph.java and here's the code:
package com.baeldung.graph;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class Graph {
private Map<Vertex, List<Vertex>> adjVertices;
Graph() {
this.adjVertices = new HashMap<Vertex, List<Vertex>>();
}
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));
}
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);
}
void removeEdge(String label1, String label2) {
Vertex v1 = new Vertex(label1);
Vertex v2 = new Vertex(label2);
List<Vertex> eV1 = adjVertices.get(v1);
List<Vertex> eV2 = adjVertices.get(v2);
if (eV1 != null)
eV1.remove(v2);
if (eV2 != null)
eV2.remove(v1);
}
List<Vertex> getAdjVertices(String label) {
return adjVertices.get(new Vertex(label));
}
String printGraph() {
StringBuffer sb = new StringBuffer();
for(Vertex v : adjVertices.keySet()) {
sb.append(v);
sb.append(adjVertices.get(v));
}
return sb.toString();
}
class Vertex {
String label;
Vertex(String label) {
this.label = label;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + getOuterType().hashCode();
result = prime * result + ((label == null) ? 0 : label.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Vertex other = (Vertex) obj;
if (!getOuterType().equals(other.getOuterType()))
return false;
if (label == null) {
if (other.label != null)
return false;
} else if (!label.equals(other.label))
return false;
return true;
}
@Override
public String toString() {
return label;
}
private Graph getOuterType() {
return Graph.this;
}
}
}
Here's the link for the second class: https://github.com/eugenp/tutorials/blob/master/data-structures/src/main/java/com/baeldung/graph/GraphTraversal.java and here's the code:
package com.baeldung.graph;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import com.baeldung.graph.Graph.Vertex;
public class GraphTraversal {
static Set<String> depthFirstTraversal(Graph graph, String root) {
Set<String> visited = new LinkedHashSet<String>();
Stack<String> stack = new Stack<String>();
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;
}
static Set<String> breadthFirstTraversal(Graph graph, String root) {
Set<String> visited = new LinkedHashSet<String>();
Queue<String> queue = new LinkedList<String>();
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;
}
}
If I understood your question correctly, you're trying to print a Graph and aren't sure where to put the main() method. You can simply put it in the graph class if you're just testing the code, but if you're trying to build a project using this class, you might want to make a different class to store the main() method.
Printing is straightforward since they give a Set<String>. Just add the following line before the method returns the visited nodes. This converts the visited nodes list to a string.
System.out.println(visited.toString());
You can test it with the following code:
static 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;
}
public static void main(String[] args) {
Graph graph = createGraph();
GraphTraversal.breadthFirstTraversal(graph, "Bob");
}
Which gives:
[Bob, Alice, Rob, Mark, Maria]
Additionally, you commented that you get a NullPointerException when you try to add vertices. There isn't enough information to figure out why you get the exception, but it may be helpful for you to check the unit tests, to figure out how to make use of the class. The unit tests are here.