View source: R/structural.properties.R
girth | R Documentation |
The girth of a graph is the length of the shortest circle in it.
girth(graph, circle = TRUE)
graph |
The input graph. It may be directed, but the algorithm searches for undirected circles anyway. |
circle |
Logical scalar, whether to return the shortest circle itself. |
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 (i.e. acyclic), then Inf
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.
A named list with two components:
girth |
Integer constant, the girth of the graph, or 0 if the graph is acyclic. |
circle |
Numeric vector with the vertex ids in the shortest circle. |
Gabor Csardi csardi.gabor@gmail.com
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
Other structural.properties:
bfs()
,
component_distribution()
,
connect()
,
constraint()
,
coreness()
,
degree()
,
dfs()
,
distance_table()
,
edge_density()
,
feedback_arc_set()
,
is_acyclic()
,
is_dag()
,
is_matching()
,
k_shortest_paths()
,
knn()
,
reciprocity()
,
subcomponent()
,
subgraph()
,
topo_sort()
,
transitivity()
,
unfold_tree()
,
which_multiple()
,
which_mutual()
Graph cycles
feedback_arc_set()
,
has_eulerian_path()
,
is_acyclic()
,
is_dag()
# No circle in a tree
g <- make_tree(1000, 3)
girth(g)
# The worst case running time is for a ring
g <- make_ring(100)
girth(g)
# What about a random graph?
g <- sample_gnp(1000, 1 / 1000)
girth(g)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.