]>
Commit | Line | Data |
---|---|---|
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> |