treegraph

TreeGraph is a hybrid data structure designed to model data that is primarily hierarchical but benefits from non-hierarchical relationships. Conceptually, it consists of a rooted tree that encodes the main parent-child relationships, with an additional set of edges that connect nodes outside the strict tree structure. In a directed TreeGraph, tree edges point from parent to child, while the extra edges may be directed or undirected depending on the implementation. Each node belongs to exactly one path from the root via tree edges, ensuring a unique ancestry for the tree portion; the extra edges can introduce cross-links without altering the fundamental tree property.

Structure and representation typically involve a node with a payload, a list of tree-children for the hierarchical portion, and a separate collection of non-tree edges for the auxiliary connections. The root is the node without a tree parent. Implementations may store data as adjacency lists or maps, distinguishing tree edges from cross-edges to support different traversal strategies and queries.

Operations commonly include adding and removing nodes, attaching a node as a tree child, and adding or removing non-tree (cross) edges. Traversal supports both tree-focused routines, such as depth-first search restricted to tree edges, and broader graph traversals that consider both edge types. Queries can compute the path from the root to a node via the tree or seek shortest paths using the combined set of edges, with performance depending on the total number of nodes and edges.

Applications for TreeGraph include modeling organizational structures augmented with cross-functional links, taxonomies with synonyms or related terms, and datasets where hierarchical classification coexists with associative relationships. It serves as a flexible alternative when a pure tree or a generic graph is insufficient, while retaining the primary hierarchical semantics.