Using Apex Describe to Find Object Paths

describe.page

<apex:page controller="DescribeController" standardStylesheets="false" showHeader="false" readOnly="true">
<apex:includeScript value="//ajax.googleapis.com/ajax/libs/jquery/1.3.2/jquery.min.js"/>
<apex:includeScript value="{!URLFOR($Resource.springy, 'springy.js')}"/>
<apex:includeScript value="{!URLFOR($Resource.springy, 'springyui.js')}"/>

<script>
var graph;
</script>
<apex:outputPanel id="graphJs">
<apex:outputPanel rendered="{!json != null}">
<script>
    graph = new Springy.Graph();
    
    console.log('{!json}');
    graph.loadJSON({!json});
    
    var layout = new Springy.Graph();
    jQuery('#container').empty();
    jQuery('#container').append('<canvas id="objectGraph" width="800" height="600"></canvas>');
    var springy = window.springy = jQuery('#objectGraph').springy({
        graph: graph
    });

</script>
</apex:outputPanel>
</apex:outputPanel>

<apex:form >
    Source:<br/>
    <apex:selectList value="{!sourceNodeStr}" multiselect="false" size="1" label="Source">
        <apex:selectOptions value="{!nodeOptions}"/>
    </apex:selectList><br/>
    Destination:<br/>
    <apex:selectList value="{!destNodeStr}" multiselect="false" size="1" label="Destination">
        <apex:selectOptions value="{!nodeOptions}"/>
    </apex:selectList><br/>

    <apex:commandButton action="{!generatePaths}" reRender="paths,graphJs" value="Get Paths"/>

</apex:form>
<apex:outputPanel id="paths">
    <apex:pageMessages />
    <ol>
        <apex:repeat value="{!paths}" var="path">
            <li>
                ({!path.length})
                <apex:repeat value="{!path.nodes}" var="node">
                    {!node.value}&nbsp;
                </apex:repeat>
            </li>
        </apex:repeat>
    </ol>
</apex:outputPanel>
<div id="container"></div>
</apex:page>

DescribeController.cls

public with sharing class DescribeController {

    public Graph theGraph { get; set; }
    public List<SelectOption> nodeOptions { get; set; }
    
    public String sourceNodeStr { get; set; }
    public String destNodeStr { get; set; }
    
    public transient List<GraphPath> paths { get; set; }
    public transient String json { get; set; }
    
    public DescribeController() {
        paths = new List<GraphPath>();
        buildGraph();
        buildSelectOptions();
    }
    
    private void buildGraph() {
        theGraph = new Graph();
        
        for (Schema.SObjectType objType : Schema.getGlobalDescribe().values()) {
            // Add parent Graph.Node
            Schema.DescribeSObjectResult objDesc = objType.getDescribe();
            Graph.Node parentNode = new Graph.Node(objDesc.getName());
            theGraph.addNode(parentNode);
            
            // Add Graph.Edges from all children to their parent
            for (Schema.ChildRelationship child : objDesc.getChildRelationShips()) {
                Schema.DescribeSObjectResult childDesc = child.getChildSObject().getDescribe();
                
                Graph.Node childNode = new Graph.Node(childDesc.getName());
                theGraph.addEdge(childNode, parentNode);
            }
        }
    }
    
    private void buildSelectOptions() {
        nodeOptions = new List<SelectOption>();
        for (Graph.Node n : theGraph.getNodes()) {
            nodeOptions.add( new SelectOption(n.value, n.value) );
        }
        
        nodeOptions.sort();
    }  
    
    public PageReference generatePaths() {
        GraphSearcher searcher = new GraphSearcher(theGraph);
        paths = searcher.findPaths( new Graph.Node(sourceNodeStr), new Graph.Node(destNodeStr) );
  
        GraphFormatter formatter = new GraphFormatter(theGraph);
        json = formatter.getJson(paths);
        
        return null;
    }
}

Graph.cls

public class Graph {
    private Map<Node, Set<Node>> adjacenyList;
        
    public Graph() {
        adjacenyList = new Map<Node, Set<Node>>();
    }
        
    public void addNode(Node n) {
        if ( !adjacenyList.keySet().contains(n) ) {
            adjacenyList.put( n, new Set<Node>() );
        }
    }
        
    public void addEdge(Node sourceNode, Node destNode) {
        addNode(sourceNode);
        addNode(destNode);
        getAdjacentNodes(sourceNode).add(destNode);
    }
        
    public Set<Node> getAdjacentNodes(Node sourceNode) {
        Set<Node> adjNodes = adjacenyList.get(sourceNode);
        if (adjNodes == null) {
            adjNodes = new Set<Node>();
            adjacenyList.put(sourceNode, adjNodes);
        }
        return adjNodes;
    }
        
