Implementation of graphs. More...

#include "type_abr.h"
#include "type_basic.h"
#include "type_binheap.h"
#include "type_dequeue.h"
#include "type_partitions.h"
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

Classes
struct	graph
	Type used to represent a directed unlabeled graph. More...

struct	lgraph
	Type used to represent a directed labeled graph. More...

struct	dgraph
	Type used to represent a complete deterministic directed labeled graph. More...

Enumerations
enum	graph_stype { DFS , BFS }
	Names for the two available algorithms for searches.

Functions
graph *	create_graph_noedges (uint)
	Creates a directed unlabeled graph without edges.

graph *	create_graph_selfloops (uint)
	Creates a directed unlabeled graph whose only edges are self-loops.

void	delete_graph (graph *)
	Releases a directed unlabeled graph.

graph *	copy_graph (graph *g)
	Makes a copy of a directed graph.

lgraph *	create_lgraph_noedges (uint, uint)
	Creates a directed graph without edges.

void	delete_lgraph (lgraph *)
	Releases a directed graph.

lgraph *	copy_lgraph (lgraph *g)
	Makes a copy of a labeled graph.

dgraph *	create_dgraph_noedges (uint, uint)
	Creates a complete deterministic directed graph without edges.

void	delete_dgraph (dgraph *)
	Release of a complete deterministic directed graph.

dgraph *	copy_dgraph (dgraph *g)
	Makes a copy of a complete deterministic directed graph.

int	graph_nb_edges (graph *)
	Computes the number of edges in a directed unlabeled graph.

int	lgraph_nb_edges (lgraph *)
	Computes the number of edges in a directed labeled graph.

int	dgraph_nb_edges (dgraph *)
	Computes the number of edges in a complete deterministic directed labeled graph.

dgraph *	dgraph_direct_product (dgraph g1, dgraph g2)
	Computes the direct product of two deterministic directed labeled graphs.

graph *	graph_mirror (graph *)
	Computes the mirror of a directed unlabeled graph.

lgraph *	lgraph_mirror (lgraph *)
	Computes the mirror of a directed labeled graph.

lgraph *	dgraph_mirror (dgraph *)
	Computes the mirror of a complete deterministic directed labeled graph.

void	graph_search_update (graph_stype, graph , dequeue , bool *)
	Searches in an unlabeled graph. A set of already visited vertices is taken as input. This set is updated by the search.

dequeue *	graph_search (graph_stype, graph , dequeue , bool *)
	Searches in an unlabeled graph. Reachable vertices are returned inside a dequeue sorted in increasing order.

void	lgraph_search_update (graph_stype, lgraph , dequeue , bool , bool )
	Search in a labeled graph. A set of already visited vertices is taken as input. This set is updated by the search.

dequeue *	lgraph_search (graph_stype, lgraph , dequeue , bool , bool )
	Search in a labeled graph. Reachable vertices are returned inside a dequeue sorted in increasing order.

void	dgraph_search_update (graph_stype, dgraph , dequeue , bool , bool )
	Search in a desterministic complete labeled graph. A set of already visited vertices is taken as input. This set is updated by the search.

dequeue *	dgraph_search (graph_stype, dgraph , dequeue , bool , bool )
	Search in a desterministic complete labeled graph. Reachable vertices are returned inside a dequeue sorted in increasing order.

void	twin_dgraph_search_update (graph_stype, dgraph , dgraph , dequeue , bool , bool *)
	Search in two deterministic complete labeled graphs (same set of vertices, same alphabet). A set of already visited vertices is taken as input. This set is updated by the search.

dequeue *	twin_dgraph_search (graph_stype, dgraph , dgraph , dequeue , bool , bool *)
	Search in two deterministic complete labeled graphs (same set of vertices, same alphabet). Reachable vertices are returned inside a dequeue sorted in increasing order.

dgraph *	dgraph_paths (dgraph *G, uint start)
	Computes a path from a given strating vertex to all other reachable vertices in a directed unlabeled graph.

graph *	merge_graphs (uint *, uint,...)
	Disjoint merge of an arbitrary number of unlabeled graphs.

lgraph *	merge_lgraphs (uint *, uint,...)
	Disjoint merge of an arbitrary number of labeled graphs.

graph *	ldgraphs_to_graph (uint, uint, uint, uint,...)
	Merging an arbitrary number of graphs using the same set of vertices into a single unlabeled graph.

