projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | <html> |
| 2 | <!-- | |
| 3 | Copyright (c) 2003 Vladimir Prus | |
| 4 | ||
| 5 | Distributed under the Boost Software License, Version 1.0. | |
| 6 | (See accompanying file LICENSE_1_0.txt or copy at | |
| 7 | http://www.boost.org/LICENSE_1_0.txt) | |
| 8 | --> | |
| 9 | <head> | |
| 10 | <title>Boost Graph Library: random</title> | |
| 11 | ||
| 12 | <body BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" | |
| 13 | ALINK="#ff0000"> | |
| 14 | <IMG SRC="../../../boost.png" | |
| 15 | ALT="C++ Boost" width="277" height="86"> | |
| 16 | ||
| 17 | <br> | |
| 18 | ||
| 19 | The header <tt><boost/graph/random></tt> provides routines to create | |
| 20 | random graph, select random vertices and edges, and randomize properties. | |
| 21 | ||
| 22 | <h1>Synopsis</h1> | |
| 23 | ||
| 24 | <pre> | |
| 25 | ||
| 26 | template <class Graph, class RandomNumGen> | |
| 27 | typename graph_traits<Graph>::vertex_descriptor | |
| 28 | random_vertex(Graph& g, RandomNumGen& gen); | |
| 29 | ||
| 30 | template <class Graph, class RandomNumGen> | |
| 31 | typename graph_traits<Graph>::edge_descriptor | |
| 32 | random_edge(Graph& g, RandomNumGen& gen); | |
| 33 | ||
| 34 | template <typename MutableGraph, class RandNumGen> | |
| 35 | void generate_random_graph | |
| 36 | (MutableGraph& g, | |
| 37 | typename graph_traits<MutableGraph>::vertices_size_type V, | |
| 38 | typename graph_traits<MutableGraph>::vertices_size_type E, | |
| 39 | RandNumGen& gen, | |
| 40 | bool self_edges = false); | |
| 41 | ||
| 42 | template<class Property, class G, class RandomGenerator> | |
| 43 | void randomize_property(G& g, RandomGenerator rg); | |
| 44 | ||
| 45 | </pre> | |
| 46 | ||
| 47 | <h1>Description</h1> | |
| 48 | ||
| 49 | <h2 id="random_vertex">random_vertex</h2> | |
| 50 | ||
| 51 | <pre> | |
| 52 | template <class Graph, class RandomNumGen> | |
| 53 | typename graph_traits<Graph>::vertex_descriptor | |
| 54 | random_vertex(Graph& g, RandomNumGen& gen); | |
| 55 | </pre> | |
| 56 | ||
| 57 | <p><b>Effects:</b> Selects a random vertex in a graph and returns it. | |
| 58 | <p><b>Preconditions:</b> <tt>num_vertices(g) != 0</tt> | |
| 59 | <p><b>Complexity:</b> <tt>O(num_vertices(g))</tt> | |
| 60 | ||
| 61 | <h2 id="random_edge">random_edge</h2> | |
| 62 | ||
| 63 | <pre> | |
| 64 | template <class Graph, class RandomNumGen> | |
| 65 | typename graph_traits<Graph>::edge_descriptor | |
| 66 | random_edge(Graph& g, RandomNumGen& gen); | |
| 67 | </pre> | |
| 68 | ||
| 69 | <p><b>Effects:</b> Selects a random edge in a graph and returns it. | |
| 70 | <p><b>Preconditions:</b> <tt>num_edges(g) != 0</tt> | |
| 71 | <p><b>Complexity:</b> <tt>O(num_edges(g))</tt> | |
| 72 | ||
| 73 | <h2 id="generate_random_graph">generate_random_graph</h2> | |
| 74 | ||
| 75 | <pre> | |
| 76 | template <typename MutableGraph, class RandNumGen> | |
| 77 | void generate_random_graph | |
| 78 | (MutableGraph& g, | |
| 79 | typename graph_traits<MutableGraph>::vertices_size_type V, | |
| 80 | typename graph_traits<MutableGraph>::vertices_size_type E, | |
| 81 | RandNumGen& gen, | |
| 82 | bool allow_parallel = true, | |
| 83 | bool self_edges = false); | |
| 84 | </pre> | |
| 85 | ||
| 86 | <p><b>Effects:</b> Adds <tt>V</tt> vertices and <tt>E</tt> edges, to | |
| 87 | <tt>g</tt>. Source and target vertices of each edge are randomly choosen. If | |
| 88 | <tt>self_edges</tt> is false, then no edge will have the same source and | |
| 89 | targets. | |
| 90 | <p><b>Precondition:</b> <tt>num_vertices(g) == 0</tt> | |
| 91 | <p><b>Compleixity:</b> <tt>O(V*E)</tt> | |
| 92 | ||
| 93 | <h2 id="randomize_property">randomize_property</h2> | |
| 94 | ||
| 95 | <pre> | |
| 96 | template<class Property, class G, class RandomGenerator> | |
| 97 | void randomize_property(G& g, RandomGenerator& rg); | |
| 98 | </pre> | |
| 99 | ||
| 100 | <p><b>Effects:</b> Sets the random value of property on either all vertices, or | |
| 101 | all edges, depending on property kind. | |
| 102 | <p><b>Complexity:</b> <tt>O(V)</tt> or <tt>O(E)</tt>, depending on property | |
| 103 | kind. | |
| 104 | ||
| 105 | <hr> | |
| 106 | ||
| 107 | <p class="revision">Last modified: Feb 05, 2003</p> | |
| 108 | ||
| 109 | <p>© Copyright Vladimir Prus 2003. Permission to copy, use, modify, | |
| 110 | sell and distribute this document is granted provided this copyright | |
| 111 | notice appears in all copies. This document is provided ``as is'' without | |
| 112 | express or implied warranty, and with no claim as to its suitability for | |
| 113 | any purpose.</p> | |
| 114 | ||
| 115 | </body> | |
| 116 | ||
| 117 | </html> |