Aleph::Build_Subgraph< GT, SA > Class Template Reference

Build a mapped subgraph from a graph starting at a given node. More...

#include <tpl_components.H>

Collaboration diagram for Aleph::Build_Subgraph< GT, SA >:

Public Member Functions
	Build_Subgraph (SA arc_filter=SA())
	Construct a subgraph builder with optional arc filter.
void	operator() (const GT &g, GT &sg, typename GT::Node *g_src)
	Build a mapped subgraph starting from a specific node.
GT	operator() (const GT &g, typename GT::Node *src)
	Build and return a subgraph containing all nodes reachable from src.
void	operator() (const GT &g, DynList< typename GT::Node * > &list, typename GT::Node *src)
	Build a list of all nodes reachable from a source node.

Private Member Functions
void	build_subgraph (GT &sg, typename GT::Node *g_src)
template<template< class > class List>
void	build_subgraph (List< typename GT::Node * > &l, typename GT::Node *p)

Private Attributes
SA	sa
const GT *	gptr = nullptr
size_t	count = 0

Detailed Description

template<class GT, class SA = Dft_Show_Arc<GT>>
class Aleph::Build_Subgraph< GT, SA >

Build a mapped subgraph from a graph starting at a given node.

This class performs a depth-first traversal of graph g starting from a source node and constructs a mapped copy of all reachable nodes and arcs (the entire graph if connected, or a connected component if not).

The resulting subgraph maintains bidirectional mappings via cookies between the original graph elements and their copies in the subgraph.

Algorithm:

1. Start from source node and mark it as visited
2. Create a copy of the node in the subgraph and establish mapping
3. For each unvisited adjacent arc, copy it and recurse on target node
4. Continue until all reachable nodes are visited

Complexity:

• Time: O(V + E) where V is vertices and E is edges in the component
• Space: O(V) for recursion stack + O(V + E) for output subgraph

Usage example:

List_Graph<Graph_Node<int>, Graph_Arc<int>> g;
// ... populate graph ...
 
List_Graph<Graph_Node<int>, Graph_Arc<int>> subgraph;
Build_Subgraph<decltype(g)> builder;
builder(g, subgraph, g.get_first_node());

Note

Uses the Build_Subtree control bit on nodes and arcs.

Template Parameters

GT	Graph type (must satisfy Aleph graph concept).
SA	Arc filter type (default: Dft_Show_Arc<GT>).

See also

Inconnected_Components For computing all connected components

copy_graph() For copying an entire graph

Definition at line 102 of file tpl_components.H.

Constructor & Destructor Documentation

Build_Subgraph()

template<class GT , class SA = Dft_Show_Arc<GT>>

Aleph::Build_Subgraph< GT, SA >::Build_Subgraph ( SA  arc_filter = SA() )

inline

Construct a subgraph builder with optional arc filter.

Parameters

arc_filter

Arc filter to control which arcs are traversed (default: show all arcs).

Definition at line 115 of file tpl_components.H.

Member Function Documentation

