Trees

A tree is an acyclic graph, in which any pair of nodes is connected through a path.

yFiles for HTML provides several ways to check the tree characteristics, querying the tree structure and help 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 either undirected or directed tree where 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, i.e. 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 tree which is the single node that has no incoming edges. Equals the customRootNode if there is one specified.
directedRootedTree: Whether the input is a directed rooted tree. If not, then the algorithm needed to reverse some edges in order to view the structure as directed tree (does not reverse edges on the original graph!).
reversedEdges: The edges that would need to be reversed in order to make the input graph a directed, rooted tree structure. This collection is empty, if the input already is such a structure.
leafNodes: Gets 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 root.
getDescendants(root: INode): Subtree: Gets all nodes and edges of the subtree that has the given node as root but not the given node itself and its outgoing edges.
getDepth(node: INode): number: Gets the depth of the node, that 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, e.g., 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 would result in node c.

Running tree analysis and finding the common ancestor of a set of nodes

// 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 of interest to find tree structures in a graph.

A spanning tree of a connected graph is the smallest set of edges such that all nodes of the graph are connected. Finding these and therefore finding the minimum spanning tree of a graph is the duty of class SpanningTree.

Consider Finding the minimum spanning tree, for instance. The numbers at the edges denote costs that are associated with an edge. The smallest set of edges such that all nodes from the graph are connected, and the accumulated costs of the set is at a minimum results in the emphasized edges. These edges define the minimum spanning tree of the graph with an overall cost of 17 [units].

analysis span 1sel — Finding the minimum spanning tree

Class SpanningTree takes costs into account and provides the total costs in its result.

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

Running the Spanning Tree algorithm

// 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). The case that a directed graph with cycles is given and has to be converted to an acyclic graph, is known as Feedback Edge Set problem as 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 for calculating the minimum spanning tree the edges may be weighted by costs that shall 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.

Running the Feedback Edge Set algorithm

// 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: Make Directed Tree

To see several tree algorithms in combination we convert a general graph to a directed tree.

In Make graph a simple graph the graph is reduced to a simple graph which contains no self-loops and multi-edges.

Make graph a simple graph

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 Make a simple graph connected unconnected components get connected by adding necessary edges.

Make a simple graph connected

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 Make a connected graph a tree the connected graph is reduced to its spanning tree by removing all non-tree edges.

Make a connected graph a tree

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 Make the tree a directed rooted tree a root node is chosen and all edges not pointing from this root to the leaves are reversed by using class TreeAnalysis.

Make the tree a directed rooted tree

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))
}

Paths Network Flows