In this post we'll see how to write Java program for addition and removal from a graph data structure.
Addition and removal in a graph can be done in the following scenarios-
- Adding a vertex
- Adding an edge
- Removing a vertex
- Removing an edge
Another thing to consider while writing Java program for graph addition, removal is the representation of graph-
- Graph is represented using adjacency matrix
- Graph is represented using adjacency list
Please refer following posts to know more about graph representations-
Graph Adjacency Representation - Java Program
Weighted Graph Adjacency Representation - Java Program
Graph addition removal Java program - Adjacency list representation
In the program, Map storing lists of its neighbours is used as adjacency list representation.
A separate class called Vertex is also there to encapsulate vertex information.
Adding a vertex means, adding that vertex as a key in the Map, along with a new ArrayList as a value.
Adding an edge means adding both the start vertex and the end vertex and the reverse link too if it is an undirected graph.
Removing a vertex means removing that particular key from the Map. Also remove where ever the removed vertex is listed as neighbour for other vertices.
Removing an edge means removing the link from starting point to end point, reverse link for the same vertices should also be removed for an undirected graph.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
/**
* Insert, delete in graph represented as adjacency list
*/
public class GraphDSAL {
Map<Vertex, List<Vertex>> adjList = new HashMap<>();
// Vertex class as nested class
static class Vertex{
String label;
Vertex(String label){
this.label = label;
}
public String getLabel() {
return label;
}
public void setLabel(String label) {
this.label = label;
}
@Override
public int hashCode() {
return Objects.hash(label);
}
@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;
return Objects.equals(label, other.label);
}
}
public void addVertex(Vertex v) {
adjList.putIfAbsent(v, new ArrayList<Vertex>());
}
public void removeVertex(Vertex v) {
// remove vertex
adjList.remove(v);
// remove where ever the removed vertex is listed as neighbour
adjList.values().forEach(e -> e.remove(v));
}
public void addEdge(String source, String destination) {
Vertex vs = new Vertex(source);
Vertex vd = new Vertex(destination);
if(!adjList.containsKey(vs)) {
addVertex(vs);
}
if(!adjList.containsKey(vd)) {
addVertex(vd);
}
adjList.get(vs).add(vd);
// Reverse link also required for undirected graph
adjList.get(vd).add(vs);
}
public void removeEdge(String source, String destination) {
Vertex vs = new Vertex(source);
Vertex vd = new Vertex(destination);
adjList.get(vs).remove(vd);
// Reverse link removal also required for undirected graph
adjList.get(vd).remove(vs);
}
// Method to display graph
public void printGraph() {
adjList.forEach((k, v) -> {
System.out.print("Vertex " + k.getLabel() + " connects to ");
v.forEach(e -> System.out.print(e.getLabel() + " "));
System.out.println();
});
}
public static void main(String[] args) {
GraphDSAL graph = new GraphDSAL();
graph.addVertex(new Vertex("A"));
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "E");
graph.addEdge("C", "D");
graph.addEdge("D", "E");
graph.printGraph();
graph.removeVertex(new Vertex("A"));
//graph.removeEdge("A", "C");
System.out.println("After removal");
graph.printGraph();
}
}
Output
Vertex A connects to B C E Vertex B connects to A Vertex C connects to A D Vertex D connects to C E Vertex E connects to A D After removal Vertex B connects to Vertex C connects to D Vertex D connects to C E Vertex E connects to D
Graph addition removal Java program - Adjacency matrix representation
When graph is represented as an adjacency matrix, that means using a 2-D array to represent a graph.
Adding a vertex means, incrementing the rows and columns of the adjacency matrix by 1 to accommodate new vertex. Copy the rows and columns from the old adjacency matrix to this new one and then assign the new adjacency matrix as the adjacency matrix of the graph.
Adding an edge means changing the row, column value to 1 for the array element, mapping to the start and end vertices for the added edge.
Removing a vertex means, decrementing the rows and columns of the adjacency matrix to represent removal of a vertex. While copying the rows and columns from the old adjacency matrix to this new one ensure that the values for the row and column represented by the removed vertex are not added to the new adjacency matrix. Assign the new adjacency matrix as the adjacency matrix of the graph.
Removing an edge means changing the row, column value to 0 for the array element, mapping to the start and end vertices for the removed edge.
/**
* Insert, delete in graph represented as adjacency matrix
*/
public class GraphDSAM {
private int vertices;
private int[][] adjMatrix;
GraphDSAM(int vertices){
this.vertices = vertices;
adjMatrix = new int[vertices][vertices];
}
public void addEdge(int source, int destination) {
if((source < 0 || source >= vertices) || (destination < 0 || destination >= vertices)) {
System.out.println("Invalid edge addition");
return;
}
adjMatrix[source][destination] = 1;
// For undirected graph reverse setting also required
adjMatrix[destination][source] = 1;
}
public void removeEdge(int source, int destination) {
if((source < 0 || source >= vertices) || (destination < 0 || destination >= vertices)) {
System.out.println("Invalid edge removal");
return;
}
adjMatrix[source][destination] = 0;
// For undirected graph reverse setting also required
adjMatrix[destination][source] = 0;
}
public void addVertex() {
int changedSize = vertices + 1;
int[][] changedAdjMatrix = new int[changedSize][changedSize];
// Copy existing connections
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
changedAdjMatrix[i][j] = adjMatrix[i][j];
}
}
this.adjMatrix = changedAdjMatrix;
vertices = changedSize;
}
public void removeVertex(int v) {
if(v < 0 || v >= vertices){
System.out.println("Invalid vertex removal");
return;
}
int[][] changedAdjMatrix = new int[vertices-1][vertices-1];
// maintaining row for changedAdjMatrix
int tempRow = 0;
for(int i = 0; i < adjMatrix.length; i++) {
if(i == v) {
continue;
}
// maintaining col for changedAdjMatrix
int tempCol = 0;
for(int j = 0; j < adjMatrix[0].length; j++) {
if(j == v) {
continue;
}
changedAdjMatrix[tempRow][tempCol] = adjMatrix[i][j];
tempCol++;
}
tempRow++;
}
this.adjMatrix = changedAdjMatrix;
}
public void printGraph() {
for(int i = 0; i < adjMatrix.length; i++) {
for(int j = 0; j < adjMatrix[0].length; j++) {
System.out.print(adjMatrix[i][j] + "\t");
}
System.out.println();
}
}
public static void main(String[] args) {
GraphDSAM graph = new GraphDSAM(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.printGraph();
System.out.println("After adding a vertex");
graph.addVertex();
graph.addEdge(3, 5);
graph.printGraph();
System.out.println("After removal");
graph.removeEdge(3, 4);
graph.printGraph();
}
}
Output
0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 1 0 After adding a vertex 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 0 After removal 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0
That's all for this topic Java Program to Add and Remove in Graph. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
No comments:
Post a Comment