ytOtoPK Class Reference

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