Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Private Member Functions | Private Attributes | List of all members
Aleph::GraphCopyWithMapping< GT, Tree > Class Template Reference
Graphs

Graph copy with explicit node mapping. More...

#include <tpl_graph.H>

Inheritance diagram for Aleph::GraphCopyWithMapping< GT, Tree >:
[legend]
Collaboration diagram for Aleph::GraphCopyWithMapping< GT, Tree >:
[legend]

Public Types

using Node = typename GT::Node
 
using Arc = typename GT::Arc
 
using Node_Type = typename GT::Node_Type
 
using Arc_Type = typename GT::Arc_Type
 

Public Member Functions

 GraphCopyWithMapping (const GT &src)
 Construct a copy of the given graph with node mapping.
 
 GraphCopyWithMapping ()=default
 Default constructor.
 
 GraphCopyWithMapping (GraphCopyWithMapping &&other) noexcept=default
 Move constructor.
 
GraphCopyWithMapping & operator= (GraphCopyWithMapping &&other) noexcept=default
 Move assignment operator.
 
 GraphCopyWithMapping (const GraphCopyWithMapping &)=delete
 
GraphCopyWithMapping & operator= (const GraphCopyWithMapping &)=delete
 
GT & get_graph () noexcept
 Get the copied graph.
 
const GT & get_graph () const noexcept
 Get the copied graph (const version).
 
Node * get_copy (Node *orig) const
 Get the copy of an original node.
 
Node * search_copy (Node *orig) const noexcept
 Search for the copy of an original node (no exception).
 
bool has_copy (Node *orig) const noexcept
 Check if an original node is in the mapping.
 
size_t num_nodes () const noexcept
 Get the number of mapped nodes.
 
size_t num_arcs () const noexcept
 Get the number of arcs in the copied graph.
 
template<typename Op >
void for_each_mapping (Op op) const
 Apply a function to each (original, copy) node pair.
 
Node * insert_unmapped_node (const Node_Type &info=Node_Type())
 Insert a new node into the copied graph (not mapped).
 
Node * insert_unmapped_node (Node_Type &&info)
 Insert a new node into the copied graph (not mapped, move version).
 
void remove_node (Node *node)
 Remove a node from the copied graph.
 
Arc * insert_arc (Node *src, Node *tgt, const Arc_Type &info=Arc_Type())
 Insert an arc into the copied graph.
 
void remove_arc (Arc *arc)
 Remove an arc from the copied graph.
 
void clear ()
 Clear the copied graph and mapping.
 

Private Member Functions

void build_copy (const GT &src)
 Build the copy and mapping.
 

Private Attributes

GT copied_graph
 
DynMapTree< Node *, Node *, Tree > node_map
 

Detailed Description

template<class GT, template< class, class > class Tree = Treap>
class Aleph::GraphCopyWithMapping< GT, Tree >

Graph copy with explicit node mapping.

This class creates a copy of a graph and maintains an explicit mapping from original nodes to their copies using a DynMapTree (not cookies).

This is essential for algorithms like Johnson's that need to:

  1. Copy a graph
  2. Run algorithms that use cookies on the copy (Bellman-Ford, Dijkstra)
  3. Still be able to translate between original and copy nodes

The mapping is unidirectional: original → copy.

Template Parameters
GTGraph type (List_Graph, List_Digraph, etc.)
TreeBinary search tree type for the mapping (default Treap)
Example
List_Digraph<Node, Arc> original;
// ... build graph ...
GraphCopyWithMapping<List_Digraph<Node, Arc>> copy(original);
// Get copied node from original
auto* orig_node = original.get_first_node();
auto* copy_node = copy.get_copy(orig_node);
// Access the copied graph
auto& copied_graph = copy.get_graph();
Aleph::Digraph
Generic directed graph (digraph) wrapper template.
Definition graph-dry.H:3848
Aleph::GraphCopyWithMapping
Graph copy with explicit node mapping.
Definition tpl_graph.H:3881
Aleph::copy
Itor2 copy(Itor1 sourceBeg, const Itor1 &sourceEnd, Itor2 destBeg)
Copy elements from one range to another.
Definition ahAlgo.H:584
Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693
See also
copy_graph map_nodes Johnson

