ytDLGraph Struct Reference

Graph structure for efficient parents and children handling. More...

#include <ytDLGraph.h>

Public Member Functions
void	ytDLGraph_delete (void *this)
	Deletes the \ytDLGraph instance.
void	ytDLGraph_copy (const ytDLGraph *this, ytDLGraph *g)
	Copies the ytDLGraph instance to another instance.
void	ytDLGraph_copyGraph (ytDLGraph *this, const ytGraph *src)
	Copies edges to this graph.
void	ytDLGraph_resize_buff (ytDLGraph *this, size_t size)
	Resizes the edge buffer size.
int	ytDLGraph_numNodes (const ytDLGraph *this)
	Returns the number of nodes.
size_t	ytDLGraph_numEdges (const ytDLGraph *this)
	Returns the number of edges.
int	ytDLGraph_checkEdge (const ytDLGraph *this, int u, int v)
	Checks if the specified edge exists.
size_t	ytDLGraph_addEdge (ytDLGraph *this, int u, int v)
	Adds a new edge from u to v.
size_t	ytDLGraph_check_edge_index (ytDLGraph *this, int u, int v)
	Checks if the specified edge exists.
size_t	ytDLGraph_check_edge_id (ytDLGraph *this, int u, int v)
	Checks if the specified edge exists.
void	ytDLGraph_get_edge (ytDLGraph *this, size_t id, int *u, int *v)
	Obtains the start and end nodes of the specified edge.
void	ytDLGraph_get_edge_index (const ytDLGraph *this, size_t index, int *u, int *v)
	Obtains the start and end nodes of the specified edge.
void	ytDLGraph_clear (ytDLGraph *this)
	Removes all the edges in the graph.
size_t	ytDLGraph_first_parent_id (ytDLGraph *this, int v)
	Returns the edge ID of the first parent of node v.
size_t	ytDLGraph_first_child_id (ytDLGraph *this, int v)
	Return the edge ID of the first child of node v.
size_t	ytDLGraph_next_parent_id (ytDLGraph *this, size_t id)
	Returns the edge ID of the next parent.
size_t	ytDLGraph_next_child_id (ytDLGraph *this, size_t id)
	Returns the edge ID of the next child.
size_t	ytDLGraph_parent_next (ytDLGraph *this, size_t id, int *pa)
	Returns the parent node and the edge ID of the next parent.
size_t	ytDLGraph_child_next (ytDLGraph *this, size_t id, int *ch)
	Returns the child node and the edge ID of the next child.
int	ytDLGraph_get_parent (ytDLGraph *this, size_t id)
	Returns the parent (initial) node corresponding to the given edge ID.
int	ytDLGraph_get_child (ytDLGraph *this, size_t id)
	Returns the child (terminate) node corresponding to the given edge ID.
void	ytDLGraph_print_all_parents (ytDLGraph *this, FILE *fp)
	Prints lists of parents for all nodes.
size_t	ytDLGraph_first_edge (ytDLGraph *this)
	Returns the edge ID for the first edge.
size_t	ytDLGraph_next_edge (ytDLGraph *this, size_t id)
	Returns the next valid ID of the given edge ID.
int	ytDLGraph_check_cyclic (ytDLGraph *this, int u, int v)
	Checks if the graph becomes cyclic by adding the edge.
size_t	ytDLGraph_num_parents (ytDLGraph *this, int v)
	Return the number of parents of the node.
size_t	ytDLGraph_degree (ytDLGraph *this, int v)
	Returns the degree of the node.
void	ytDLGraph_remove_edge_id (ytDLGraph *this, size_t id)
	Removes an edge specified by its ID.
void	ytDLGraph_remove_edge (ytDLGraph *this, int u, int v)
	Removes an edge specified by its starting and ending node.
size_t	ytDLGraph_parents (ytDLGraph *this, int v, ytIntArray *ar)
	Gets the list of parents in ytIntArray.
void	ytDLGraph_fill (ytDLGraph *this)
	Fills the empty slot in the buffer.
ytObject *	ytDLGraph_obj (ytDLGraph *this)
	Returns the ytObject of this instance.
#define	ytDLGraph_NULL
	Value representing NULL.

