A system that automatically recycles unused memory in a programming language.
Pros -
- Makes programming easier
- Helps developers to avoid several memory problems
Cons -
- Consumes computing resources
- Consumes memory to store status of objects
- Recycle process may even block the program potentially
Memory Problems -
- Dangling pointers - point to an object that no longer exists
- Freeing a region of memory that s already free
- Memory leaks - Unreachable region of memory that can never be freed
Designing Garbage Collection - All objects in-memory heap are like a directional graph. All the nodes(vertices) which are not reachable from root(s) can be freed.
Problem - Find unreachable nodes in a directional graph
Solution -
Edge.java
public class Edge<T> {
private final int cost;
private final Vertex<T> to;
private final Vertex<T> from;
public Edge(Vertex<T> from, Vertex<T> to, int cost) {
this.cost = cost;
this.to = to;
this.from = from;
}
public Vertex<T> getTo() { return to; }
public Vertex<T> getFrom() { return from; }
@Override public boolean equals(Object obj) {
Objects.requireNonNull(obj);
if(this==obj) return true;
Edge other = null;
if(obj instanceof Edge)
other = (Edge)obj;
if (!this.getFrom().equals(other.getFrom())) return false;
if (!this.getTo().equals(other.getTo())) return false;
return true;
}
}
Vertex.java
public class Vertex<T> {
private Color markState;
private final String name;
private final T value;
private List<Edge<T>> edges;
private List<Edge<T>> incomingEdges;
private List<Edge<T>> outgoingEdges;
public Vertex(String name, T value) {
this.name = name;
this.value = value;
incomingEdges = new ArrayList<>();
outgoingEdges = new ArrayList<>();
edges = new ArrayList<>();
}
public Edge<T> findEdge(com.graph.Vertex<T> to) {
Optional<Edge<T>> e = edges.stream()
.filter(edge -> edge.getFrom().equals(this) && edge.getTo().equals(to))
.findAny();
return e.isPresent() ? e.get():null;
}
public void addEdge(Edge<T> e, boolean isIncoming) {
this.edges.add(e);
if (isIncoming) { incomingEdges.add(e);
} else { outgoingEdges.add(e); }
}
public void remove(Edge<T> e) {
incomingEdges.remove(e);
outgoingEdges.remove(e);
edges.remove(e);
}
public void clearMark() { this.markState = null; }
public void setMarkState(Color markState) {
this.markState = markState;
}
public Color getMarkState() { return markState; }
public String getName() { return name; }
public T getValue() { return value; }
public List<Edge<T>> getOutgoingEdges() { return outgoingEdges; }
public List<Edge<T>> getIncomingEdges() { return incomingEdges; }
}
Color.java
public enum Color { BLACK, WHITE, GREY }
Graph.java
class Graph<T> {
Set<Vertex<T>> vertices;
List<Edge<T>> edges;
Vertex rootVertex;
public Graph() {
vertices = new HashSet<>();
edges = new ArrayList<>();
}
public boolean isEmpty() { return size() == 0; }
public Vertex getRootVertex() { return rootVertex; }
public void setRootVertex(Vertex rootVertex) {
this.rootVertex = rootVertex;
this.addVertex(rootVertex);
}
public Vertex getVertex(T value) {
return vertices.stream().filter(val -> value.equals(val)).findAny().get();
}
public boolean addEdge(Vertex<T> from, Vertex<T> to, int cost) {
if (!(vertices.contains(from) || vertices.contains(to))) {
throw new NoSuchElementException("Element not found");
}
Edge<T> e = new Edge<T>(from, to, cost);
if (from.findEdge(to) == null) {
from.addEdge(e, false);
to.addEdge(e, true);
edges.add(e);
return true;
}
return false;
}
private int size() { return vertices.size(); }
public boolean addVertex(Vertex<T> vertex) {
Objects.requireNonNull(vertices, "Vertices are null");
return vertices.add(vertex);
}
public boolean insertBiEdge(Vertex<T> from, Vertex<T> to, int cost)
throws IllegalArgumentException {
return addEdge(from, to, cost) && addEdge(to, from, cost);
}
public Vertex<T> findVertexByName(String name) {
return vertices.stream().filter(vertex -> vertex.getName().equals(name))
.findAny().get();
}
public Vertex<T> findVertexByValue(T value) {
return vertices.stream().filter(vertex -> value.equals(vertex.getValue()))
.findAny().get();
}
public String toString() {
StringBuffer tmp = new StringBuffer("Graph[");
vertices.stream().forEach(v -> tmp.append(v.getValue()).append(" "));
tmp.append(']');
return tmp.toString();
}
public boolean removeVertex(Vertex<T> v) {
if (v == rootVertex)
rootVertex = null;
// Remove the edges associated with v
v.getOutgoingEdges().forEach(e -> {
v.remove(e);
Vertex<T> to = e.getTo();
to.remove(e);
edges.remove(e);
});
v.getIncomingEdges().forEach(e -> {
v.remove(e);
Vertex<T> from = e.getFrom();
from.remove(e);
edges.remove(e);
});
return true;
}
public boolean removeEdge(Vertex<T> from, Vertex<T> to) {
Edge<T> e = from.findEdge(to);
if (e != null) {
from.remove(e);
to.remove(e);
edges.remove(e);
return true;
}
return false;
}
public void clearMark() {
vertices.stream().forEach(vertex -> vertex.clearMark());
}
public void garbageCollection() {
vertices.stream().forEach(v -> v.setMarkState(Color.WHITE));
visit(getRootVertex());
vertices.stream().filter(vertex -> vertex.getMarkState() == Color.WHITE)
.forEach(vertex -> removeVertex(vertex));
vertices.removeIf(vertex -> vertex.getMarkState() == Color.WHITE);
clearMark(); }
private void visit(Vertex<T> v) {
v.setMarkState(Color.GREY);
v.getOutgoingEdges().stream().forEach(edge -> {
Vertex<T> u = edge.getTo();
if (u.getMarkState() == Color.WHITE)
visit(u);
v.setMarkState(Color.BLACK); });
}
Main class - DirectionalGraph.java
public class DirectionalGraph {
public static void main(String[] args) {
Graph graph = new Graph();
Vertex<String> vertexA = new Vertex<>("a", "a");
Vertex<String> vertexB = new Vertex<>("b", "b");
Vertex<String> vertexC = new Vertex<>("c", "c");
Vertex<String> vertexD = new Vertex<>("d", "d");
Vertex<String> vertexE = new Vertex<>("e", "e");
Vertex<String> vertexF = new Vertex<>("f", "f");
graph.setRootVertex(vertexA);
graph.addVertex(vertexA);
graph.addVertex(vertexB);
graph.addVertex(vertexC);
graph.addVertex(vertexD);
graph.addVertex(vertexE);
graph.addVertex(vertexF);
graph.addEdge(vertexA, vertexB, 5);
graph.addEdge(vertexA, vertexC, 5);
graph.addEdge(vertexB, vertexD, 5);
graph.addEdge(vertexB, vertexE, 5);
graph.addEdge(vertexD, vertexE, 5);
System.out.println(graph);
graph.garbageCollection();
System.out.println(graph);
}
}
Output -
Graph[e d b a c f ]
Graph[e d b a c ]
- As f is not connected to any node is removed from Graph. Garbage collected