Definition at line 3880 of file tpl_graph.H.

Member Typedef Documentation

◆ Arc

template<class GT , template< class, class > class Tree = Treap>
using Aleph::GraphCopyWithMapping< GT, Tree >::Arc = typename GT::Arc

Definition at line 3884 of file tpl_graph.H.

◆ Arc_Type

template<class GT , template< class, class > class Tree = Treap>
using Aleph::GraphCopyWithMapping< GT, Tree >::Arc_Type = typename GT::Arc_Type

Definition at line 3886 of file tpl_graph.H.

◆ Node

template<class GT , template< class, class > class Tree = Treap>
using Aleph::GraphCopyWithMapping< GT, Tree >::Node = typename GT::Node

Definition at line 3883 of file tpl_graph.H.

◆ Node_Type

template<class GT , template< class, class > class Tree = Treap>
using Aleph::GraphCopyWithMapping< GT, Tree >::Node_Type = typename GT::Node_Type

Definition at line 3885 of file tpl_graph.H.

Constructor & Destructor Documentation

◆ GraphCopyWithMapping() [1/4]

template<class GT , template< class, class > class Tree = Treap>
Aleph::GraphCopyWithMapping< GT, Tree >::GraphCopyWithMapping ( const GT &  src)
inlineexplicit

Construct a copy of the given graph with node mapping.

Creates a deep copy of the source graph and builds a mapping from source nodes to their corresponding copies.

Parameters
[in]srcThe source graph to copy.
Exceptions
std::bad_allocif there is not enough memory.
Note
Complexity: O(V log V + E) due to map insertions.
Exception safety: Strong guarantee.

Definition at line 3928 of file tpl_graph.H.

References Aleph::GraphCopyWithMapping< GT, Tree >::build_copy().

◆ GraphCopyWithMapping() [2/4]

template<class GT , template< class, class > class Tree = Treap>
Aleph::GraphCopyWithMapping< GT, Tree >::GraphCopyWithMapping ( )
default

Default constructor.

Creates an empty graph and an empty mapping.

Exceptions
none
Note
Complexity: O(1)
Exception safety: noexcept

◆ GraphCopyWithMapping() [3/4]

template<class GT , template< class, class > class Tree = Treap>
Aleph::GraphCopyWithMapping< GT, Tree >::GraphCopyWithMapping ( GraphCopyWithMapping< GT, Tree > &&  other)
defaultnoexcept

Move constructor.

Transfers ownership of the graph and mapping from another instance.

Parameters
[in,out]otherThe instance to move from.
Exceptions
none
Postcondition
other is left in the default-constructed state (empty graph and mapping).
Note
Complexity: O(1)
Exception safety: noexcept

◆ GraphCopyWithMapping() [4/4]

template<class GT , template< class, class > class Tree = Treap>
Aleph::GraphCopyWithMapping< GT, Tree >::GraphCopyWithMapping ( const GraphCopyWithMapping< GT, Tree > &  )
delete

Member Function Documentation

◆ build_copy()

template<class GT , template< class, class > class Tree = Treap>
void Aleph::GraphCopyWithMapping< GT, Tree >::build_copy ( const GT &  src)
inlineprivate

Build the copy and mapping.

Definition at line 3893 of file tpl_graph.H.

References Aleph::GraphCopyWithMapping< GT, Tree >::copied_graph, GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Dlink::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), and Aleph::GraphCopyWithMapping< GT, Tree >::node_map.

Referenced by Aleph::GraphCopyWithMapping< GT, Tree >::GraphCopyWithMapping().

◆ clear()

template<class GT , template< class, class > class Tree = Treap>
void Aleph::GraphCopyWithMapping< GT, Tree >::clear ( )
inline

