INGOR
Loading...
Searching...
No Matches
Public Member Functions | Public Attributes | List of all members
ytOtoPK Class Reference

Online Topological Ordering by PK Algorithm. More...

#include <ytOtoPk.h>

Public Member Functions

ytOtoPKytOtoPK_new (int size)
 Generates a new ytOtoPK instance for online topological ordering.
 
ytOtoPKytOtoPK_newPCGraph (const ytPCGraph *g)
 Generates a new ytOtoPK instance with a ytPCGraph.
 
int ytOtoPK_init (ytOtoPK *this, const ytPCGraph *g)
 Reordering by the specified graph.
 
void ytOtoPK_delete (void *this)
 Deletes the ytOtoPK instance.
 
int ytOtoPK_addEdge (ytOtoPK *this, int x, int y, ytPCGraph *g)
 Adds an edge with checking if it makes the graph cyclic.
 
int ytOtoPK_checkCyclic (ytOtoPK *this, int x, int y, const ytPCGraph *g)
 Checkes if the specified edge makes the graph cyclic.
 
int ytOtoPK_checkCyclicReorder (ytOtoPK *this, int x, int y, const ytPCGraph *g)
 Checkes if the specified edge makes the graph cyclic.
 
void ytOtoPK_setOrder (const ytOtoPK *this, int *ord)
 Set the topological order.
 

Public Attributes

int size
 
int * ord
 
int * visited
 
ytOtoPK_sort_tRf
 
int Rfp
 
ytOtoPK_sort_tRb
 
int Rbp
 

Detailed Description

Online Topological Ordering by PK Algorithm.

The algorithm is written in the paper: D. J. Pearch and P. H. J. Kelly (2006). A dynamic topological sort algorithm for directed acyclic graphs. ACM Journal of Experimental Algorithms, 11, 1-24.

See also
ytPCGraph

Member Function Documentation

◆ ytOtoPK_addEdge()

int ytOtoPK_addEdge ( ytOtoPK this,
int  x,
int  y,
ytPCGraph g 
)

Adds an edge with checking if it makes the graph cyclic.

Parameters
thispointer to the ytOtoPK instance.
x
y
gpointer to the SGN_PCGraph instance.
Returns
0 if successful, or 1 if a cycle becomes with x - y edge.

◆ ytOtoPK_checkCyclic()

int ytOtoPK_checkCyclic ( ytOtoPK this,
int  x,
int  y,
const ytPCGraph g 
)

Checkes if the specified edge makes the graph cyclic.

This does not affect the current topological order.

Returns
1 if the edges makes the graph cyclic, or 0 otherwise.

◆ ytOtoPK_checkCyclicReorder()

int ytOtoPK_checkCyclicReorder ( ytOtoPK this,
int  x,
int  y,
const ytPCGraph g 
)

Checkes if the specified edge makes the graph cyclic.

This affects (changes) the current topological order.

Returns
1 if the edges makes the graph cyclic, or 0 otherwise.

◆ ytOtoPK_init()

int ytOtoPK_init ( ytOtoPK this,
const ytPCGraph g 
)

Reordering by the specified graph.

Returns
0 on successful, or 1 if the graph is DAG and not able to order.

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