Garbage Collection

 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