Clear the copied graph and mapping.

Removes all nodes and arcs from the copied graph and clears the mapping.

Exceptions
none
Note
Complexity: O(V + E)
Exception safety: noexcept.

Definition at line 4175 of file tpl_graph.H.

References Aleph::clear_graph(), Aleph::GraphCopyWithMapping< GT, Tree >::copied_graph, and Aleph::GraphCopyWithMapping< GT, Tree >::node_map.

◆ for_each_mapping()

template<class GT , template< class, class > class Tree = Treap>
template<typename Op >
void Aleph::GraphCopyWithMapping< GT, Tree >::for_each_mapping ( Op  op) const
inline

Apply a function to each (original, copy) node pair.

Iterates over all mappings and applies the given function.

Template Parameters
OpFunction type taking (Node* original, Node* copy).
Parameters
[in]opFunction to apply.
Exceptions
whateverop throws.
Note
Complexity: O(V)
Exception safety: Basic guarantee (depends on op).

Definition at line 4070 of file tpl_graph.H.

References Aleph::GraphCopyWithMapping< GT, Tree >::node_map.

◆ get_copy()

template<class GT , template< class, class > class Tree = Treap>
Node * Aleph::GraphCopyWithMapping< GT, Tree >::get_copy ( Node *  orig) const
inline

Get the copy of an original node.

Retrieves the node in the copied graph that corresponds to the given node in the original graph.

Parameters
[in]origPointer to the original node.
Returns
Pointer to the corresponding node in the copy.
Exceptions
std::domain_errorif the node is not in the mapping.
Note
Complexity: O(log V)
Exception safety: Strong guarantee.

Definition at line 4003 of file tpl_graph.H.

References ah_domain_error_if, Aleph::maps(), and Aleph::GraphCopyWithMapping< GT, Tree >::node_map.

◆ get_graph() [1/2]

template<class GT , template< class, class > class Tree = Treap>
const GT & Aleph::GraphCopyWithMapping< GT, Tree >::get_graph ( ) const
inlinenoexcept

Get the copied graph (const version).

Returns
Const reference to the copied graph.
Exceptions
none
Note
Complexity: O(1)
Exception safety: noexcept

Definition at line 3990 of file tpl_graph.H.

References Aleph::GraphCopyWithMapping< GT, Tree >::copied_graph.

◆ get_graph() [2/2]

template<class GT , template< class, class > class Tree = Treap>
GT & Aleph::GraphCopyWithMapping< GT, Tree >::get_graph ( )
inlinenoexcept

Get the copied graph.

Returns
Reference to the copied graph.
Exceptions
none
Note
Complexity: O(1)
Exception safety: noexcept

Definition at line 3981 of file tpl_graph.H.

References Aleph::GraphCopyWithMapping< GT, Tree >::copied_graph.

◆ has_copy()

template<class GT , template< class, class > class Tree = Treap>
bool Aleph::GraphCopyWithMapping< GT, Tree >::has_copy ( Node *  orig) const
inlinenoexcept

Check if an original node is in the mapping.

Parameters
[in]origPointer to the original node.
Returns
true if the node is mapped, false otherwise.
Exceptions
none
Note
Complexity: O(log V)
Exception safety: noexcept

Definition at line 4036 of file tpl_graph.H.

References Aleph::maps(), and Aleph::GraphCopyWithMapping< GT, Tree >::node_map.

◆ insert_arc()

template<class GT , template< class, class > class Tree = Treap>
Arc * Aleph::GraphCopyWithMapping< GT, Tree >::insert_arc ( Node *  src,
Node *  tgt,
const Arc_Type &  info = Arc_Type() 
)
inline

Insert an arc into the copied graph.

Parameters
[in]srcSource node (in the copy).
[in]tgtTarget node (in the copy).
[in]infoArc information.
Returns
Pointer to the new arc.
Exceptions
std::bad_allocif memory allocation fails.
Note
Complexity: O(1)
Exception safety: Strong guarantee.