    public Set<Node> getNodes() {
        return new Set<Node>(adjacenyList.keySet());
    }   
    
    public class Node {
        // Using String for 'value' for simplicity. Could use
        // Object or Comparable to be more flexible.
        public String value { get; set; }
        
        public Node(String val) {
            value = val;
        }
        
        public Boolean equals(Object o) {
           Node other = (Node) o;
           if (other == null) {
               return false;
           }
           return this.value.equals(other.value);
        }
        
        public Integer hashCode() {
            return value.hashCode();
        }
        
        public Integer compareTo(Object o) {
            Node other = (Node) o;
            if (other == null) {
                return 1;
            }
            return this.value.compareTo(other.value);
        }
    }
    
}

GraphFormatter.cls

public class GraphFormatter {
    private final Graph g;
        
    public GraphFormatter(Graph gr) {
        g = gr;
    }
        
    public String getJson(List<GraphPath> paths) {
        JSONGenerator gen = JSON.createGenerator(false);
        
        gen.writeStartObject();
            
        // Nodes
        Set<Object> nodes = new Set<Object>();
        Set<Object> edges = new Set<Object>();

        for (GraphPath path : paths) {
            for (Integer i = 1; i < path.getLength(); i++) {
                Object sourceVal = path.get(i - 1).value;
                Object destVal = path.get(i).value;
                nodes.add(sourceVal);
                nodes.add(destVal);
                      
                edges.add(new List<Object>{sourceVal, destVal});
            }
        }    
            
        gen.writeObjectField('nodes', nodes);
        gen.writeObjectField('edges', edges);
           
        return gen.getAsString();
    } 
}

GraphPath.cls

public class GraphPath {
    private List<Graph.Node> path { get; set; }
        
    // Need both Set and List since no concept
    // of an Ordered Set (e.g., LinkedSet).
    // Allows constant time inclusion check (i.e., map.get()).
    private Set<Graph.Node> pathSet;
        
    public GraphPath() {
        path = new List<Graph.Node>();
        pathSet = new Set<Graph.Node>();
    }
        
    public GraphPath(GraphPath orig) {
        this();
        for (Graph.Node n : orig.getNodes()) {
            add(n);
        }
    }
        
    public void add(Graph.Node n) {
        path.add(n);
        pathSet.add(n);
    }
        
    public Graph.Node removeLast() {
        Graph.Node n = path.remove(path.size() - 1);
        pathSet.remove(n);
        
        return n;
    }
        
    public Graph.Node remove(Integer pathNum) {
        Graph.Node n = path.remove(pathNum);
        pathSet.remove(n);
        return n;
    }
        
    public Integer getLength() {
        return path.size();
    }
        
    public Boolean contains(Graph.Node n) {
        return pathSet.contains(n);
    }
        
    public Graph.Node get(Integer pathNum) {
        return path.get(pathNum);
    }
        
    public List<Graph.Node> getNodes() {
        return new List<Graph.Node>(path);
    }
}

GraphSearcher.cls

public class GraphSearcher {
    private final Graph g;
        
    private Graph.Node destNode;
    private List<GraphPath> paths;
        
    public GraphSearcher(Graph gr) {
        g = gr;
    }
     
    public List<GraphPath> findPaths(Graph.Node sourceNode, Graph.Node destNode) {
        this.destNode = destNode;
        this.paths = new List<GraphPath>();
          
        GraphPath currentPath = new GraphPath();
            
        search(sourceNode, currentPath);
            
        return paths;
    }
        
    private void search(Graph.Node currentNode, GraphPath currentPath) {
        currentPath.add(currentNode);
        Set<Graph.Node> adjacentNodes = g.getAdjacentNodes(currentNode);
            
        // Check if the adjGraph.Node is the destGraph.Node. 
        // If so, a path has been found
        for (Graph.Node adjNode : adjacentNodes) {
            if (adjNode.equals(destNode)) {
                currentPath.add(adjNode);
                paths.add(new GraphPath(currentPath));
                 
                // remove the destGraph.Node in case there is another
                // way to get to the destGraph.Node
                currentPath.removeLast();
                    
                break;
            } 
        }
            
        // Search the unvisited adjacent Graph.Nodes
        for (Graph.Node adjNode : adjacentNodes) {
            if (!currentPath.contains(adjNode) && !adjNode.equals(destNode)) {
                search(adjNode, currentPath);
                currentPath.removeLast();
            }
        }
            
    }
}

This code is from my blog article Using Apex Describe to Find Object Paths.