Detailed Description

Graph structure for efficient parents and children handling.

ytDLGraph is similar to ytPGraph except that this maintains the list of edges both for parents and children. ytPGraph maintains only the list of parents. Therefore, if users often need to access both children and parents of certain nodes, then this is suitable for that purposes.

See also

ytPGraph, ytGraph

Member Function Documentation

ytDLGraph_addEdge()

size_t ytDLGraph_addEdge	(	ytDLGraph *	this,
		int	u,
		int	v
	)

Adds a new edge from u to v.

If the buffer size is not enough to add a new edge, this automatically extends its size.

This does not check if the edge already exists in the graph.

This is a constant time operation.

Parameters

this	pointer to the ytDLGraph instance.
u	start node of the edge to add.
v	end node of the edge to add.

Returns

edge ID of the newly added one.

ytDLGraph_check_cyclic()

int ytDLGraph_check_cyclic	(	ytDLGraph *	this,
		int	u,
		int	v
	)

Checks if the graph becomes cyclic by adding the edge.

This check whether the graph becomes cyclic if u - v edge is added.

Note that this algorithm is very slow. If you want to add edges repeadedly with keeping the graph acyclic, use OTO_PK with the ytDLGraph instance.

Parameters

this	pointer to the Graph instance.
u	index of the starting node of the edge
v	index of the ending node of the edge

Returns

1 if the graph becomes cyclic with u - v edge, or 0 otherwise.

Go to top

ytDLGraph_check_edge_id()

size_t ytDLGraph_check_edge_id	(	ytDLGraph *	this,
		int	u,
		int	v
	)

Checks if the specified edge exists.

This takes at most O(n / 2) time where n represents the number of parents or children.

This is identical to ytDLGraph_check_edge() except that this returns an edge ID (not an edge index) if found.

Parameters

this	pointer to the ytDLGraph instance.
u	start node of the edge to check
v	end node of the edge to check

Returns

ID of the edge if it exsits, or ytDLGraph_NULL otherwise.

Go to top

ytDLGraph_check_edge_index()

size_t ytDLGraph_check_edge_index	(	ytDLGraph *	this,
		int	u,
		int	v
	)

Checks if the specified edge exists.

This takes at most O(n) time where n represents the number of parents or children.

This is identical to ytDLGraph_check_edge() except that this returns an edge index (not an edge ID) if found.

Parameters

this	pointer to the ytDLGraph instance.
u	start node of the edge to check
v	end node of the edge to check

Returns

index of the edge if it exsits, or ytDLGraph_NULL otherwise.

Go to top

ytDLGraph_checkEdge()

int ytDLGraph_checkEdge	(	const ytDLGraph *	this,
		int	u,
		int	v
	)

Checks if the specified edge exists.

This takes at most O(n) time where n represents the number of parents or children.

Parameters

this	pointer to the ytDLGraph instance.
u	start node of the edge to check
v	end node of the edge to check

Returns

1 if the edge exsits, or 0 otherwise.

ytDLGraph_child_next()

size_t ytDLGraph_child_next	(	ytDLGraph *	this,
		size_t	id,
		int *	ch
	)

Returns the child node and the edge ID of the next child.

Go to top

ytDLGraph_clear()

void ytDLGraph_clear

(

ytDLGraph *

this

)

Removes all the edges in the graph.

Parameters

this	pointer to the ytDLGraph instance.

Go to top

ytDLGraph_copy()

void ytDLGraph_copy	(	const ytDLGraph *	this,
		ytDLGraph *	g
	)

Copies the ytDLGraph instance to another instance.

Go to top

ytDLGraph_copyGraph()

void ytDLGraph_copyGraph	(	ytDLGraph *	this,
		const ytGraph *	src
	)

Copies edges to this graph.

The current edges in this graph are removed, then edges in src are copied into this graph.

Parameters

this
src

See also

ytDLGraph_copy()

ytDLGraph_degree()

size_t ytDLGraph_degree	(	ytDLGraph *	this,
		int	v
	)

Returns the degree of the node.

Go to top

ytDLGraph_delete()

void ytDLGraph_delete

(

void *

this

)

Deletes the \ytDLGraph instance.