lgraph *	ldgraphs_to_lgraph (uint, uint, uint,...)
	Merging an arbitrary number of labeled graphs using the same set of vertices into a single labeled graph.

lgraph *	dgraph_to_lgraph (dgraph *)
	Conversion of a complete deterministic labeled graph into a standard labeled graph.

graph *	lgraph_to_graph (lgraph *)
	Conversion of a standard labeled graph into a unlabeled graph.

graph *	lgraph_to_graph_alpha (lgraph , bool )
	Conversion of a standard labeled graph into a unlabeled graph. Restricted version.

graph *	dgraph_to_graph (dgraph *)
	Conversion of a deterministic labeled graph into a unlabeled graph.

graph *	dgraph_to_graph_alpha (dgraph , bool )
	Conversion of a deterministic labeled graph into a unlabeled graph. Restricted version.

dequeue *	lgraph_reachable (lgraph , dequeue , uint)
	Given a labeled graph, a list of vertices in this graph and a label, computes the list of all vertices connected to a vertex in the input list by an edge labeled by the input label.

Detailed Description

Implementation of graphs.

Contains the various types used to represent graphs and some functions that can manipulate them.

Function Documentation

◆ copy_dgraph()

dgraph * copy_dgraph ( dgraph * g )

Makes a copy of a complete deterministic directed graph.

Returns: The copy.

Parameters

g	The graph.

◆ copy_graph()

graph * copy_graph ( graph * g )

Makes a copy of a directed graph.

Returns: The copy.

Parameters

g	The graph.

◆ copy_lgraph()

lgraph * copy_lgraph ( lgraph * g )

Makes a copy of a labeled graph.

Returns: The copy.

Parameters

g	The graph.

◆ create_dgraph_noedges()

dgraph * create_dgraph_noedges	(	uint	size_graph,
		uint	size_alpha )

Creates a complete deterministic directed graph without edges.

Returns: The created graph.

Parameters

size_graph	Number of vertices.
size_alpha	Number of labels.

◆ create_graph_noedges()

graph * create_graph_noedges ( uint size )

Creates a directed unlabeled graph without edges.

Returns: The created graph.

Parameters

size	Number of vertices.

◆ create_graph_selfloops()

graph * create_graph_selfloops ( uint )

Creates a directed unlabeled graph whose only edges are self-loops.

Returns: The created graph.

◆ create_lgraph_noedges()

lgraph * create_lgraph_noedges	(	uint	size_graph,
		uint	size_alpha )

Creates a directed graph without edges.

Returns: The created graph.

Parameters

size_graph	Number of vertices.
size_alpha	Number of labels.

◆ dgraph_direct_product()

dgraph * dgraph_direct_product	(	dgraph *	g1,
		dgraph *	g2 )

Computes the direct product of two deterministic directed labeled graphs.

Remarks: The vertex (q1,q2) is is encoded as the integer q1 * g2->size_graph + q2 in the resulting graph.; The graphs need not be complete. A undefined edge is represented by the destination value UINT_MAX in both the input graphs and the resulting graph.

Attention: The two graphs must have the same alphabet size.

Returns: The resulting graph.

Parameters

g1	The first graph.
g2	The second graph.

◆ dgraph_mirror()

lgraph * dgraph_mirror ( dgraph * G )

Computes the mirror of a complete deterministic directed labeled graph.

Returns: The mirror of the graph (an lgraph since the mirror need not be deterministic)

◆ dgraph_nb_edges()

int dgraph_nb_edges ( dgraph * G )

Computes the number of edges in a complete deterministic directed labeled graph.

Returns: The number of edges in the graph.

◆ dgraph_paths()

dgraph * dgraph_paths	(	dgraph *	G,
		uint	start )

Computes a path from a given strating vertex to all other reachable vertices in a directed unlabeled graph.

Remarks: The paths are computed using a breadth-first search.; It is allowed for the input graph to have non-defined edges (in these cases the value UINT_MAX is used to represent the non-defined edges).

Returns: A graph containing the back edges of the paths.

Parameters

G	The graph.
start	The starting vertex.

◆ dgraph_search()

dequeue * dgraph_search	(	graph_stype	T,
		dgraph *	G,
		dequeue *	ini,
		bool *	alph,
		bool *	rest )

Search in a desterministic complete labeled graph. Reachable vertices are returned inside a dequeue sorted in increasing order.

