Typedefs
typedef piojo_id_t	piojo_graph_vid_t

typedef float	piojo_graph_weight_t

typedef bool(*	piojo_graph_visit_cb )(piojo_graph_vid_t v, const piojo_graph_t *graph)

typedef piojo_graph_weight_t(*	piojo_graph_cost_cb )(piojo_graph_vid_t from, piojo_graph_vid_t to, const piojo_graph_t *graph)

Enumerations
enum	piojo_graph_dir_t { PIOJO_GRAPH_DIR_TRUE, PIOJO_GRAPH_DIR_FALSE }

Functions
piojo_graph_t *	piojo_graph_alloc (piojo_graph_dir_t directed)

piojo_graph_t *	piojo_graph_alloc_cb (piojo_graph_dir_t directed, piojo_alloc_if allocator)

piojo_graph_t *	piojo_graph_copy (const piojo_graph_t *graph)

void	piojo_graph_free (const piojo_graph_t *graph)

void	piojo_graph_clear (piojo_graph_t *graph)

void	piojo_graph_set_gvalue (piojo_opaque_t value, piojo_graph_t *graph)

piojo_opaque_t	piojo_graph_gvalue (const piojo_graph_t *graph)

bool	piojo_graph_insert (piojo_graph_vid_t vertex, piojo_graph_t *graph)

bool	piojo_graph_delete (piojo_graph_vid_t vertex, piojo_graph_t *graph)

void	piojo_graph_set_vvalue (piojo_opaque_t value, piojo_graph_vid_t vertex, piojo_graph_t *graph)

piojo_opaque_t	piojo_graph_vvalue (piojo_graph_vid_t vertex, const piojo_graph_t *graph)

void	piojo_graph_link (piojo_graph_weight_t weight, piojo_graph_vid_t from, piojo_graph_vid_t to, piojo_graph_t *graph)

piojo_graph_weight_t *	piojo_graph_linked (piojo_graph_vid_t from, piojo_graph_vid_t to, const piojo_graph_t *graph)

void	piojo_graph_unlink (piojo_graph_vid_t from, piojo_graph_vid_t to, piojo_graph_t *graph)

void	piojo_graph_unlink_all (piojo_graph_vid_t vertex, piojo_graph_t *graph)

size_t	piojo_graph_neighbor_cnt (piojo_graph_vid_t vertex, const piojo_graph_t *graph)

piojo_graph_vid_t	piojo_graph_neighbor_at (size_t idx, piojo_graph_vid_t vertex, const piojo_graph_t *graph)

piojo_graph_weight_t	piojo_graph_edge_weight (size_t idx, piojo_graph_vid_t vertex, const piojo_graph_t *graph)

bool	piojo_graph_vid_eq (const void e1, const void e2)

bool	piojo_graph_breadth_first (piojo_graph_vid_t root, piojo_graph_visit_cb cb, size_t limit, const piojo_graph_t *graph)

bool	piojo_graph_depth_first (piojo_graph_vid_t root, piojo_graph_visit_cb cb, size_t limit, const piojo_graph_t *graph)

void	piojo_graph_source_path (piojo_graph_vid_t root, const piojo_graph_t graph, piojo_hash_t dists, piojo_hash_t *prevs)

piojo_graph_weight_t	piojo_graph_pair_path (piojo_graph_vid_t root, piojo_graph_vid_t dst, const piojo_graph_t graph, piojo_hash_t prevs)

bool	piojo_graph_neg_source_path (piojo_graph_vid_t root, const piojo_graph_t graph, piojo_hash_t dists, piojo_hash_t *prevs)

piojo_graph_weight_t	piojo_graph_min_tree (const piojo_graph_t graph, piojo_graph_t tree)

piojo_graph_weight_t	piojo_graph_a_star (piojo_graph_vid_t root, piojo_graph_vid_t dst, piojo_graph_cost_cb heuristic, const piojo_graph_t graph, piojo_hash_t prevs)

bool	piojo_graph_sort (const piojo_graph_t graph, piojo_array_t vertices)

Variables
const size_t	piojo_graph_sizeof

const piojo_graph_weight_t	PIOJO_GRAPH_WEIGHT_MAX

Detailed Description

Piojo Graph implementation.

Typedef Documentation

typedef piojo_graph_weight_t(* piojo_graph_cost_cb)(piojo_graph_vid_t from, piojo_graph_vid_t to, const piojo_graph_t *graph)

Returns cost estimate between two vertices.

typedef piojo_id_t piojo_graph_vid_t

Vertex id.

typedef bool(* piojo_graph_visit_cb)(piojo_graph_vid_t v, const piojo_graph_t *graph)

Vertex visitor, returns TRUE to stop traversal, FALSE otherwise.

typedef float piojo_graph_weight_t

Edge weight.

Enumeration Type Documentation

enum piojo_graph_dir_t

Whether the graph is directed.