Parameters

this	pointer to the ytDLGraph instance to delete.

Go to top

ytDLGraph_fill()

void ytDLGraph_fill

(

ytDLGraph *

this

)

Fills the empty slot in the buffer.

This re-allocate the buffer so that the users can access all the edges by ytDLGraph_get_edge_index().

This is required to call ytDLGraph_get_edge_index() if ytDLGraph_remove_edge() or ytDLGraph_remove_edge_id() have been called once.

Go to top

ytDLGraph_first_child_id()

size_t ytDLGraph_first_child_id	(	ytDLGraph *	this,
		int	v
	)

Return the edge ID of the first child of node v.

Note that the returning value is not a child node, but it is an edge ID. To obtain a child node of the edge ID, use ytDLGraph_get_child().

This is convenient if you want to visit all of children of a certain node. To do this, after obtaining the first edge ID by this function, use ytDLGraph_next_child_id(), or ytDLGraph_child_next(), which returns both edge ID and the corresponding parent, iteratively until ytDLGraph_NULL is returned.

Parameters

this	pointer to the ytDLGraph instance.
v	node

Returns

edge ID for the first child of node v, or ytDLGraph_NULL if it has no children.

See also

ytDLGraph_get_child(), ytDLGraph_next_child_id(), ytDLGraph_child_next(), ytDLGraph_first_parent_id()

Go to top

ytDLGraph_first_edge()

size_t ytDLGraph_first_edge

(

ytDLGraph *

this

)

Returns the edge ID for the first edge.

Parameters

this	pointer to the ytDLGraph instance.

See also

ytDLGraph_next_edge()

Go to top

ytDLGraph_first_parent_id()

size_t ytDLGraph_first_parent_id	(	ytDLGraph *	this,
		int	v
	)

Returns the edge ID of the first parent of node v.

Note that the returning value is not a parent node, but it is an edge ID. To obtain a parent node of the edge ID, use ytDLGraph_get_parent().

This is convenient if you want to visit all of parents of a certain node. To do this, after obtaining the first edge ID by this function, use ytDLGraph_next_parent_id(), or ytDLGraph_parent_next(), which returns both edge ID and the corresponding parent, iteratively until ytDLGraph_NULL is returned.

Parameters

this	pointer to the ytDLGraph instance.
v	node

Returns

edge ID for the first parent of node v, or ytDLGraph_NULL if it has no parents.

See also

ytDLGraph_get_parent(), ytDLGraph_next_parent_id(), ytDLGraph_parent_next(), ytDLGraph_first_child_id()

Go to top

ytDLGraph_get_child()

int ytDLGraph_get_child	(	ytDLGraph *	this,
		size_t	id
	)

Returns the child (terminate) node corresponding to the given edge ID.

This returns the child (terminate) node of the edge specified by its ID id. If the invalid edge ID is given, this returns a meaningless value. To get both initial and terminate node of the edge, use ytDLGraph_get_edge().

Parameters

this	pointer to the ytDLGraph instance.
id	edge ID.

Returns

terminate node of the specified edge.

Go to top

ytDLGraph_get_edge()

void ytDLGraph_get_edge	(	ytDLGraph *	this,
		size_t	id,
		int *	u,
		int *	v
	)

Obtains the start and end nodes of the specified edge.

This returns u' and v' of (u', v' )-edge, specified by its ID id, into the variables given by pointer parameters u and v.

Note that argument id is not an index of edges. To visit all the edges in the graph, use ytDLGraph_get_edge_index(). The first edge does not have an ID == 0.

Parameters

this	pointer to the ytDLGraph instance.
id	ID of the edge to obtain
u	initial node of the specified edge will be set.
v	terminal node of the specified edge will be set.

See also

ytDLGraph_get_edge_index().

Go to top

ytDLGraph_get_edge_index()

void ytDLGraph_get_edge_index	(	const ytDLGraph *	this,
		size_t	index,
		int *	u,
		int *	v
	)

Obtains the start and end nodes of the specified edge.

This returns u' and v' of (u', v' )-edge, specified by its index index, into the variables given by pointer parameters u and v.

The idexes of edges start from 0 and end at n - 1 where n is the number of edges.