build_subgraph() [1/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Build_Subgraph< GT, SA >::build_subgraph ( GT &  sg, typename GT::Node *  g_src  )

inlineprivate

Definition at line 121 of file tpl_components.H.

References ARC_BITS, Aleph::Build_Subgraph< GT, SA >::build_subgraph(), Aleph::Build_Subtree, Aleph::Build_Subgraph< GT, SA >::count, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IS_ARC_VISITED, IS_NODE_VISITED, GraphCommon< GT, Node, Arc >::map_arcs(), GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_BITS, and Aleph::Build_Subgraph< GT, SA >::sa.

Referenced by Aleph::Build_Subgraph< GT, SA >::build_subgraph(), Aleph::Build_Subgraph< GT, SA >::build_subgraph(), Aleph::Build_Subgraph< GT, SA >::operator()(), and Aleph::Build_Subgraph< GT, SA >::operator()().

build_subgraph() [2/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

template<template< class > class List>

void Aleph::Build_Subgraph< GT, SA >::build_subgraph ( List< typename GT::Node * > &  l, typename GT::Node *  p  )

inlineprivate

Definition at line 168 of file tpl_components.H.

References Aleph::DynList< T >::append(), ARC_BITS, Aleph::Build_Subgraph< GT, SA >::build_subgraph(), Aleph::Build_Subtree, Aleph::Build_Subgraph< GT, SA >::count, GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Build_Subgraph< GT, SA >::gptr, IS_ARC_VISITED, IS_NODE_VISITED, l, Aleph::maps(), NODE_BITS, and Aleph::Build_Subgraph< GT, SA >::sa.

operator()() [1/3]

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Build_Subgraph< GT, SA >::operator() ( const GT &  g, DynList< typename GT::Node * > &  list, typename GT::Node *  src  )

inline

Build a list of all nodes reachable from a source node.

Performs DFS from src and collects all reachable nodes into list.

Parameters

[in]	g	Source graph to traverse.
[out]	list	Output list to store reachable node pointers.
[in]	src	Starting node for the traversal.

Exceptions

std::bad_alloc	If memory allocation fails.
std::invalid_argument	If src is nullptr.

Note

Uses the Build_Subtree control bit on nodes and arcs.

Definition at line 254 of file tpl_components.H.

References ah_invalid_argument_if, Aleph::Build_Subgraph< GT, SA >::count, Aleph::Build_Subgraph< GT, SA >::gptr, and Aleph::maps().

operator()() [2/3]

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Build_Subgraph< GT, SA >::operator() ( const GT &  g, GT &  sg, typename GT::Node *  g_src  )

inline

Build a mapped subgraph starting from a specific node.

Performs a DFS traversal from g_src and constructs a mapped copy of all reachable nodes and arcs in sg.

Parameters

[in]	g	Source graph to traverse.
[out]	sg	Output subgraph (should be empty; will contain mapped copy).
[in]	g_src	Starting node for the traversal.

Exceptions

std::bad_alloc	If memory allocation fails.
std::invalid_argument	If g_src is nullptr.

Note

Uses the Build_Subtree control bit on nodes and arcs.

After execution, nodes/arcs in sg are mapped to g via cookies.

Definition at line 209 of file tpl_components.H.

References ah_invalid_argument_if, Aleph::Build_Subgraph< GT, SA >::build_subgraph(), Aleph::Build_Subgraph< GT, SA >::count, Aleph::Build_Subgraph< GT, SA >::gptr, and Aleph::maps().

operator()() [3/3]

template<class GT , class SA = Dft_Show_Arc<GT>>

GT Aleph::Build_Subgraph< GT, SA >::operator() ( const GT &  g, typename GT::Node *  src  )

inline

Build and return a subgraph containing all nodes reachable from src.

Parameters

[in]	g	Source graph to traverse.
[in]	src	Starting node for the traversal.

Returns

A new graph containing mapped copies of all reachable nodes/arcs.

Exceptions

std::bad_alloc	If memory allocation fails.
std::invalid_argument	If src is nullptr.

Definition at line 229 of file tpl_components.H.

References ah_invalid_argument_if, Aleph::Build_Subgraph< GT, SA >::build_subgraph(), Aleph::Build_Subgraph< GT, SA >::count, and Aleph::Build_Subgraph< GT, SA >::gptr.

Member Data Documentation

count

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Build_Subgraph< GT, SA >::count = 0

private

Definition at line 106 of file tpl_components.H.

Referenced by Aleph::Build_Subgraph< GT, SA >::build_subgraph(), Aleph::Build_Subgraph< GT, SA >::build_subgraph(), Aleph::Build_Subgraph< GT, SA >::operator()(), Aleph::Build_Subgraph< GT, SA >::operator()(), and Aleph::Build_Subgraph< GT, SA >::operator()().

gptr

template<class GT , class SA = Dft_Show_Arc<GT>>

const GT* Aleph::Build_Subgraph< GT, SA >::gptr = nullptr

private

Definition at line 105 of file tpl_components.H.

Referenced by Aleph::Build_Subgraph< GT, SA >::build_subgraph(), Aleph::Build_Subgraph< GT, SA >::operator()(), Aleph::Build_Subgraph< GT, SA >::operator()(), and Aleph::Build_Subgraph< GT, SA >::operator()().

sa

template<class GT , class SA = Dft_Show_Arc<GT>>

SA Aleph::Build_Subgraph< GT, SA >::sa

private

Definition at line 104 of file tpl_components.H.

Referenced by Aleph::Build_Subgraph< GT, SA >::build_subgraph(), and Aleph::Build_Subgraph< GT, SA >::build_subgraph().

---

The documentation for this class was generated from the following file:

• tpl_components.H