Definition at line 4150 of file tpl_graph.H.

References Aleph::GraphCopyWithMapping< GT, Tree >::copied_graph, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), and Aleph::maps().

◆ insert_unmapped_node() [1/2]

template<class GT , template< class, class > class Tree = Treap>
Node * Aleph::GraphCopyWithMapping< GT, Tree >::insert_unmapped_node ( const Node_Type &  info = Node_Type())
inline

Insert a new node into the copied graph (not mapped).

Useful for adding auxiliary nodes (like dummy nodes in Johnson's algorithm) that don't correspond to any original node.

Parameters
[in]infoNode information.
Returns
Pointer to the new node in the copied graph.
Exceptions
std::bad_allocif memory allocation fails.
Note
Complexity: O(1)
Exception safety: Strong guarantee.

Definition at line 4089 of file tpl_graph.H.

References Aleph::GraphCopyWithMapping< GT, Tree >::copied_graph, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

◆ insert_unmapped_node() [2/2]

template<class GT , template< class, class > class Tree = Treap>
Node * Aleph::GraphCopyWithMapping< GT, Tree >::insert_unmapped_node ( Node_Type &&  info)
inline

Insert a new node into the copied graph (not mapped, move version).

Useful for adding auxiliary nodes (like dummy nodes in Johnson's algorithm) that don't correspond to any original node.

Parameters
[in]infoNode information (moved).
Returns
Pointer to the new node in the copied graph.
Exceptions
std::bad_allocif memory allocation fails.
Note
Complexity: O(1)
Exception safety: Strong guarantee.

Definition at line 4105 of file tpl_graph.H.

References Aleph::GraphCopyWithMapping< GT, Tree >::copied_graph, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

◆ num_arcs()

template<class GT , template< class, class > class Tree = Treap>
size_t Aleph::GraphCopyWithMapping< GT, Tree >::num_arcs ( ) const
inlinenoexcept

Get the number of arcs in the copied graph.

Returns
Number of arcs in the copy.
Exceptions
none
Note
Complexity: O(1)
Exception safety: noexcept

Definition at line 4057 of file tpl_graph.H.

References Aleph::GraphCopyWithMapping< GT, Tree >::copied_graph, and GraphCommon< GT, Node, Arc >::get_num_arcs().

◆ num_nodes()

template<class GT , template< class, class > class Tree = Treap>
size_t Aleph::GraphCopyWithMapping< GT, Tree >::num_nodes ( ) const
inlinenoexcept

Get the number of mapped nodes.

Returns
Number of nodes in the mapping.
Exceptions
none
Note
Complexity: O(1)
Exception safety: noexcept

Definition at line 4048 of file tpl_graph.H.

References Aleph::GraphCopyWithMapping< GT, Tree >::node_map, and Aleph::HTList::size().

◆ operator=() [1/2]

template<class GT , template< class, class > class Tree = Treap>
GraphCopyWithMapping & Aleph::GraphCopyWithMapping< GT, Tree >::operator= ( const GraphCopyWithMapping< GT, Tree > &  )
delete

◆ operator=() [2/2]

template<class GT , template< class, class > class Tree = Treap>
GraphCopyWithMapping & Aleph::GraphCopyWithMapping< GT, Tree >::operator= ( GraphCopyWithMapping< GT, Tree > &&  other)
defaultnoexcept

Move assignment operator.

Transfers ownership of the graph and mapping from another instance.

Parameters
[in,out]otherThe instance to move from.
Returns
Reference to this instance.
Exceptions
none
Postcondition
other receives the previous contents of *this (swap semantics). If *this was empty, other becomes empty.
Note
Complexity: O(1)
Exception safety: noexcept

◆ remove_arc()

template<class GT , template< class, class > class Tree = Treap>
void Aleph::GraphCopyWithMapping< GT, Tree >::remove_arc ( Arc *  arc)
inline

Remove an arc from the copied graph.

Parameters
[in]arcPointer to the arc to remove.
Exceptions
none
Note
Complexity: O(1)
Exception safety: noexcept.

Definition at line 4162 of file tpl_graph.H.

References Aleph::GraphCopyWithMapping< GT, Tree >::copied_graph, and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_arc().

◆ remove_node()

template<class GT , template< class, class > class Tree = Treap>
void Aleph::GraphCopyWithMapping< GT, Tree >::remove_node ( Node *  node)
inline

Remove a node from the copied graph.

If the node was mapped, the mapping entry is removed to keep the mapping consistent.

Parameters
[in]nodePointer to the node to remove.
Exceptions
Anyexception thrown by the underlying mapping or graph removal operations.
Note
Complexity: O(degree + V) for List_Graph, O(E + V) for List_Digraph (due to reverse lookup in map).
Exception safety: This function does not add new throwing points beyond those of the underlying containers.

Definition at line 4120 of file tpl_graph.H.

References Aleph::GraphCopyWithMapping< GT, Tree >::copied_graph, FunctionalMethods< Container, T >::for_each(), Aleph::maps(), Aleph::GraphCopyWithMapping< GT, Tree >::node_map, and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node().

◆ search_copy()

template<class GT , template< class, class > class Tree = Treap>
Node * Aleph::GraphCopyWithMapping< GT, Tree >::search_copy ( Node *  orig) const
inlinenoexcept

Search for the copy of an original node (no exception).

Retrieves the node in the copied graph that corresponds to the given node in the original graph, or nullptr if not found.

Parameters
[in]origPointer to the original node.
Returns
Pointer to the corresponding node in the copy, or nullptr if not found.
Exceptions
none
Note
Complexity: O(log V)
Exception safety: noexcept

Definition at line 4022 of file tpl_graph.H.

References Aleph::maps(), and Aleph::GraphCopyWithMapping< GT, Tree >::node_map.

Member Data Documentation

◆ copied_graph

template<class GT , template< class, class > class Tree = Treap>
GT Aleph::GraphCopyWithMapping< GT, Tree >::copied_graph
private

Definition at line 3889 of file tpl_graph.H.

Referenced by Aleph::GraphCopyWithMapping< GT, Tree >::build_copy(), Aleph::GraphCopyWithMapping< GT, Tree >::clear(), Aleph::GraphCopyWithMapping< GT, Tree >::get_graph(), Aleph::GraphCopyWithMapping< GT, Tree >::get_graph(), Aleph::GraphCopyWithMapping< GT, Tree >::insert_arc(), Aleph::GraphCopyWithMapping< GT, Tree >::insert_unmapped_node(), Aleph::GraphCopyWithMapping< GT, Tree >::insert_unmapped_node(), Aleph::GraphCopyWithMapping< GT, Tree >::num_arcs(), Aleph::GraphCopyWithMapping< GT, Tree >::remove_arc(), and Aleph::GraphCopyWithMapping< GT, Tree >::remove_node().

◆ node_map

template<class GT , template< class, class > class Tree = Treap>
DynMapTree<Node *, Node *, Tree> Aleph::GraphCopyWithMapping< GT, Tree >::node_map
private

Definition at line 3890 of file tpl_graph.H.

Referenced by Aleph::GraphCopyWithMapping< GT, Tree >::build_copy(), Aleph::GraphCopyWithMapping< GT, Tree >::clear(), Aleph::GraphCopyWithMapping< GT, Tree >::for_each_mapping(), Aleph::GraphCopyWithMapping< GT, Tree >::get_copy(), Aleph::GraphCopyWithMapping< GT, Tree >::has_copy(), Aleph::GraphCopyWithMapping< GT, Tree >::num_nodes(), Aleph::GraphCopyWithMapping< GT, Tree >::remove_node(), and Aleph::GraphCopyWithMapping< GT, Tree >::search_copy().

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