Trees

A tree is an acyclic graph where any two nodes are connected by a single path.

yFiles for HTML provides several ways to check tree characteristics, to query the tree structure, and to help with finding tree edges in a graph.

Tree Characteristics

The GraphStructureAnalyzer provides several methods to check for tree characteristics.

isTree

Determines whether the graph is an undirected or directed tree. A directed tree is a tree with one Root node where all edges are directed from the Root to the Leaves.

isForest

Determines whether the graph is a forest. A forest is a graph where each of its components is a tree.

isNaryTree(number)

Determines whether the graph is a directed rooted tree where each node has a maximum of n children.

Querying Tree Structures

The TreeAnalysis algorithm analyzes a tree graph and its result provides access to important tree structure characteristics.

The algorithm supports directed, rooted trees as well as undirected trees. For undirected trees, the algorithm computes the edges which need to be reversed in order to make it a directed tree (see property reversedEdges). This means that the result always yields a directed view of the structure when rooted at the node stored in root.

The analysis run returns a result of type TreeAnalysisResult which gives access to the following properties:

root

The root node of the tree is the single node that has no incoming edges. It equals the customRootNode if one is specified.

directedRootedTree

Indicates whether the input is a directed rooted tree. If not, the algorithm reverses some edges to view the structure as a directed tree (it does not reverse edges on the original graph!).

reversedEdges

The edges that must be reversed to make the input graph a directed, rooted tree structure. This collection is empty if the input is already such a structure.

leafNodes

All leaf nodes in the tree, which are nodes without outgoing edges (i.e., without children).

getChildren(node: INode): ResultItemCollection<INode>

Gets the child nodes of the given node in the tree.

getParent(node: INode): INode

Gets the parent of the given node in the tree.

getSubtree(subtreeRoot: INode): Subtree

Gets all nodes and edges of the subtree that has the given node as its root.

getDescendants(root: INode): Subtree

Gets all nodes and edges of the subtree that has the given node as root, excluding the given node itself and its outgoing edges.

getDepth(node: INode): number

Gets the depth of the node, which is the length of the path between the root and the node.

getNearestCommonAncestor(nodes: IEnumerable<INode>): INode

Determines the nearest common ancestor for the given nodes.

Querying the tree depicted in A simple tree for its root node would lead to node ROOT, and the list of all leaf nodes would be {a, f, i, j, k}.

Running tree analysis and finding the common ancestor of a set of nodes shows the code to run the tree analysis algorithm to query the root node, leaf nodes, and to find the common ancestor of nodes {f, j, k} in A simple tree. The common ancestor query in this example results in node c.

// analyze the tree using TreeAnalysis
const analysisResult = new TreeAnalysis().run(graph)
// query the root node of the tree
const rootNode = analysisResult.root
// query the leaf nodes
const leafNodes = analysisResult.leafNodes
// find the nearest common ancestor for the given nodes.
const nodeC = analysisResult.getNearestCommonAncestor(nodeF, nodeJ, nodeK)

Finding trees

Often, it is useful to find tree structures within a graph.

A spanning tree of a connected graph is the smallest set of edges that connects all nodes in the graph. Finding these, and therefore finding the minimum spanning tree of a graph, is the purpose of the SpanningTree class.

Consider Finding the minimum spanning tree. The numbers on the edges represent costs associated with each edge. The smallest set of edges that connects all nodes in the graph, while also minimizing the total cost, is shown by the emphasized edges. These edges define the minimum spanning tree of the graph, with an overall cost of 17 units.

The SpanningTree class considers costs and provides the total costs in its result.

Running the Spanning Tree algorithm shows the code to prepare and run the Spanning Tree algorithm on the graph shown in Finding the minimum spanning tree.

// configure and run the spanning tree algorithm
const spanningTreeResult = new SpanningTree({
  costs: (edge) => getEdgeCost(edge)
}).run(graph)

// Get the tree edges and the overall costs of the minimum spanning tree.
const spanningTreeEdges = spanningTreeResult.edges
const totalCost = spanningTreeResult.totalCost

A superset of directed trees are directed acyclic graphs (DAG). When a directed graph with cycles is given and must be converted to an acyclic graph, this is known as the Feedback Edge Set problem. Each feedback edge in a directed rooted graph is part of a cycle, and each cycle contains feedback edges. Therefore, finding the set of feedback edges and removing or reverting them removes all cycles and results in a DAG.

As with calculating the minimum spanning tree, the edges may be weighted by costs that will be minimized for the calculated FeedbackEdgeSet.

