Whenever I study Garbage Collector I hear the term object Graph. What does it mean exactly?


Objects have references to other objects which may in turn have references to more objects including the starting object. This creates a graph of objects, useful in reachability analysis. For instance, if the starting object is reachable (say it's in a thread's local stack) then all objects in the graph are reachable and an exact garbage collector cannot harvest any of these objects. Similarly, starting with a set of live objects (roots) if we create a list of all reachable objects, all other objects are garbage - fair game for collection.

  • 2
    Re "not all": I think, all objects have references to other objects, at the very least a reference to their class. – Thilo Jan 12 '10 at 5:32

An 'Object Graph' is the conceptualization of all instances of the objects from your object model (the classes in your program) and their interconnections.

Take for example:

You have two classes

Class Foo
    String aString = "foo";
    Bar aBar;

Class Bar
    String aString = "boo";

If you were to create an instance, Foo myFoo and then create an instance of Bar myBar, and connect them, myFoo.aBar = myBar;, your object graph would consist of a single instance of Foo with a reference to a single instance of Bar.

The garbage collector essentially uses the object graph to determine which instances in memory are still linked to something and possibly needed by the program, and which instances are no longer accessible and therefore can be deleted.

Someone on wikipedia puts it more eloquently than me:

Object-oriented applications contain complex webs of interrelated objects. Objects are linked to each other by one object either owning or containing another object or holding a reference to another object. This web of objects is called an object graph and it is the more abstract structure that can be used in discussing an application's state.


What we are talking about is the mathematical notion of a directed graph that consists of nodes and edges that connect the nodes. An object graph is some graph whose nodes are objects, and whose edges are relationship of interest between the objects.

In the case of the Java garbage collector, the object graph of concern is the graph of reachable objects. In this graph, the nodes are Java objects, and the edges are the explicit or implied references that allow a running program to "reach" other objects from a given one. (For example of an implied reference, there is an implied reference from an object to it's Class object, and hence to the heap objects holding the classes statics and its code ... but I digress.)

As @Chandra Patni explained, garbage collection works by traversing the reachability graph consisting of all objects that can be reached from one of a set of starting points; the "root set" in GC terminology. Any object that is not found in this graph traversal can no longer influence the computation, and is therefore eligible to be garbage collected.


Object graph is basically a dependency graph between objects

It is used to determine which objects are reachable and which not, so that all unreachable objects could be made eligible for garbage collection.

  • 1
    I don't know. I was inclined to downvote because you described the reachability graph as a dependency graph :-) – Stephen C Jan 12 '10 at 5:27

Object graph is a network of instances of classes of our application/software that currently exist in memory.

Click to see image: http://blog.ploeh.dk/content/binary/Windows-Live-Writer/Compose-object-graphs-with-confidence_921A/Tree_1.png

It can be a long chain of objects to a short one object graph also. E.g.: lets say we have classes like PetDog, Owner, PetKennel in a application. Now, PetDog has owner, Owner have one or many PetDog, PetDog is trained from a PetKennel and a PetKennel trains many PedDog. Now on implementation of those relationships in Object Oriented Approach we, a Owner (lets say you: a instance/object of Owner class) might reference (link to) many PetDog instances (if you have many dogs else you reference to only one PetDog), again a PetDog references to its particular owner instance/object (that is you in your's dogs case, Mr. John will be referenced by (linked to) his dog), you might have bought pet dog from different kennel club (where dogs are trained and sold also) then each of PetDog instances/objects references/linked to their particular Kennel clubs. This creates a complex network of objects related to each other.

If you happen to represent each instances/objects (each objects of PetDog, Owner, PetKennel) as circle/square (or any shape) in your note/sketch book and draw arrow or lines to represent who object is linked (referencing) with which object then you create a object graph.

Sometime it happens that when you delete or change links between those instances of any class then some instances might not be referenced (linked) to any other instances which will be removed by garbage collector.


As we know Objects are instance of a Class. An Object may have reference to the other object (use of Pointers for addressing). Also these objects may have reference to another object and so on leading into a Hierarchy of Objects references to each other.

This is an Object Graph.

Your Answer

