Online Topological Ordering by PK Algorithm. More...

#include <ytOtoPk.h>

Public Member Functions
ytOtoPK *	ytOtoPK_new (int size)
	Generates a new ytOtoPK instance for online topological ordering.

ytOtoPK *	ytOtoPK_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. More...

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. More...

int	ytOtoPK_checkCyclic (ytOtoPK this, int x, int y, const ytPCGraph g)
	Checkes if the specified edge makes the graph cyclic. More...

int	ytOtoPK_checkCyclicReorder (ytOtoPK this, int x, int y, const ytPCGraph g)
	Checkes if the specified edge makes the graph cyclic. More...

void	ytOtoPK_setOrder (const ytOtoPK this, int ord)
	Set the topological order.

Public Attributes
int	size

int *	ord

int *	visited

ytOtoPK_sort_t *	Rf

int	Rfp

ytOtoPK_sort_t *	Rb

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

this	pointer to the ytOtoPK instance.
x
y
g	pointer 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:

math/ytOtoPK.h
math/ytOtoPK.c