Dependency Graph Construction

Dependency Graph in Maven

Maven provides an implementation for building dependency trees (*) for a module. The implementation can be found in the org.apache.maven.shared.dependency.graph package. The entry point is the class DependencyGraphBuilder which is able to create a dependency tree consisting of nested DependencyNode objects. Dependency nodes can be visited using implementations of the DependencyNodeVisitor interface. Dependency nodes are always visited in depth-first order, meaning that the visitation follows the children of a node first before moving on to the next node. The visitor provides the two methods visit(DependencyNode) and endVisit(DependencyNode). The former is called when a new node is visited, the latter when the node and all of its children were completely visited.

(*) The resolved dependencies of a maven module do always form a tree. There are neither cycles nor different paths from one dependency to another.

Bottom-up Dependency Graph Construction

This Maven plugin uses its own DependencyNodeVisitor implementation to build the dependency graph output. It uses a bottom-up strategy for constructing the dependency graph. It starts with the child nodes and build the graph up to the root node. To keep track of a child node's location in the graph, the visitor uses a stack where all parent elements of a node are pushed. So the top of the stack does always contain the immediate parent of the node that is currently visited.

The startVisit() method is only used to build up the stack. The endVisit() method constructs an edge consisting of the currently visited node and its parent on the top of the stack.

Example

The table below describes the visitation of a module A with this dependency tree (red indicates a change to the stack or the constructed graph):

Visitor Call	Node Stack	Constructed Graph
visit(A)		n/a
visit(B)		n/a
visit(C)		n/a
endVisit(C)
visit(D)
visit(E)
endVisit(E)
visit(F)
endVisit(F)
endVisit(D)
endVisit(B)
endVisit(A)