Running the Feedback Edge Set algorithm shows the code to prepare and run a Feedback Edge Set search and reverse the feedback edges.

// configure and run the feedback edge set algorithm
const feedbackEdgeSetResult = new FeedbackEdgeSet({
  costs: (edge) => getEdgeCost(edge)
}).run(graph)

// Reverse all feedback edges to get a directed acyclic graph
feedbackEdgeSetResult.feedbackEdgeSet.forEach((edge) => graph.reverse(edge))

Example: Create a Directed Tree

To see several tree algorithms working together, we convert a general graph into a directed tree.

In Reduce Graph the graph is reduced to a simple graph without self-loops and multi-edges.

const analyzer = new GraphStructureAnalyzer(graph)
if (!analyzer.isSimple()) {
  // remove selfloops and/or multiple edges between nodes
  const edgesToRemove = new List()
  const neighbors = new Set()
  for (const node of graph.nodes) {
    for (const edge of graph.edgesAt(node)) {
      if (edge.isSelfLoop && !edgesToRemove.includes(edge)) {
        edgesToRemove.add(edge)
      } else {
        const neighbor = edge.opposite(node)
        if (neighbors.has(neighbor)) {
          // there was already an edge to this neighbor
          edgesToRemove.add(edge)
        } else {
          neighbors.add(neighbor)
        }
      }
    }
    for (const edge of edgesToRemove) {
      graph.remove(edge)
    }
    edgesToRemove.clear()
    neighbors.clear()
  }
}
const analyzer = new GraphStructureAnalyzer(graph)
if (!analyzer.isSimple()) {
  // remove selfloops and/or multiple edges between nodes
  const edgesToRemove = new List<IEdge>()
  const neighbors = new Set<IPortOwner>()
  for (const node of graph.nodes) {
    for (const edge of graph.edgesAt(node)) {
      if (edge.isSelfLoop && !edgesToRemove.includes(edge)) {
        edgesToRemove.add(edge)
      } else {
        const neighbor = edge.opposite(node)
        if (neighbors.has(neighbor)) {
          // there was already an edge to this neighbor
          edgesToRemove.add(edge)
        } else {
          neighbors.add(neighbor)
        }
      }
    }
    for (const edge of edgesToRemove) {
      graph.remove(edge)
    }
    edgesToRemove.clear()
    neighbors.clear()
  }
}

In Extend to a Connected Graph, unconnected components are connected by adding edges.

if (!analyzer.isConnected()) {
  const connectedComponentsResult = new ConnectedComponents().run(graph)
  let sourceNode = null
  connectedComponentsResult.components.forEach((component) => {
    const representative = component.nodes.get(0)
    if (sourceNode === null) {
      sourceNode = representative
    } else {
      graph.createEdge(sourceNode, representative)
    }
  })
}
if (!analyzer.isConnected()) {
  const connectedComponentsResult = new ConnectedComponents().run(graph)
  let sourceNode: INode | null = null
  connectedComponentsResult.components.forEach((component) => {
    const representative = component.nodes.get(0)
    if (sourceNode === null) {
      sourceNode = representative
    } else {
      graph.createEdge(sourceNode, representative)
    }
  })
}

In Create Spanning Tree, the connected graph is reduced to a spanning tree by removing non-tree edges.

if (!analyzer.isTree(false)) {
  const spanningTreeResult = new SpanningTree().run(graph)
  // remove all edges that are not part of the spanning tree
  const edges = graph.edges.toList()
  for (const edge of edges) {
    if (!spanningTreeResult.edges.contains(edge)) {
      graph.remove(edge)
    }
  }
}

In Create Directed Rooted Tree, a root node is chosen. Then, any edges that do not point away from the root toward the leaves are reversed, using the TreeAnalysis class.

if (!analyzer.isTree(true)) {
  // nominate one node as root and run the analysis
  const root = graph.nodes.first()
  const result = new TreeAnalysis({
    customRootNode: root
  }).run(graph)
  // reverse edges that the analysis found need reversal in order to get a directed tree
  result.reversedEdges.forEach((edge) => graph.reverse(edge))
}
if (!analyzer.isTree(true)) {
  // nominate one node as root and run the analysis
  const root = graph.nodes.first()!
  const result = new TreeAnalysis({
    customRootNode: root
  }).run(graph)
  // reverse edges that the analysis found need reversal in order to get a directed tree
  result.reversedEdges.forEach((edge) => graph.reverse(edge))
}