Attention: The starting set is emptied by the function (it serves as a stack or a queue).

Remarks: Two arrays of Booleans are taken as input. The first one is indexed by the labels. It represents a set of labels which restricts the edges that can be used to those labeled by a label in this set. The second array is indexed by the vertices. It represents a subset of these vertices which is used to restrict the list of reachable vertices to those in the given set. In both cases, if no restriction is needed, a NULL pointer should be given as input.

Returns: The list of reachable vertices sorted in increasing order.

Parameters

T	The type of search that has to be used.
G	The graph.
ini	The starting set of vertices.
alph	An array indexed by the labels. Used to restrict the edges that can be used.
rest	An array indexed by the vertices. Used to restrict the list of reachable vertices.

◆ dgraph_search_update()

void dgraph_search_update	(	graph_stype	T,
		dgraph *	G,
		dequeue *	ini,
		bool *	alph,
		bool *	visited )

Search in a desterministic complete labeled graph. A set of already visited vertices is taken as input. This set is updated by the search.

Remarks: An additional array of Booleans is taken as input. It is indexed by the labels and represents a set of labels. It restricts the edges that can be used to those labeled by a label in this set. If no restriction is needed, a NULL pointer should be given as input.

Attention: The starting set is emptied by the function (it serves as a stack or a queue).

Parameters

T	The type of search that has to be used.
G	The graph.
ini	The starting set of vertices.
alph	An array indexed by the labels. Used to restrict the edges that can be used.
visited	A set of already visited vertices. It is updated by the fucntion.

◆ dgraph_to_graph()

graph * dgraph_to_graph ( dgraph * dg )

Conversion of a deterministic labeled graph into a unlabeled graph.

Returns: The unlabeled graph.

Parameters

dg	The labeled graph.

◆ dgraph_to_graph_alpha()

graph * dgraph_to_graph_alpha	(	dgraph *	dg,
		bool *	alph )

Conversion of a deterministic labeled graph into a unlabeled graph. Restricted version.

Remarks: An array of Booleans is taken as input. It is indexed by the labels and represents a sub-alphabet of the graph. It restricts the edges that can be used to those labeled by a label in this set. If a NULL pointer is given, all edges are used.

Returns: The unlabeled graph.

Parameters

dg	The labeled graph.
alph	An array indexed by the labels. Used to restrict the edges that can be used.

◆ dgraph_to_lgraph()

lgraph * dgraph_to_lgraph ( dgraph * DG )

Conversion of a complete deterministic labeled graph into a standard labeled graph.

Returns: The labeled graph.

Parameters

DG	The complete deterministic labeled graph.

◆ graph_mirror()

graph * graph_mirror ( graph * G )

Computes the mirror of a directed unlabeled graph.

Returns: The mirror of the graph.

◆ graph_nb_edges()

int graph_nb_edges ( graph * G )

Computes the number of edges in a directed unlabeled graph.

Returns: The number of edges in the graph.

◆ graph_search()

dequeue * graph_search	(	graph_stype	T,
		graph *	G,
		dequeue *	ini,
		bool *	rest )

Searches in an unlabeled graph. Reachable vertices are returned inside a dequeue sorted in increasing order.

Attention: The starting set is emptied by the function (it serves as a stack or a queue).

Remarks: An array of Booleans is taken as input. It is indexed by the vertices in the graph and represents a subset of these vertices. It is used to restrict the list of reachable vertices to those in the given set. If no restriction is needed, a NULL pointer should be given as input.

Returns: The list of reachable vertices sorted in increasing order.

Parameters

T	The type of search that has to be used.
G	The graph.
ini	The starting set of vertices.
rest	An array indexed by the vertices. Used to restrict the list of reachable vertices.

◆ graph_search_update()

void graph_search_update	(	graph_stype	T,
		graph *	G,
		dequeue *	ini,
		bool *	visited )

Searches in an unlabeled graph. A set of already visited vertices is taken as input. This set is updated by the search.

Attention: The starting set is emptied by the function (it serves as a stack or a queue).

Parameters

T	The type of search that has to be used.
G	The graph.
ini	The starting set of vertices.
visited	A set of already visited vertices. It is updated by the fucntion.

◆ ldgraphs_to_graph()

graph * ldgraphs_to_graph	(	uint	ng,
		uint	nlg,
		uint	ndg,
		uint	n,
			... )

