2.10. igraph_girth — The girth of a graph is the length of the shortest circle in it.

2.10. `igraph_girth` — The girth of a graph is the length of the shortest circle in it.

int igraph_girth(const igraph_t *graph, igraph_integer_t *girth, 
		 igraph_vector_t *circle);

The current implementation works for undirected graphs only, directed graphs are treated as undirected graphs. Loop edges and multiple edges are ignored.

If the graph is a forest (ie. acyclic), then zero is returned.

This implementation is based on Alon Itai and Michael Rodeh: Finding a minimum circuit in a graph Proceedings of the ninth annual ACM symposium on Theory of computing , 1-10, 1977. The first implementation of this function was done by Keith Briggs, thanks Keith.

Arguments:

`graph`:	The input graph.
`girth`:	Pointer to an integer, if not `NULL` then the result will be stored here.
`circle`:	Pointer to an initialized vector, the vertex ids in the shortest circle will be stored here. If `NULL` then it is ignored.

Returns:

Error code.

Time complexity: O((|V|+|E|)^2), |V| is the number of vertices, |E| is the number of edges in the general case. If the graph has no circles at all then the function needs O(|V|+|E|) time to realize this and then it stops.