__DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc > Class Template Reference
[Classes and types for internal use]
Directed graph base class.
More...
#include <vgtl_dag.h>
Public Types | |
| typedef _Ctr | container_type |
| typedef _Iterator | children_iterator |
| typedef _Iterator | parents_iterator |
| typedef _Base::allocator_type | allocator_type |
| typedef _DG_iterator< _Tp, _Tp &, _Tp *, container_type, children_iterator, children_const_iterator > | iterator |
| typedef _DG_iterator< _Tp, const _Tp &, const _Tp *, container_type, children_iterator, children_const_iterator > | const_iterator |
| typedef std::reverse_iterator < const_iterator > | const_reverse_iterator |
| typedef std::reverse_iterator < iterator > | reverse_iterator |
| typedef _DG_walker< _Tp, _Tp &, _Tp *, container_type, children_iterator, children_const_iterator > | walker |
| typedef _DG_walker< _Tp, const _Tp &, const _Tp *, container_type, children_iterator, children_const_iterator > | const_walker |
| typedef std::pair< walker, walker > | edge |
| typedef std::pair< edge, bool > | enhanced_edge |
| typedef _Tp | value_type |
| typedef _Node | node_type |
| typedef value_type * | pointer |
| typedef const value_type * | const_pointer |
| typedef value_type & | reference |
| typedef const value_type & | const_reference |
| typedef size_t | size_type |
| typedef ptrdiff_t | difference_type |
Public Member Functions | |
| allocator_type | get_allocator () const |
| __DG (const allocator_type &__a=allocator_type()) | |
| walker | ground () |
| walker | sky () |
| const_walker | ground () const |
| const_walker | sky () const |
| children_iterator | root_begin () |
| children_iterator | root_end () |
| children_const_iterator | root_begin () const |
| children_const_iterator | root_end () const |
| parents_iterator | leaf_begin () |
| parents_iterator | leaf_end () |
| parents_const_iterator | leaf_begin () const |
| parents_const_iterator | leaf_end () const |
| bool | empty () const |
| size_type | size () const |
| size_type | max_size () const |
| void | swap (_Self &__x) |
| walker | insert_node_in_graph (_Node *__n, const walker &__parent, const walker &__child, const container_insert_arg &__Itc, const container_insert_arg &__Itp) |
| walker | insert_in_graph (const _Tp &__x, const walker &__parent, const walker &__child, const container_insert_arg &__Itc, const container_insert_arg &__Itp) |
| walker | insert_in_graph (const walker &__parent, const walker &__child, const container_insert_arg &__Itc, const container_insert_arg &__Itp) |
| void | insert_subgraph (_Self &__subgraph, const walker &__parent, const walker &__child, const container_insert_arg &__Itc, const container_insert_arg &__Itp) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr1, template< class __Tp, class __AllocTp > class __SequenceCtr2, class _Allocator1 , class _Allocator2 > | |
| walker | insert_node_in_graph (_Node *__node, const __SequenceCtr1< walker, _Allocator1 > &__parents, const __SequenceCtr2< walker, _Allocator2 > &__children) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr1, template< class __Tp, class __AllocTp > class __SequenceCtr2, class _Allocator1 , class _Allocator2 > | |
| walker | insert_in_graph (const _Tp &__x, const __SequenceCtr1< walker, _Allocator1 > &__parents, const __SequenceCtr2< walker, _Allocator2 > &__children) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr1, template< class __Tp, class __AllocTp > class __SequenceCtr2, class _Allocator1 , class _Allocator2 > | |
| walker | insert_in_graph (const __SequenceCtr1< walker, _Allocator1 > &__parents, const __SequenceCtr2< walker, _Allocator2 > &__children) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr, class _Allocator > | |
| walker | insert_node_in_graph (_Node *__node, const walker &__parent, const container_insert_arg &__pref, const __SequenceCtr< walker, _Allocator > &__children) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr, class _Allocator > | |
| walker | insert_in_graph (const _Tp &__x, const walker &__parent, const container_insert_arg &__pref, const __SequenceCtr< walker, _Allocator > &__children) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr, class _Allocator > | |
| walker | insert_in_graph (const walker &__parent, const container_insert_arg &__pref, const __SequenceCtr< walker, _Allocator > &__children) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr, class _Allocator > | |
| walker | insert_node_in_graph (_Node *__node, const __SequenceCtr< walker, _Allocator > &__parents, const walker &__child, const container_insert_arg &__cref) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr, class _Allocator > | |
| walker | insert_in_graph (const _Tp &__x, const __SequenceCtr< walker, _Allocator > &__parents, const walker &__child, const container_insert_arg &__cref) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr, class _Allocator > | |
| walker | insert_in_graph (const __SequenceCtr< walker, _Allocator > &__parents, const walker &__child, const container_insert_arg &__cref) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr1, template< class __Tp, class __AllocTp > class __SequenceCtr2, class _Allocator1 , class _Allocator2 > | |
| void | insert_subgraph (_Self &__subgraph, const __SequenceCtr1< walker, _Allocator1 > &__parents, const __SequenceCtr2< walker, _Allocator2 > &__children) |
| void | add_edge (const edge &__edge, const container_insert_arg &__Itc, const container_insert_arg &__Itp) |
| void | add_edge (const walker &__parent, const walker &__child, const container_insert_arg &__Itc, const container_insert_arg &__Itp) |
| void | replace_edge_to_child (const walker &__parent, const walker &__child_old, const walker &__child_new) |
| void | replace_edge_to_parent (const walker &__parent_old, const walker &__parent_new, const walker &__child) |
| void | remove_edge (const edge &__edge) |
| void | remove_edge_and_deattach (const walker &__parent, const walker &__child) |
| void | remove_edge (const walker &__parent, const walker &__child) |
| template<class Compare > | |
| void | sort_child_edges (walker __position, children_iterator first, children_iterator last, Compare comp) |
| template<class Compare > | |
| void | sort_parent_edges (walker __position, parents_iterator first, parents_iterator last, Compare comp) |
| template<class Compare > | |
| void | sort_child_edges (walker __position, Compare comp) |
| template<class Compare > | |
| void | sort_parent_edges (walker __position, Compare comp) |
| walker | insert_node (_Node *_node, const walker &__position, const container_insert_arg &__It) |
| walker | insert_node (const _Tp &__x, const walker &__position, const container_insert_arg &__It) |
| walker | insert_node (const walker &__position, const container_insert_arg &__It) |
| walker | insert_node_before (_Node *_node, const walker &__position, const container_insert_arg &__It) |
| void | insert_node_before (const _Tp &__x, const walker &__position, const container_insert_arg &__It) |
| void | insert_node_before (const walker &__position, const container_insert_arg &__It) |
| void | merge (const walker &__position, const walker &__second, bool merge_parent_edges=true, bool merge_child_edges=true) |
| void | erase (const walker &__position) |
| void | partial_erase_to_parent (const walker &__position, const walker &__parent, unsigned int idx) |
| void | clear_erased_part (erased_part &_ep) |
| erased_part | erase_maximal_subgraph (const walker &__position) |
| erased_part | erase_minimal_subgraph (const walker &__position) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr, class _Allocator > | |
| erased_part | erase_maximal_subgraph (const __SequenceCtr< walker, _Allocator > &__positions) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr, class _Allocator > | |
| erased_part | erase_minimal_subgraph (const __SequenceCtr< walker, _Allocator > &__positions) |
| erased_part | erase_maximal_pregraph (const walker &__position) |
| erased_part | erase_minimal_pregraph (const walker &__position) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr, class _Allocator > | |
| erased_part | erase_maximal_pregraph (const __SequenceCtr< walker, _Allocator > &__positions) |
| template<template< class __Tp, class __AllocTp > class __SequenceCtr, class _Allocator > | |
| erased_part | erase_minimal_pregraph (const __SequenceCtr< walker, _Allocator > &__positions) |
| bool | erase_child (const walker &__position, const children_iterator &__It) |
| bool | erase_parent (const walker &__position, const parents_iterator &__It) |
| void | clear () |
| __DG (const _Self &__x) | |
| ~__DG () | |
| _Self & | operator= (const _Self &__x) |
| _Self & | operator= (const _RV_DG &__rl) |
| _Self & | operator= (const erased_part &__ep) |
Protected Types | |
| typedef std::pair< _RV_DG, std::vector< enhanced_edge > > | erased_part |
Protected Member Functions | |
| _Node * | _C_create_node (const _Tp &__x) |
| _Node * | _C_create_node () |
| void | _C_destroy_node (_Node *__p) |
| void | clear_graph (_DG_node< _Tp, _Ctr, _Iterator > *_node) |
| _DG_node< _Tp, _Ctr, _Iterator > * | _C_get_node () |
| void | _C_put_node (_DG_node< _Tp, _Ctr, _Iterator > *__p) |
| void | clear_children () |
| void | clear_parents () |
| void | add_all_children (_Output_Iterator fi, _DG_node< _Tp, _Ctr, _Iterator > *_parent) |
| void | add_all_parents (_Output_Iterator fi, _DG_node< _Tp, _Ctr, _Iterator > *_child) |
Protected Attributes | |
| _DG_node< _Tp, _Ctr, _Iterator > * | _C_ground |
| _DG_node< _Tp, _Ctr, _Iterator > * | _C_sky |
| int | _C_mark |
Detailed Description
template<class _Tp, class _Ctr, class _Iterator, class _CIterator, class _Inserter, class _Alloc>
class __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >
This is the toplevel base class for all directed graphs independent of allocators
Definition at line 557 of file vgtl_dag.h.
Member Typedef Documentation
| typedef _Base::allocator_type __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::allocator_type |
allocator type
Reimplemented from _DG_base< _Tp, _Ctr, _Iterator, _CIterator, _Alloc >.
Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >.
Definition at line 590 of file vgtl_dag.h.
| typedef _Iterator __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::children_iterator |
iterator for accessing the children
Reimplemented from _DG_base< _Tp, _Ctr, _Iterator, _CIterator, _Alloc >.
Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >.
Definition at line 561 of file vgtl_dag.h.
| typedef _DG_iterator<_Tp,const _Tp&,const _Tp*,container_type, children_iterator,children_const_iterator> __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::const_iterator |
the const iterator
Definition at line 600 of file vgtl_dag.h.
| typedef const value_type* __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::const_pointer |
standard typedef
Definition at line 583 of file vgtl_dag.h.
| typedef const value_type& __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::const_reference |
standard typedef
Definition at line 585 of file vgtl_dag.h.
| typedef std::reverse_iterator<const_iterator> __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::const_reverse_iterator |
the const reverse iterator
Definition at line 604 of file vgtl_dag.h.
| typedef _DG_walker<_Tp,const _Tp&,const _Tp*,container_type,children_iterator, children_const_iterator> __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::const_walker |
the (recursive) const walker
Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >.
Definition at line 623 of file vgtl_dag.h.
| typedef _Ctr __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::container_type |
internal container used to store the children
Reimplemented from _DG_base< _Tp, _Ctr, _Iterator, _CIterator, _Alloc >.
Definition at line 560 of file vgtl_dag.h.
| typedef ptrdiff_t __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::difference_type |
standard typedef
Definition at line 587 of file vgtl_dag.h.
| typedef std::pair<walker,walker> __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::edge |
an edge of the graph (parent, child)
Definition at line 626 of file vgtl_dag.h.
| typedef std::pair<edge,bool> __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::enhanced_edge |
an edge with additiona information about erased ground/sky edges
Definition at line 628 of file vgtl_dag.h.
typedef std::pair<_RV_DG, std::vector<enhanced_edge> > __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::erased_part [protected] |
an erased subgraph which is not yet a new directed graph
Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >.
Definition at line 632 of file vgtl_dag.h.
| typedef _DG_iterator<_Tp,_Tp&,_Tp*,container_type,children_iterator, children_const_iterator> __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::iterator |
the iterator
Definition at line 597 of file vgtl_dag.h.
| typedef _Node __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::node_type |
standard typedef
Definition at line 581 of file vgtl_dag.h.
| typedef _Iterator __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::parents_iterator |
iterator for accessing the parents
Reimplemented from _DG_base< _Tp, _Ctr, _Iterator, _CIterator, _Alloc >.
Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >.
Definition at line 562 of file vgtl_dag.h.
| typedef value_type* __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::pointer |
standard typedef
Definition at line 582 of file vgtl_dag.h.
| typedef value_type& __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::reference |
standard typedef
Definition at line 584 of file vgtl_dag.h.
| typedef std::reverse_iterator<iterator> __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::reverse_iterator |
the reverse iterator
Definition at line 606 of file vgtl_dag.h.
| typedef size_t __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::size_type |
standard typedef
Definition at line 586 of file vgtl_dag.h.
| typedef _Tp __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::value_type |
standard typedef
Definition at line 580 of file vgtl_dag.h.
| typedef _DG_walker<_Tp,_Tp&,_Tp*,container_type,children_iterator, children_const_iterator> __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::walker |
the (recursive) walker
Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >.
Definition at line 620 of file vgtl_dag.h.
Constructor & Destructor Documentation
| __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::__DG | ( | const allocator_type & | __a = allocator_type() |
) | [inline, explicit] |
standard constructor
Definition at line 684 of file vgtl_dag.h.
| __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::__DG | ( | const _Self & | __x | ) | [inline] |
copy constructor
Definition at line 1992 of file vgtl_dag.h.
| __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::~__DG | ( | ) | [inline] |
standard destructor
Definition at line 2009 of file vgtl_dag.h.
Member Function Documentation
| _Node* __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::_C_create_node | ( | ) | [inline, protected] |
construct a new tree node containing default data
Definition at line 659 of file vgtl_dag.h.
| _Node* __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::_C_create_node | ( | const _Tp & | __x | ) | [inline, protected] |
construct a new tree node containing data __x
Definition at line 645 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::_C_destroy_node | ( | _Node * | __p | ) | [inline, protected] |
construct a new tree node containing default data
Definition at line 673 of file vgtl_dag.h.
| _DG_node<_Tp ,_Ctr ,_Iterator >* _DG_base< _Tp , _Ctr , _Iterator , _CIterator , _Alloc >::_C_get_node | ( | ) | [inline, protected, inherited] |
allocate a new node
Definition at line 405 of file vgtl_dagbase.h.
| void _DG_base< _Tp , _Ctr , _Iterator , _CIterator , _Alloc >::_C_put_node | ( | _DG_node< _Tp , _Ctr , _Iterator > * | __p | ) | [inline, protected, inherited] |
deallocate a node
Definition at line 408 of file vgtl_dagbase.h.
| void _DG_base< _Tp, _Ctr, _Iterator, _CIterator, _Alloc >::add_all_children | ( | _Output_Iterator | fi, | |
| _DG_node< _Tp , _Ctr , _Iterator > * | _parent | |||
| ) | [inline, protected, inherited] |
add all children to the parent _parent. fi is a iterator to the children container of the parent
Definition at line 475 of file vgtl_dagbase.h.
| void _DG_base< _Tp, _Ctr, _Iterator, _CIterator, _Alloc >::add_all_parents | ( | _Output_Iterator | fi, | |
| _DG_node< _Tp , _Ctr , _Iterator > * | _child | |||
| ) | [inline, protected, inherited] |
add all parents to the child _child. fi is a iterator to the parents container of the child
Definition at line 484 of file vgtl_dagbase.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::add_edge | ( | const walker & | __parent, | |
| const walker & | __child, | |||
| const container_insert_arg & | __Itc, | |||
| const container_insert_arg & | __Itp | |||
| ) | [inline] |
add an edge between __parent and __child at positions __Itc and __Itp, respectively
Definition at line 1079 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::add_edge | ( | const edge & | __edge, | |
| const container_insert_arg & | __Itc, | |||
| const container_insert_arg & | __Itp | |||
| ) | [inline] |
add one edge between two nodes at the positions described by __Itc and __Itp.
Definition at line 1070 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::clear | ( | ) | [inline] |
erase all the nodes except sky and ground
Reimplemented from _DG_base< _Tp, _Ctr, _Iterator, _CIterator, _Alloc >.
Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >.
Definition at line 1952 of file vgtl_dag.h.
| void _DG_base< _Tp , _Ctr , _Iterator , _CIterator , _Alloc >::clear_children | ( | ) | [inline, protected, inherited] |
clear all children of the root node
Definition at line 420 of file vgtl_dagbase.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::clear_erased_part | ( | erased_part & | _ep | ) | [inline] |
clear all nodes in an erased part
Definition at line 1751 of file vgtl_dag.h.
| void _DG_base< _Tp, _Ctr, _Iterator, _CIterator, _Alloc >::clear_graph | ( | _DG_node< _Tp , _Ctr , _Iterator > * | _node | ) | [inline, protected, inherited] |
removes recursively all nodes downward starting from _node.
Definition at line 444 of file vgtl_dagbase.h.
| void _DG_base< _Tp , _Ctr , _Iterator , _CIterator , _Alloc >::clear_parents | ( | ) | [inline, protected, inherited] |
clear all parents of the leaf node
Definition at line 423 of file vgtl_dagbase.h.
| bool __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::empty | ( | ) | const [inline] |
returns true if the DG is empty
Definition at line 767 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::erase | ( | const walker & | __position | ) | [inline] |
erase a node from the DG except the sky and ground
Definition at line 1400 of file vgtl_dag.h.
| bool __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::erase_child | ( | const walker & | __position, | |
| const children_iterator & | __It | |||
| ) | [inline] |
Erase a child of __position. This works if and only if the child has only one child and no other parents.
Definition at line 1904 of file vgtl_dag.h.
| erased_part __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::erase_maximal_pregraph | ( | const __SequenceCtr< walker, _Allocator > & | __positions | ) | [inline] |
here every child is removed till the sky included all nodes from __positions. The removed subgraph is returned. The subgraph is maximal, i.e. all nodes are removed, which are reachable from any node from __positions by walking up.
Definition at line 1868 of file vgtl_dag.h.
| erased_part __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::erase_maximal_pregraph | ( | const walker & | __position | ) | [inline] |
here every child is removed till the sky node. included the node at __position. The removed subgraph is returned. The subgraph is maximal, i.e. all nodes are removed, which are reachable from __position by walking upwards.
Definition at line 1834 of file vgtl_dag.h.
| erased_part __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::erase_maximal_subgraph | ( | const __SequenceCtr< walker, _Allocator > & | __positions | ) | [inline] |
here every child is removed till the last base node, included all nodes from __positions. The removed subgraph is returned. The subgraph is maximal, i.e. all nodes are removed, which are reachable from any node from __positions by walking down.
Definition at line 1797 of file vgtl_dag.h.
| erased_part __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::erase_maximal_subgraph | ( | const walker & | __position | ) | [inline] |
here every child is removed till the last base node, included the node at __position. The removed subgraph is returned. The subgraph is maximal, i.e. all nodes are removed, which are reachable from __position by walking down.
Definition at line 1763 of file vgtl_dag.h.
| erased_part __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::erase_minimal_pregraph | ( | const __SequenceCtr< walker, _Allocator > & | __positions | ) | [inline] |
here every child is removed till the sky. included all nodes from __positions. The removed subgraph is returned. The subgraph is minimal, i.e. only nodes are removed, which have no other ancestor than any node in __positions. I.e., when walking towards the ground, there is no way which bypasses all nodes in __positions.
Definition at line 1888 of file vgtl_dag.h.
| erased_part __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::erase_minimal_pregraph | ( | const walker & | __position | ) | [inline] |
here every child is removed till the sky. included the node at __position. The removed subgraph is returned. The subgraph is minimal, i.e. only nodes are removed, which have no other descendant than __position. I.e., when walking towards the sky, there is no way which bypasses __position.
Definition at line 1850 of file vgtl_dag.h.
| erased_part __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::erase_minimal_subgraph | ( | const __SequenceCtr< walker, _Allocator > & | __positions | ) | [inline] |
here every child is removed till the last base node, included all nodes from __positions. The removed subgraph is returned. The subgraph is minimal, i.e. only nodes are removed, which have no other ancestor than any node in __positions. I.e., when walking towards the ground, there is no way which bypasses all nodes in __positions.
Definition at line 1817 of file vgtl_dag.h.
| erased_part __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::erase_minimal_subgraph | ( | const walker & | __position | ) | [inline] |
here every child is removed till the last base node, included the node at __position. The removed subgraph is returned. The subgraph is minimal, i.e. only nodes are removed, which have no other ancestor than __position. I.e., when walking towards the ground, there is no way which bypasses __position.
Definition at line 1779 of file vgtl_dag.h.
| bool __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::erase_parent | ( | const walker & | __position, | |
| const parents_iterator & | __It | |||
| ) | [inline] |
Erase a parent of __position. This works if and only if the parent has only one parent and no other children.
Definition at line 1930 of file vgtl_dag.h.
| allocator_type __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::get_allocator | ( | ) | const [inline] |
construct an allocator object
Reimplemented from _DG_base< _Tp, _Ctr, _Iterator, _CIterator, _Alloc >.
Definition at line 592 of file vgtl_dag.h.
| const_walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::ground | ( | ) | const [inline] |
return a const walker to the virtual ground node.
Definition at line 697 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::ground | ( | ) | [inline] |
return a walker to the virtual ground node.
Definition at line 687 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_in_graph | ( | const __SequenceCtr< walker, _Allocator > & | __parents, | |
| const walker & | __child, | |||
| const container_insert_arg & | __cref | |||
| ) | [inline] |
insert a node with default data into the graph between all parents from __parents and the child __child.
Definition at line 1006 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_in_graph | ( | const _Tp & | __x, | |
| const __SequenceCtr< walker, _Allocator > & | __parents, | |||
| const walker & | __child, | |||
| const container_insert_arg & | __cref | |||
| ) | [inline] |
insert a node with data __x into the graph between all parents from __parents and the child __child.
Definition at line 991 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_in_graph | ( | const walker & | __parent, | |
| const container_insert_arg & | __pref, | |||
| const __SequenceCtr< walker, _Allocator > & | __children | |||
| ) | [inline] |
insert a node with data __x into the graph between the parent __parent and all children from __children.
Definition at line 952 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_in_graph | ( | const _Tp & | __x, | |
| const walker & | __parent, | |||
| const container_insert_arg & | __pref, | |||
| const __SequenceCtr< walker, _Allocator > & | __children | |||
| ) | [inline] |
insert a node with data __x into the graph between the parent __parent and all children from __children.
Definition at line 938 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_in_graph | ( | const __SequenceCtr1< walker, _Allocator1 > & | __parents, | |
| const __SequenceCtr2< walker, _Allocator2 > & | __children | |||
| ) | [inline] |
insert a node with default data into the graph between all parents from __parents and all children from __children.
Definition at line 900 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_in_graph | ( | const _Tp & | __x, | |
| const __SequenceCtr1< walker, _Allocator1 > & | __parents, | |||
| const __SequenceCtr2< walker, _Allocator2 > & | __children | |||
| ) | [inline] |
insert a node with data __x into the graph between all parents from __parents and all children from __children.
Definition at line 885 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_in_graph | ( | const walker & | __parent, | |
| const walker & | __child, | |||
| const container_insert_arg & | __Itc, | |||
| const container_insert_arg & | __Itp | |||
| ) | [inline] |
insert node with default data into the graph between __parent and __child, the edge at the specific positions described by __Itc and __Itp.
Definition at line 821 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_in_graph | ( | const _Tp & | __x, | |
| const walker & | __parent, | |||
| const walker & | __child, | |||
| const container_insert_arg & | __Itc, | |||
| const container_insert_arg & | __Itp | |||
| ) | [inline] |
insert node with data __n into the graph between __parent and __child, the edge at the specific positions described by __Itc and __Itp.
Definition at line 807 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_node | ( | const walker & | __position, | |
| const container_insert_arg & | __It | |||
| ) | [inline] |
insert a new node with default data as child of __position
Definition at line 1281 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_node | ( | const _Tp & | __x, | |
| const walker & | __position, | |||
| const container_insert_arg & | __It | |||
| ) | [inline] |
insert a new node with data __x as child of __position
Definition at line 1275 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_node | ( | _Node * | _node, | |
| const walker & | __position, | |||
| const container_insert_arg & | __It | |||
| ) | [inline] |
insert one node as child of __position
Definition at line 1261 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_node_before | ( | const walker & | __position, | |
| const container_insert_arg & | __It | |||
| ) | [inline] |
insert a new node with default data as parent of __position
Definition at line 1305 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_node_before | ( | const _Tp & | __x, | |
| const walker & | __position, | |||
| const container_insert_arg & | __It | |||
| ) | [inline] |
insert a new node with data __x as parent of __position
Definition at line 1300 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_node_before | ( | _Node * | _node, | |
| const walker & | __position, | |||
| const container_insert_arg & | __It | |||
| ) | [inline] |
insert a node as parent of __position
Definition at line 1286 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_node_in_graph | ( | _Node * | __node, | |
| const __SequenceCtr< walker, _Allocator > & | __parents, | |||
| const walker & | __child, | |||
| const container_insert_arg & | __cref | |||
| ) | [inline] |
insert node __n into the graph between all parents from __parents and the child __child.
Definition at line 966 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_node_in_graph | ( | _Node * | __node, | |
| const walker & | __parent, | |||
| const container_insert_arg & | __pref, | |||
| const __SequenceCtr< walker, _Allocator > & | __children | |||
| ) | [inline] |
insert node __n into the graph between the parent __parent and all children from __children.
Definition at line 913 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_node_in_graph | ( | _Node * | __node, | |
| const __SequenceCtr1< walker, _Allocator1 > & | __parents, | |||
| const __SequenceCtr2< walker, _Allocator2 > & | __children | |||
| ) | [inline] |
insert node __n into the graph between all parents from __parents and all children from __children.
Definition at line 854 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_node_in_graph | ( | _Node * | __n, | |
| const walker & | __parent, | |||
| const walker & | __child, | |||
| const container_insert_arg & | __Itc, | |||
| const container_insert_arg & | __Itp | |||
| ) | [inline] |
insert node __n into the graph between __parent and __child, the edge at the specific positions described by __Itc and __Itp.
Definition at line 791 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_subgraph | ( | _Self & | __subgraph, | |
| const __SequenceCtr1< walker, _Allocator1 > & | __parents, | |||
| const __SequenceCtr2< walker, _Allocator2 > & | __children | |||
| ) | [inline] |
in this method one DG is inserted into another DG between the parents __parents and the children __children.
Definition at line 1020 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::insert_subgraph | ( | _Self & | __subgraph, | |
| const walker & | __parent, | |||
| const walker & | __child, | |||
| const container_insert_arg & | __Itc, | |||
| const container_insert_arg & | __Itp | |||
| ) | [inline] |
insert a subgraph into the graph between __parent and __child, the edge at the specific positions described by __Itc and __Itp.
Definition at line 832 of file vgtl_dag.h.
| parents_const_iterator __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::leaf_begin | ( | ) | const [inline] |
return the first leaf of the directed graph
Definition at line 728 of file vgtl_dag.h.
| parents_iterator __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::leaf_begin | ( | ) | [inline] |
return the first leaf of the directed graph
Definition at line 721 of file vgtl_dag.h.
| parents_const_iterator __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::leaf_end | ( | ) | const [inline] |
return beyond the last leaf of the directed graph
Definition at line 731 of file vgtl_dag.h.
| parents_iterator __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::leaf_end | ( | ) | [inline] |
return beyond the last leaf of the directed graph
Definition at line 724 of file vgtl_dag.h.
| size_type __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::max_size | ( | ) | const [inline] |
the maximum size of a DG is virtually unlimited
Definition at line 778 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::merge | ( | const walker & | __position, | |
| const walker & | __second, | |||
| bool | merge_parent_edges = true, |
|||
| bool | merge_child_edges = true | |||
| ) | [inline] |
merge two nodes, call also the merge method for the node data
Definition at line 1311 of file vgtl_dag.h.
| _Self& __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::operator= | ( | const erased_part & | __ep | ) | [inline] |
assignment operator from an erased part
Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >.
Definition at line 2023 of file vgtl_dag.h.
| _Self& __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::operator= | ( | const _RV_DG & | __rl | ) | [inline] |
assignment operator from a part of an erased part
Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >.
Definition at line 2015 of file vgtl_dag.h.
| _Self& __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::operator= | ( | const _Self & | __x | ) |
standard assignment operator
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::partial_erase_to_parent | ( | const walker & | __position, | |
| const walker & | __parent, | |||
| unsigned int | idx | |||
| ) | [inline] |
split a node in two, the first connected to the __parent, the second connected to all other parents. Then erase the first node.
Definition at line 1461 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::remove_edge | ( | const walker & | __parent, | |
| const walker & | __child | |||
| ) | [inline] |
just remove one edge between __parent and __child
Definition at line 1214 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::remove_edge | ( | const edge & | __edge | ) | [inline] |
remove an edge with a particular parent and child
Definition at line 1197 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::remove_edge_and_deattach | ( | const walker & | __parent, | |
| const walker & | __child | |||
| ) | [inline] |
remove one egde and don't reconnect the node to sky/ground
Definition at line 1201 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::replace_edge_to_child | ( | const walker & | __parent, | |
| const walker & | __child_old, | |||
| const walker & | __child_new | |||
| ) | [inline] |
change the edge from __parent to __child_old to an edge from __parent to __child_new.
Definition at line 1125 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::replace_edge_to_parent | ( | const walker & | __parent_old, | |
| const walker & | __parent_new, | |||
| const walker & | __child | |||
| ) | [inline] |
change the edge from __parent_old to __child to an edge from __parent_new to __child.
Definition at line 1163 of file vgtl_dag.h.
| children_const_iterator __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::root_begin | ( | ) | const [inline] |
return the first root of the directed graph
Definition at line 714 of file vgtl_dag.h.
| children_iterator __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::root_begin | ( | ) | [inline] |
return the first root of the directed graph
Definition at line 707 of file vgtl_dag.h.
| children_const_iterator __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::root_end | ( | ) | const [inline] |
return beyond the last root of the directed graph
Definition at line 717 of file vgtl_dag.h.
| children_iterator __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::root_end | ( | ) | [inline] |
return beyond the last root of the directed graph
Definition at line 710 of file vgtl_dag.h.
| size_type __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::size | ( | ) | const [inline] |
returns the size of the DG (number of nodes)
Definition at line 771 of file vgtl_dag.h.
| const_walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::sky | ( | ) | const [inline] |
return a const walker to the virtual sky node.
Definition at line 702 of file vgtl_dag.h.
| walker __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::sky | ( | ) | [inline] |
return a walker to the virtual sky node.
Definition at line 692 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::sort_child_edges | ( | walker | __position, | |
| Compare | comp | |||
| ) | [inline] |
sort all child edges according to comp
Definition at line 1250 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::sort_child_edges | ( | walker | __position, | |
| children_iterator | first, | |||
| children_iterator | last, | |||
| Compare | comp | |||
| ) | [inline] |
sort the child edges in the range [first,last) according to comp
Definition at line 1238 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::sort_parent_edges | ( | walker | __position, | |
| Compare | comp | |||
| ) | [inline] |
sort all parent edges according to comp
Definition at line 1256 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::sort_parent_edges | ( | walker | __position, | |
| parents_iterator | first, | |||
| parents_iterator | last, | |||
| Compare | comp | |||
| ) | [inline] |
sort the parent edges in the range [first,last) according to comp
Definition at line 1244 of file vgtl_dag.h.
| void __DG< _Tp, _Ctr, _Iterator, _CIterator, _Inserter, _Alloc >::swap | ( | _Self & | __x | ) | [inline] |
swap two DGs
Definition at line 781 of file vgtl_dag.h.
Member Data Documentation
_DG_node<_Tp ,_Ctr ,_Iterator >* _DG_base< _Tp , _Ctr , _Iterator , _CIterator , _Alloc >::_C_ground [protected, inherited] |
the virtual ground node (below all roots)
Definition at line 413 of file vgtl_dagbase.h.
an internal counter for setting marks during certain algorithms
Definition at line 417 of file vgtl_dagbase.h.
_DG_node<_Tp ,_Ctr ,_Iterator >* _DG_base< _Tp , _Ctr , _Iterator , _CIterator , _Alloc >::_C_sky [protected, inherited] |
the virtual sky node (above all leafs)
Definition at line 415 of file vgtl_dagbase.h.
The documentation for this class was generated from the following file:
