Defined in <
template<typename GraphView> GraphView make_lollipop(size_t m,size_t n,bool bidirectional)
Generate a lollipop graph.
This is the barbell graph without the right barbell.
For $$m > 1$$ and $$n \geq 0$$, the complete graph $$K_m$$ is connected to the path $$P_n$$. The resulting $$m+n$$ nodes are labelled $$0, \dots, m-1$$ for the complete graph and $$m, \dots, m+n-1$$ for the path. The 2 subgraphs are joined via the edge $$(m-1,m)$$. If $$n=0$$, this is merely a complete graph.
Node labels are the integers 0 to m+n-1.
This function mutates the input graph.
This graph is an extremal example in David Aldous and Jim Fill's etext on Random Walks on Graphs. 1
- m: The number of nodes in the complete subgraph.
- n: The number of nodes in the chain.
- bidirectional: True for adding back-edges, False for forward only.
A view over the generated graph.
The returned view owns its underlying container.
using view_type = stapl::graph_view<stapl::multidigraph<int>>; auto v = stapl::generators::make_lollipop<view_type>(16, 1024);
1 Aldous, David and Fill, James Allen. "Reversible Markov Chains and Random Walks on Graphs," 2002. https://www.stat.berkeley.edu/~aldous/RWG/book.html