Please do not confuse with ytDLGraph_get_edge() which returns an edge specified by its ID.

Parameters

this	pointer to the ytDLGraph instance.
index	index of the edge to obtain.
u	initial node of the specified edge will be set.
v	terminal node of the specified edge will be set.

See also

ytDLGraph_get_edge().

Go to top

ytDLGraph_get_parent()

int ytDLGraph_get_parent	(	ytDLGraph *	this,
		size_t	id
	)

Returns the parent (initial) node corresponding to the given edge ID.

This returns the parent (initial) node of the edge specified by its ID id. If the invalid edge ID is given, this returns a meaningless value. To get both initial and terminate node of the edge, use ytDLGraph_get_edge().

Parameters

this	pointer to the ytDLGraph instance.
id	edge ID.

Returns

initial node of the specified edge.

Go to top

ytDLGraph_next_child_id()

size_t ytDLGraph_next_child_id	(	ytDLGraph *	this,
		size_t	id
	)

Returns the edge ID of the next child.

The second parameter \id needs to be a value returned by ytDLGraph_first_child_id() or ytDLGraph_child_next().

Go to top

ytDLGraph_next_edge()

size_t ytDLGraph_next_edge	(	ytDLGraph *	this,
		size_t	id
	)

Returns the next valid ID of the given edge ID.

Go to top

ytDLGraph_next_parent_id()

size_t ytDLGraph_next_parent_id	(	ytDLGraph *	this,
		size_t	id
	)

Returns the edge ID of the next parent.

The second parameter \id needs to be a value returned by ytDLGraph_first_parent_id() or ytDLGraph_parent_next().

Go to top

ytDLGraph_num_parents()

size_t ytDLGraph_num_parents	(	ytDLGraph *	this,
		int	v
	)

Return the number of parents of the node.

Go to top

ytDLGraph_numEdges()

size_t ytDLGraph_numEdges

(

const ytDLGraph *

this

)

Returns the number of edges.

Parameters

this	pointer to the ytDLGraph instance.

Returns

The number of edges in the graph.

ytDLGraph_numNodes()

int ytDLGraph_numNodes

(

const ytDLGraph *

this

)

Returns the number of nodes.

Parameters

this	pointer to the ytDLGraph instance.

Returns

The number of nodes in the graph.

ytDLGraph_obj()

ytObject * ytDLGraph_obj

(

ytDLGraph *

this

)

Returns the ytObject of this instance.

Parameters

this	pointer to the ytDLGraph instance.

Returns

pointer to the ytObject of this instance.

ytDLGraph_parent_next()

size_t ytDLGraph_parent_next	(	ytDLGraph *	this,
		size_t	id,
		int *	pa
	)

Returns the parent node and the edge ID of the next parent.

Go to top

ytDLGraph_parents()

size_t ytDLGraph_parents	(	ytDLGraph *	this,
		int	v,
		ytIntArray *	ar
	)

Gets the list of parents in ytIntArray.

Returns

the number of parents of v.

Go to top

ytDLGraph_print_all_parents()

void ytDLGraph_print_all_parents	(	ytDLGraph *	this,
		FILE *	fp
	)

Prints lists of parents for all nodes.

Parameters

this	pointer to the ytDLGraph instance.
fp	FILE pointer to which lists of parents are printed.

Go to top

ytDLGraph_remove_edge()

void ytDLGraph_remove_edge	(	ytDLGraph *	this,
		int	u,
		int	v
	)

Removes an edge specified by its starting and ending node.

Go to top

ytDLGraph_remove_edge_id()

void ytDLGraph_remove_edge_id	(	ytDLGraph *	this,
		size_t	id
	)

Removes an edge specified by its ID.

Go to top

ytDLGraph_resize_buff()

void ytDLGraph_resize_buff	(	ytDLGraph *	this,
		size_t	size
	)

Resizes the edge buffer size.

If size is smaller than the current buffer size, it is regarded as the current buffer size.

The current implementation will abort if it fails to resize the memory, especially when enlarging it.

Parameters

this	pointer to the ytDLGraph instance.
size	new buffer size.

Go to top

---

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

• math/ytDLGraph.h
• math/ytDLGraph.c