MySQL 9.0.0
Source Code Documentation
|
A fast online cycle finder, based on [Pea03]. More...
#include <online_cycle_finder.h>
Public Member Functions | |
OnlineCycleFinder (MEM_ROOT *mem_root, int num_vertices) | |
bool | EdgeWouldCreateCycle (int a_idx, int b_idx) |
bool | AddEdge (int a_idx, int b_idx) |
void | DeleteEdge (int a_idx, int b_idx) |
Bounds_checked_array< int > | order () const |
Private Member Functions | |
bool | DepthFirstSearch (int node_idx, int upper_bound, int node_idx_to_avoid) |
void | MoveAllMarked (int start_pos, int new_pos) |
void | Allocate (int node_idx, int index_in_order) |
Private Attributes | |
Bounds_checked_array< int > | m_order |
Bounds_checked_array< int > | m_position_of_node |
Bounds_checked_array< bool > | m_visited |
Mem_root_array< int > | m_to_shift |
mem_root_unordered_multimap< int, int > | m_edges |
A fast online cycle finder, based on [Pea03].
It keeps a DAG in memory, built up incrementally, and is able to reject adding edges that would create cycles (or, equivalently, test if adding an edge would create a cycle). The amortized cost of checking ϴ(E) insertions is O(V).
The basic working of the algorithm is to keep a list of all vertices, topologically sorted given the order so far. When inserting a new edge, we can quickly identify any vertices that would need to be moved in the topological sort (they are the ones stored between the two endpoints), run a DFS, and see if moving them would cause a contradiction (and thus, a cycle). See EdgeWouldCreateCycle() or the paper for more details.
Note that confusingly enough, when used from the graph simplification algorithm, the vertices in this graph represent hyperedges (joins) in the join hypergraph, not the vertices (tables) themselves. The edges in this graph are happens-before relations between those joins.
[Pea03] Pearce et al: “Online Cycle Detection and Difference Propagation for Pointer Analysis”, section 3.2.
OnlineCycleFinder::OnlineCycleFinder | ( | MEM_ROOT * | mem_root, |
int | num_vertices | ||
) |
bool OnlineCycleFinder::AddEdge | ( | int | a_idx, |
int | b_idx | ||
) |
|
inlineprivate |
void OnlineCycleFinder::DeleteEdge | ( | int | a_idx, |
int | b_idx | ||
) |
|
private |
bool OnlineCycleFinder::EdgeWouldCreateCycle | ( | int | a_idx, |
int | b_idx | ||
) |
|
private |
|
inline |
|
private |
|
private |
|
private |
|
private |
|
private |