#include <vgtl_dag.h>
Inheritance diagram for __DG< _Tp, _Ctr, _Iterator, _Inserter, _Alloc >:
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 > | iterator |
typedef _DG_iterator< _Tp, const _Tp &, const _Tp *, container_type, children_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 > | walker |
typedef _DG_walker< _Tp, const _Tp &, const _Tp *, container_type, children_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 Methods | |
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 () |
parents_iterator | leaf_begin () |
parents_iterator | leaf_end () |
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 | 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) |
void | clear_children () |
void | clear_parents () |
template<class _Output_Iterator> void | add_all_children (_Output_Iterator fi, _DG_node< _Tp, _Ctr, _Iterator > *_parent) |
template<class _Output_Iterator> void | add_all_parents (_Output_Iterator fi, _DG_node< _Tp, _Ctr, _Iterator > *_child) |
Protected Types | |
typedef std::pair< _RV_DG, std::vector< enhanced_edge > > | erased_part |
Protected Methods | |
_Node * | _C_create_node (const _Tp &__x) |
_Node * | _C_create_node () |
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) |
Protected Attributes | |
_DG_node< _Tp, _Ctr, _Iterator > * | _C_ground |
_DG_node< _Tp, _Ctr, _Iterator > * | _C_sky |
int | _C_mark |
Friends | |
bool | operator==__VGTL_NULL_TMPL_ARGS (const __DG &__x, const __DG &__y) |
Definition at line 506 of file vgtl_dag.h.
|
allocator type Reimplemented from _DG_base< _Tp, _Ctr, _Iterator, _Alloc >. Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >. Definition at line 535 of file vgtl_dag.h. |
|
iterator for accessing the children Reimplemented from _DG_base< _Tp, _Ctr, _Iterator, _Alloc >. Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >. Definition at line 510 of file vgtl_dag.h. |
|
the const iterator Definition at line 543 of file vgtl_dag.h. |
|
standard typedef Definition at line 528 of file vgtl_dag.h. |
|
standard typedef Definition at line 530 of file vgtl_dag.h. |
|
the const reverse iterator Definition at line 547 of file vgtl_dag.h. |
|
the (recursive) const walker Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >. Definition at line 564 of file vgtl_dag.h. |
|
internal container used to store the children and parents Reimplemented from _DG_base< _Tp, _Ctr, _Iterator, _Alloc >. Definition at line 509 of file vgtl_dag.h. |
|
standard typedef Definition at line 532 of file vgtl_dag.h. |
|
an edge of the graph (parent, child) Definition at line 567 of file vgtl_dag.h. |
|
an edge with additiona information about erased ground/sky edges Definition at line 569 of file vgtl_dag.h. |
|
an erased subgraph which is not yet a new directed graph Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >. Definition at line 573 of file vgtl_dag.h. |
|
the iterator Definition at line 541 of file vgtl_dag.h. |
|
standard typedef Definition at line 526 of file vgtl_dag.h. |
|
iterator for accessing the parents Reimplemented from _DG_base< _Tp, _Ctr, _Iterator, _Alloc >. Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >. Definition at line 511 of file vgtl_dag.h. |
|
standard typedef Definition at line 527 of file vgtl_dag.h. |
|
standard typedef Definition at line 529 of file vgtl_dag.h. |
|
the reverse iterator Definition at line 549 of file vgtl_dag.h. |
|
standard typedef Definition at line 531 of file vgtl_dag.h. |
|
standard typedef Definition at line 525 of file vgtl_dag.h. |
|
the (recursive) walker Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >. Definition at line 562 of file vgtl_dag.h. |
|
standard constructor Definition at line 615 of file vgtl_dag.h. |
|
copy constructor Definition at line 1822 of file vgtl_dag.h. |
|
standard destructor Definition at line 1839 of file vgtl_dag.h. |
|
construct a new tree node containing default data Definition at line 600 of file vgtl_dag.h. |
|
construct a new tree node containing data Definition at line 586 of file vgtl_dag.h. |
|
allocates the memory of one node Definition at line 194 of file vgtl_dagbase.h. |
|
de-allocates the memory of one node Definition at line 197 of file vgtl_dagbase.h. |
|
add all children to the parent Definition at line 459 of file vgtl_dagbase.h. |
|
add all parents to the child Definition at line 466 of file vgtl_dagbase.h. |
|
add an edge between Definition at line 980 of file vgtl_dag.h. |
|
add one edge between two nodes at the positions described by Definition at line 971 of file vgtl_dag.h. |
|
erase all the nodes except sky and ground Reimplemented from _DG_base< _Tp, _Ctr, _Iterator, _Alloc >. Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >. Definition at line 1782 of file vgtl_dag.h. |
|
clear all children of the ground node Definition at line 314 of file vgtl_dagbase.h. |
|
clear all nodes in an erased part Definition at line 1582 of file vgtl_dag.h. |
|
removes all the nodes of the graph except the sky and ground nodes Definition at line 430 of file vgtl_dagbase.h. |
|
clear all parents of the sky node Definition at line 317 of file vgtl_dagbase.h. |
|
returns Definition at line 668 of file vgtl_dag.h. |
|
erase a node from the DG except the sky and ground Definition at line 1297 of file vgtl_dag.h. |
|
Erase a child of Definition at line 1734 of file vgtl_dag.h. |
|
here every child is removed till the sky included all nodes from Definition at line 1698 of file vgtl_dag.h. |
|
here every child is removed till the sky node. included the node at Definition at line 1664 of file vgtl_dag.h. |
|
here every child is removed till the last base node, included all nodes from Definition at line 1627 of file vgtl_dag.h. |
|
here every child is removed till the last base node, included the node at Definition at line 1593 of file vgtl_dag.h. |
|
here every child is removed till the sky. included all nodes from Definition at line 1718 of file vgtl_dag.h. |
|
here every child is removed till the sky. included the node at Definition at line 1680 of file vgtl_dag.h. |
|
here every child is removed till the last base node, included all nodes from Definition at line 1647 of file vgtl_dag.h. |
|
here every child is removed till the last base node, included the node at Definition at line 1609 of file vgtl_dag.h. |
|
Erase a parent of Definition at line 1760 of file vgtl_dag.h. |
|
construct an allocator object Reimplemented from _DG_alloc_base< _Tp, _Ctr, _Iterator, _Alloc, std::_Alloc_traits< _Tp, _Alloc >::_S_instanceless >. Definition at line 537 of file vgtl_dag.h. |
|
return a const walker to the virtual ground node. Definition at line 628 of file vgtl_dag.h. |
|
return a walker to the virtual ground node. Definition at line 618 of file vgtl_dag.h. |
|
insert a node with default data into the graph between all parents from Definition at line 907 of file vgtl_dag.h. |
|
insert a node with data Definition at line 892 of file vgtl_dag.h. |
|
insert a node with data Definition at line 853 of file vgtl_dag.h. |
|
insert a node with data Definition at line 839 of file vgtl_dag.h. |
|
insert a node with default data into the graph between all parents from Definition at line 801 of file vgtl_dag.h. |
|
insert a node with data Definition at line 786 of file vgtl_dag.h. |
|
insert node with default data into the graph between Definition at line 722 of file vgtl_dag.h. |
|
insert node with data Definition at line 708 of file vgtl_dag.h. |
|
insert a new node with default data as child of Definition at line 1178 of file vgtl_dag.h. |
|
insert a new node with data Definition at line 1172 of file vgtl_dag.h. |
|
insert one node as child of Definition at line 1158 of file vgtl_dag.h. |
|
insert a new node with default data as parent of Definition at line 1202 of file vgtl_dag.h. |
|
insert a new node with data Definition at line 1197 of file vgtl_dag.h. |
|
insert a node as parent of Definition at line 1183 of file vgtl_dag.h. |
|
insert node Definition at line 867 of file vgtl_dag.h. |
|
insert node Definition at line 814 of file vgtl_dag.h. |
|
insert node Definition at line 755 of file vgtl_dag.h. |
|
insert node Definition at line 692 of file vgtl_dag.h. |
|
in this method one DG is inserted into another DG between the parents Definition at line 921 of file vgtl_dag.h. |
|
insert a subgraph into the graph between Definition at line 733 of file vgtl_dag.h. |
|
return the first leaf of the directed graph Definition at line 645 of file vgtl_dag.h. |
|
return beyond the last leaf of the directed graph Definition at line 648 of file vgtl_dag.h. |
|
the maximum size of a DG is virtually unlimited Definition at line 679 of file vgtl_dag.h. |
|
merge two nodes, call also the merge method for the node data Definition at line 1208 of file vgtl_dag.h. |
|
assignment operator from an erased part Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >. Definition at line 1853 of file vgtl_dag.h. |
|
assignment operator from a part of an erased part Reimplemented in dgraph< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >, and dag< _Tp, _SequenceCtr, _PtrAlloc, _Alloc >. Definition at line 1845 of file vgtl_dag.h. |
|
standard assignment operator |
|
just remove one edge between Definition at line 1111 of file vgtl_dag.h. |
|
remove an edge with a particular parent and child Definition at line 1094 of file vgtl_dag.h. |
|
remove one egde and don't reconnect the node to sky/ground Definition at line 1098 of file vgtl_dag.h. |
|
change the edge from Definition at line 1023 of file vgtl_dag.h. |
|
change the edge from Definition at line 1060 of file vgtl_dag.h. |
|
return the first root of the directed graph Definition at line 638 of file vgtl_dag.h. |
|
return beyond the last root of the directed graph Definition at line 641 of file vgtl_dag.h. |
|
returns the size of the DG (number of nodes) Definition at line 672 of file vgtl_dag.h. |
|
return a const walker to the virtual sky node. Definition at line 633 of file vgtl_dag.h. |
|
return a walker to the virtual sky node. Definition at line 623 of file vgtl_dag.h. |
|
sort all child edges according to Definition at line 1147 of file vgtl_dag.h. |
|
sort the child edges in the range [first,last) according to Definition at line 1135 of file vgtl_dag.h. |
|
sort all parent edges according to Definition at line 1153 of file vgtl_dag.h. |
|
sort the parent edges in the range [first,last) according to Definition at line 1141 of file vgtl_dag.h. |
|
swap two DGs Definition at line 682 of file vgtl_dag.h. |
|
standard comparison operator |
|
the virtual ground node (below all roots) Definition at line 206 of file vgtl_dagbase.h. |
|
internal counter for various algorithms Definition at line 210 of file vgtl_dagbase.h. |
|
the virtual sky node (above all leaves) Definition at line 208 of file vgtl_dagbase.h. |