C++ Boost
<boost/graph/random> ヘッダは、ランダムグラフの生成、 ランダムな頂点と辺の選択、プロパティのランダム化を行うルーチンを提供する。

Synopsis


  template <class Graph, class RandomNumGen>
  typename graph_traits<Graph>::vertex_descriptor
  random_vertex(Graph& g, RandomNumGen& gen);

  template <class Graph, class RandomNumGen>
  typename graph_traits<Graph>::edge_descriptor
  random_edge(Graph& g, RandomNumGen& gen);

  template <typename MutableGraph, class RandNumGen>
  void generate_random_graph
    (MutableGraph& g, 
     typename graph_traits<MutableGraph>::vertices_size_type V,
     typename graph_traits<MutableGraph>::vertices_size_type E,
     RandNumGen& gen,
     bool self_edges = false);

  template<class Property, class G, class RandomGenerator>
    void randomize_property(G& g, RandomGenerator rg);

Description

random_vertex

  template <class Graph, class RandomNumGen>
  typename graph_traits<Graph>::vertex_descriptor
  random_vertex(Graph& g, RandomNumGen& gen);

Effects: グラフ中の頂点をランダムに選択し、それを返す。

Preconditions: num_vertices(g) != 0

Complexity: O(num_vertices(g))

random_edge

  template <class Graph, class RandomNumGen>
  typename graph_traits<Graph>::edge_descriptor
  random_edge(Graph& g, RandomNumGen& gen);

Effects: グラフ中の辺をランダムに選択し、それを返す。

Preconditions: num_edges(g) != 0

Complexity: O(num_edges(g))

generate_random_graph

  template <typename MutableGraph, class RandNumGen>
  void generate_random_graph
    (MutableGraph& g, 
     typename graph_traits<MutableGraph>::vertices_size_type V,
     typename graph_traits<MutableGraph>::vertices_size_type E,
     RandNumGen& gen,
     bool allow_parallel = true,
     bool self_edges = false);

Effects: g　に頂点 V　と辺 E を加える。 それぞれの辺の始点と終点はランダムに選択される。 self_edges が false なら始点と終点が同一である辺は加えられない。

Precondition: num_vertices(g) == 0

Compleixity: O(V*E)

randomize_property

  template<class Property, class G, class RandomGenerator>
    void randomize_property(G& g, RandomGenerator& rg);

Effects: プロパティの種類に応じて、全ての頂点、または全ての辺に対して、ランダムなプロパティ値を設定する。

Complexity: O(V) または O(E) : プロパティの種類による。

Last modified: Feb 05, 2003

© Copyright Vladimir Prus 2003. Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided ``as is'' without express or implied warranty, and with no claim as to its suitability for any purpose.

Japanese Translation Copyright (C) 2003 Kohske Takahashi

オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の 複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」 に提供されており、いかなる明示的、暗黙的保証も行わない。また、 いかなる目的に対しても、その利用が適していることを関知しない。