graph_to_tree.H File Reference

Convert spanning tree graphs to Tree_Node structures. More...

#include <tpl_tree_node.H>
#include <tpl_graph.H>
#include <tpl_graph_utils.H>
#include <ah-errors.H>

Include dependency graph for graph_to_tree.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Graph_To_Tree_Node< GT, Key, Convert, SA >
	Functor class to convert a tree graph to Tree_Node structure. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<class GT , typename Key , class Convert >
static Tree_Node< Key > *	Aleph::graph_to_tree_node (GT &g, typename GT::Node *groot)
template<class GT , typename Key , class Convert >
static void	Aleph::__graph_to_tree_node (GT &g, typename GT::Node *groot, Tree_Node< Key > *troot)
template<class GT , typename Key , typename Convert , class SA >
static void	Aleph::__graph_to_tree_node (GT &g, typename GT::Node *groot, Tree_Node< Key > *troot)
template<class GT , typename Key , class Convert , class SA = Dft_Show_Arc<GT>>
Tree_Node< Key > *	Aleph::graph_to_tree_node (GT &g, typename GT::Node *groot)
	Convert a tree graph to a Tree_Node structure.

Detailed Description

Convert spanning tree graphs to Tree_Node structures.

This file provides utilities for converting spanning trees represented as adjacency-list graphs into Tree_Node<Key> structures, enabling the use of tree-specific algorithms and visualization tools.

Purpose

While spanning trees can be represented using graph structures like List_Graph, the Tree_Node representation offers advantages for:

• Tree drawing and visualization (e.g., with ntreepic)
• Tree-specific traversal algorithms
• Simpler recursive tree operations

Key Limitations

Tree_Node<Key> is less versatile than graph representations:

• No storage for arc/edge data (only node data)
• Key type may differ from the graph's node type
• Requires a Convert class to map graph nodes to tree keys

Example: Converting graph to DFS tree

using GT = List_Graph<Graph_Node<string>, Graph_Arc<int>>;
GT g;
 
auto a = g.insert_node("A");
auto b = g.insert_node("B");
auto c = g.insert_node("C");
g.insert_arc(a, b);
g.insert_arc(a, c);
 
// Define converter from graph node to tree node
struct CopyInfo {
  void operator()(GT::Node* gnode, Tree_Node<string>* tnode) {
    tnode->get_key() = gnode->get_info();
  }
};
 
Tree_Node<string> tree_root;
DynMapTree<GT::Node*, Tree_Node<string>*> node_map;
 
build_tree_dfs<GT, Tree_Node<string>, CopyInfo>(g, a, tree_root, node_map);
// tree_root now contains the DFS spanning tree

Example: BFS tree with node mapping

build_tree_bfs<GT, Tree_Node<string>, CopyInfo>(g, a, tree_root, node_map);
 
// Use mapping to find tree node from graph node
auto tree_node = node_map[b];  // Get tree node for graph node b

See also

Tree_Node For the target tree structure

generate_tree.H For tree visualization

tpl_spanning_tree.H For spanning tree algorithms

Author

Leandro Rabindranath León

Definition in file graph_to_tree.H.