Enumerator
PIOJO_GRAPH_DIR_TRUE	Directed graph.
PIOJO_GRAPH_DIR_FALSE	Undirected graph.

Function Documentation

piojo_graph_weight_t piojo_graph_a_star	(	piojo_graph_vid_t	root,
		piojo_graph_vid_t	dst,
		piojo_graph_cost_cb	heuristic,
		const piojo_graph_t *	graph,
		piojo_hash_t *	prevs
	)

Finds shortest path from root to dst vertex using A* algorithm.

Warning: The graph can't have negative edge weights.; root must be different from dst.

Parameters

[in]	root	Starting vertex.
[in]	dst	Destination vertex.
[in]	heuristic	Cost estimate function (should be consistent).
[in]	graph
[out]	prevs	Previous vertex in path for each vertex (if a path exists), can be NULL.

Returns: Distance (weight sum) to dst or 0 if there isn't any path.

piojo_graph_t* piojo_graph_alloc ( piojo_graph_dir_t directed )

Allocates a new graph. Uses default allocator.

Parameters

[in] directed Graph direction.

Returns: New graph.

piojo_graph_t* piojo_graph_alloc_cb	(	piojo_graph_dir_t	directed,
		piojo_alloc_if	allocator
	)

Allocates a new graph.

Parameters

[in]	directed	Graph direction.
[in]	allocator	Allocator to be used.

Returns: New graph.

bool piojo_graph_breadth_first	(	piojo_graph_vid_t	root,
		piojo_graph_visit_cb	cb,
		size_t	limit,
		const piojo_graph_t *	graph
	)

Traverses graph following a breadth first search.

Parameters

[in]	root	Starting vertex.
[in]	cb	Vertex visit function.
[in]	limit	Depth limit or 0 for no limit.
[in]	graph

Returns: Value returned by cb.

void piojo_graph_clear ( piojo_graph_t * graph )

Deletes all vertices/edges in graph.

Parameters

[out] graph Graph being cleared.

piojo_graph_t* piojo_graph_copy ( const piojo_graph_t * graph )

Copies graph and all its vertices/edges.

Parameters

[in] graph Graph being copied.

Returns: New graph.

bool piojo_graph_delete	(	piojo_graph_vid_t	vertex,
		piojo_graph_t *	graph
	)

Deletes vertex.

Parameters

[in]	vertex	Vertex being deleted.
[out]	graph

Returns: TRUE if deleted, FALSE if it's not present.

bool piojo_graph_depth_first	(	piojo_graph_vid_t	root,
		piojo_graph_visit_cb	cb,
		size_t	limit,
		const piojo_graph_t *	graph
	)

Traverses graph following a depth first search.

Parameters

[in]	root	Starting vertex.
[in]	cb	Vertex visit function.
[in]	limit	Depth limit or 0 for no limit.
[in]	graph

Returns: Value returned by cb.

piojo_graph_weight_t piojo_graph_edge_weight	(	size_t	idx,
		piojo_graph_vid_t	vertex,
		const piojo_graph_t *	graph
	)

Returns edge weight from vertex to neighbor idx.

Parameters

[in]	idx	Neighbor index.
[in]	vertex	Vertex.
[in]	graph

Returns: Neighbor edge weight.

void piojo_graph_free ( const piojo_graph_t * graph )

Frees graph and all its vertices/edges.

Parameters

[in] graph Graph being freed.

piojo_opaque_t piojo_graph_gvalue ( const piojo_graph_t * graph )

Returns user-defined graph value (default is 0).

Parameters

[in] graph

Returns: Graph value.

bool piojo_graph_insert	(	piojo_graph_vid_t	vertex,
		piojo_graph_t *	graph
	)

Inserts new vertex.

Parameters

[in]	vertex
[out]	graph

Returns: TRUE if inserted, FALSE if it's duplicated.

void piojo_graph_link	(	piojo_graph_weight_t	weight,
		piojo_graph_vid_t	from,
		piojo_graph_vid_t	to,
		piojo_graph_t *	graph
	)

Links two vertices, if they're already linked updates the weight.

Parameters

[in]	weight	Edge weight.
[in]	from	Source vertex.
[in]	to	Destination vertex.
[out]	graph

piojo_graph_weight_t* piojo_graph_linked	(	piojo_graph_vid_t	from,
		piojo_graph_vid_t	to,
		const piojo_graph_t *	graph
	)

Returns edge weight if an edge exists between two vertices.

Parameters

[in]	from	Source vertex.
[in]	to	Destination vertex.
[in]	graph

Returns: Pointer to edge weight if an edge exists, NULL otherwise.

piojo_graph_weight_t piojo_graph_min_tree	(	const piojo_graph_t *	graph,
		piojo_graph_t *	tree
	)