Merging an arbitrary number of graphs using the same set of vertices into a single unlabeled graph.

Remarks: It is possible to merge arbitrary kinds of graphs. The unlabeled inputs must be given first, then the labeled one, then the complete deterministic labeled ones.

Attention: All graphs must have the same size.

Returns: The resulting unlabeled graph.

Parameters

ng	Number of input unlabeled graphs.
nlg	Number of input labeled graphs.
ndg	Number of input complete deterministic labeled graphs.
n	Total number of input graphs (sum of the three).
...	The graphs.

◆ ldgraphs_to_lgraph()

lgraph * ldgraphs_to_lgraph	(	uint	nlg,
		uint	ndg,
		uint	n,
			... )

Merging an arbitrary number of labeled graphs using the same set of vertices into a single labeled graph.

Remarks: It is possible to merge standard labeled graphs with complete deterministic labeled graphs. The former must be given first, then the latter.

Attention: All graphs must have the same size.

Returns: The resulting labeled graph.

Parameters

nlg	Number of input labeled graphs.
ndg	Number of input complete deterministic labeled graphs.
n	Total number of input graphs (sum of the two).
...	The graphs.

◆ lgraph_mirror()

lgraph * lgraph_mirror ( lgraph * G )

Computes the mirror of a directed labeled graph.

Returns: The mirror of the graph.

◆ lgraph_nb_edges()

int lgraph_nb_edges ( lgraph * G )

Computes the number of edges in a directed labeled graph.

Returns: The number of edges in the graph.

◆ lgraph_reachable()

dequeue * lgraph_reachable	(	lgraph *	G,
		dequeue *	start,
		uint	a )

Given a labeled graph, a list of vertices in this graph and a label, computes the list of all vertices connected to a vertex in the input list by an edge labeled by the input label.

Returns: The list of all connected vertices sorted in increasing order.

Parameters

G	The graph.
start	The input list of vertices.
a	The label.

◆ lgraph_search()

dequeue * lgraph_search	(	graph_stype	T,
		lgraph *	G,
		dequeue *	ini,
		bool *	alph,
		bool *	rest )

Search in a labeled graph. Reachable vertices are returned inside a dequeue sorted in increasing order.

Attention: The starting set is emptied by the function (it serves as a stack or a queue).

Remarks: Two arrays of Booleans are taken as input. The first one is indexed by the labels. It represents a set of labels which restricts the edges that can be used to those labeled by a label in this set. The second array is indexed by the vertices. It represents a subset of these vertices which is used to restrict the list of reachable vertices to those in the given set. In both cases, if no restriction is needed, a NULL pointer should be given as input.

Returns: The list of reachable vertices sorted in increasing order.

Parameters

T	The type of search that has to be used.
G	The graph.
ini	The starting set of vertices.
alph	An array indexed by the labels. Used to restrict the edges that can be used.
rest	An array indexed by the vertices. Used to restrict the list of reachable vertices.

◆ lgraph_search_update()

void lgraph_search_update	(	graph_stype	T,
		lgraph *	G,
		dequeue *	ini,
		bool *	alph,
		bool *	visited )

Search in a labeled graph. A set of already visited vertices is taken as input. This set is updated by the search.

Remarks: An additional array of Booleans is taken as input. It is indexed by the labels and represents a set of labels. It restricts the edges that can be used to those labeled by a label in this set. If no restriction is needed, a NULL pointer should be given as input.

Attention: The starting set is emptied by the function (it serves as a stack or a queue).

Parameters

T	The type of search that has to be used.
G	The graph.
ini	The starting set of vertices.
alph	An array indexed by the labels. Used to restrict the edges that can be used.
visited	A set of already visited vertices. It is updated by the fucntion.

◆ lgraph_to_graph()

graph * lgraph_to_graph ( lgraph * lg )

Conversion of a standard labeled graph into a unlabeled graph.

Returns: The unlabeled graph.

Parameters

lg	The labeled graph.

◆ lgraph_to_graph_alpha()

graph * lgraph_to_graph_alpha	(	lgraph *	lg,
		bool *	alph )

Conversion of a standard labeled graph into a unlabeled graph. Restricted version.

Remarks: An array of Booleans is taken as input. It is indexed by the labels and represents a sub-alphabet of the graph. It restricts the edges that can be used to those labeled by a label in this set. If a NULL pointer is given, all edges are used.

Returns: The unlabeled graph.

Parameters

lg	The labeled graph.
alph	An array indexed by the labels. Used to restrict the edges that can be used.

◆ merge_graphs()

graph * merge_graphs	(	uint *	lag,
		uint	n,
			... )

Disjoint merge of an arbitrary number of unlabeled graphs.

Remarks: If one of the input graphs is NULL, it is not taken into account. If all of the input graphs are NULL, the function returns NULL.

Returns: The resulting unlabeled graph.

Parameters

lag	An array indexed by the input graphs. It is used to return the index of the first vertex of each graph in the merged graph.
n	The number of graphs given as input.
...	The graphs.

◆ merge_lgraphs()

lgraph * merge_lgraphs	(	uint *	lag,
		uint	n,
			... )

Disjoint merge of an arbitrary number of labeled graphs.

Remarks: If one of the input graphs is NULL, it is not taken into account. If all of the input graphs are NULL, the function returns NULL.

Attention: The input graphs must have the same number of labels.

Returns: The resulting labeled graph.

Parameters

lag	An array indexed by the input graphs. It is used to return the index of the first vertex of each graph in the merged graph.
n	The number of graphs given as input.
...	The graphs.

◆ twin_dgraph_search()

dequeue * twin_dgraph_search	(	graph_stype	T,
		dgraph *	G1,
		dgraph *	G2,
		dequeue *	ini,
		bool *	alph,
		bool *	rest )

Search in two deterministic complete labeled graphs (same set of vertices, same alphabet). Reachable vertices are returned inside a dequeue sorted in increasing order.

Attention: The starting set is emptied by the function (it serves as a stack or a queue).

Remarks: Two arrays of Booleans are taken as input. The first one is indexed by the labels. It represents a set of labels which restricts the edges that can be used to those labeled by a label in this set. The second array is indexed by the vertices. It represents a subset of these vertices which is used to restrict the list of reachable vertices to those in the given set. In both cases, if no restriction is needed, a NULL pointer should be given as input.

Returns: The list of reachable vertices sorted in increasing order.

Parameters

T	The type of search that has to be used.
G1	The first graph.
G2	The second graph.
ini	The starting set of vertices.
alph	An array indexed by the labels. Used to restrict the edges that can be used.
rest	An array indexed by the vertices. Used to restrict the list of reachable vertices.

◆ twin_dgraph_search_update()

void twin_dgraph_search_update	(	graph_stype	T,
		dgraph *	G1,
		dgraph *	G2,
		dequeue *	ini,
		bool *	alph,
		bool *	visited )

Search in two deterministic complete labeled graphs (same set of vertices, same alphabet). A set of already visited vertices is taken as input. This set is updated by the search.

Remarks: An additional array of Booleans is taken as input. It is indexed by the labels and represents a set of labels. It restricts the edges that can be used to those labeled by a label in this set. If no restriction is needed, a NULL pointer should be given as input.

Attention: The starting set is emptied by the function (it serves as a stack or a queue).

Parameters

T	The type of search that has to be used.
G1	The first graph.
G2	The second graph.
ini	The starting set of vertices.
alph	An array indexed by the labels. Used to restrict the edges that can be used.
visited	A set of already visited vertices. It is updated by the fucntion.

Classes

Enumerations

Functions

Detailed Description

Function Documentation

◆ copy_dgraph()

◆ copy_graph()

◆ copy_lgraph()

◆ create_dgraph_noedges()

◆ create_graph_noedges()

◆ create_graph_selfloops()

◆ create_lgraph_noedges()

◆ dgraph_direct_product()

◆ dgraph_mirror()

◆ dgraph_nb_edges()

◆ dgraph_paths()

◆ dgraph_search()

◆ dgraph_search_update()

◆ dgraph_to_graph()

◆ dgraph_to_graph_alpha()

◆ dgraph_to_lgraph()

◆ graph_mirror()

◆ graph_nb_edges()

◆ graph_search()

◆ graph_search_update()

◆ ldgraphs_to_graph()

◆ ldgraphs_to_lgraph()

◆ lgraph_mirror()

◆ lgraph_nb_edges()

◆ lgraph_reachable()

◆ lgraph_search()

◆ lgraph_search_update()

◆ lgraph_to_graph()

◆ lgraph_to_graph_alpha()

◆ merge_graphs()

◆ merge_lgraphs()

◆ twin_dgraph_search()

◆ twin_dgraph_search_update()