Finds minimum spanning tree when graph is connected. Otherwise, finds the minimum spanning forest (Kruskal's algorithm).

Warning: The graph must be undirected.

Parameters

[in]	graph
[out]	tree	Minimum spanning tree/forest of graph.

Returns: Tree weight or 0 for an empty graph.

bool piojo_graph_neg_source_path	(	piojo_graph_vid_t	root,
		const piojo_graph_t *	graph,
		piojo_hash_t *	dists,
		piojo_hash_t *	prevs
	)

Finds shortest path from root to all vertices (Bellman-Ford algorithm).

Warning: If the graph have negative cycles reachable from root, shortest paths won't be found.; If the graph is undirected then any edge with negative weight forms a negative cycle.

Parameters

[in]	root	Starting vertex.
[in]	graph
[out]	dists	Distance (weight sum) for each vertex (if a path exists).
[out]	prevs	Previous vertex in path for each vertex (if a path exists), can be NULL.

Returns: TRUE if root reaches a negative cycle, FALSE otherwise.

piojo_graph_vid_t piojo_graph_neighbor_at	(	size_t	idx,
		piojo_graph_vid_t	vertex,
		const piojo_graph_t *	graph
	)

Returns neighbor from vertex.

Parameters

[in]	idx	Neighbor index.
[in]	vertex	Vertex.
[in]	graph

Returns: Neighbor vertex.

size_t piojo_graph_neighbor_cnt	(	piojo_graph_vid_t	vertex,
		const piojo_graph_t *	graph
	)

Returns neighbor count from vertex.

Parameters

[in]	vertex	Vertex.
[in]	graph

Returns: Number of neighbor vertices.

piojo_graph_weight_t piojo_graph_pair_path	(	piojo_graph_vid_t	root,
		piojo_graph_vid_t	dst,
		const piojo_graph_t *	graph,
		piojo_hash_t *	prevs
	)

Finds shortest path from root to dst vertex (Dijkstra's algorithm).

Warning: The graph can't have negative edge weights.; root must be different from dst.

Parameters

[in]	root	Starting vertex.
[in]	dst	Destination vertex.
[in]	graph
[out]	prevs	Previous vertex in path for each vertex (if a path exists), can be NULL.

Returns: Distance (weight sum) to dst or 0 if there isn't any path.

void piojo_graph_set_gvalue	(	piojo_opaque_t	value,
		piojo_graph_t *	graph
	)

Sets user-defined graph value (default is 0).

Parameters

[in]	value
[out]	graph

void piojo_graph_set_vvalue	(	piojo_opaque_t	value,
		piojo_graph_vid_t	vertex,
		piojo_graph_t *	graph
	)

Sets user-defined vertex value (default is 0).

Parameters

[in]	value
[in]	vertex
[out]	graph

bool piojo_graph_sort	(	const piojo_graph_t *	graph,
		piojo_array_t *	vertices
	)

Finds a topological ordering (Kahn's algorithm).

Warning: The graph must be directed.

Parameters

[in]	graph
[out]	vertices	Vertices in topological order.

Returns: TRUE if graph has a cycle, FALSE otherwise.

void piojo_graph_source_path	(	piojo_graph_vid_t	root,
		const piojo_graph_t *	graph,
		piojo_hash_t *	dists,
		piojo_hash_t *	prevs
	)

Finds shortest path from root to all vertices (Dijkstra's algorithm).

Warning: The graph can't have negative edge weights.

Parameters

[in]	root	Starting vertex.
[in]	graph
[out]	dists	Distance (weight sum) for each vertex (if a path exists).
[out]	prevs	Previous vertex in path for each vertex (if a path exists), can be NULL.

void piojo_graph_unlink	(	piojo_graph_vid_t	from,
		piojo_graph_vid_t	to,
		piojo_graph_t *	graph
	)

Unlinks two vertices if they are linked (does nothing otherwise).

Parameters

[in]	from	Vertex.
[in]	to	Vertex.
[out]	graph

void piojo_graph_unlink_all	(	piojo_graph_vid_t	vertex,
		piojo_graph_t *	graph
	)

Unlinks every vertex from vertex.

Parameters

[in]	vertex	Vertex.
[out]	graph

bool piojo_graph_vid_eq	(	const void *	e1,
		const void *	e2
	)

Vertex equality function.

Parameters

[in]	e1	Vertex pointer.
[in]	e2	Vertex pointer.

Returns: TRUE if e1 is equal to e2, FALSE otherwise.

piojo_opaque_t piojo_graph_vvalue	(	piojo_graph_vid_t	vertex,
		const piojo_graph_t *	graph
	)

Returns user-defined vertex value (default is 0).

Parameters

[in]	vertex
[in]	graph

Returns: Vertex value.

Variable Documentation

const size_t piojo_graph_sizeof

Size of graph in bytes

const piojo_graph_weight_t PIOJO_GRAPH_WEIGHT_MAX

Maximum weight, greater values will be capped to it.

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation