| |
An undirected graph data structure.
An undirected graph (also called a network) is a data structure that
contains a set of vertices and relationships between pairs of vertices,
called edges. Given two vertices u and v, an edge (u, v) indicates a
relationship between them. What vertices and edges mean depends on how
the data structure is used. For instance, vertices may be cities and
edges are the roads that connect them. Or, edges may represent direct
network connections between two routers or two computers. Since the
graph is undirected, the order of the vertices in the edge does not
matter: the relationship is mutual. For graphs where the edge direction
does matter, use the Digraph class.
Vertices and edges provide the structure of the graph, but most of the
interesting domain-specific information of graphs is actually stored on
the vertices and edges of the graph. For this reason, one can create
properties via the vertex_property_map and edge_property_map methods
to represent, for instance, the IP address of a vertex that represents
a router or the length of a road connecting two cities.
Complete C++ documentation for the adjacency list representation:
http://www.boost.org/libs/graph/doc/adjacency_list.html
|
| |
- Method resolution order:
- Graph
- Boost.Python.instance
- __builtin__.object
Methods defined here:
- __getstate__(...)
- __init__(...)
- __init__(self, edges = list()) -> Graph
Constructs a new graph from a list of edges. The edges argument
should be a sequence of tuples, where each tuple contains the source and
target vertices of an edge. The sources and targets can be any type,
so long as that type can be ordered with < and compared with ==, e.g.,
strings, integers, or floating-point-numbers.
- __reduce__ = (...)
- __setstate__(...)
- add_edge(...)
- add_edge(self, u, v) -> Edge
Add an edge between two vertices.
Self-loops and parallel edges are permitted.
- add_vertex(...)
- add_vertex(self) -> Vertex
Adds a new vertex to the graph.
- adjacent_vertices(...)
- adjacent_vertices(self, u) -> AdjacencyIterator
Enumerate vertices adjacent to u.
- clear_vertex(...)
- clear_vertex(self, v)
Removes all outgoing and incoming edges from v.
- convert_property_map(...)
- convert_property_map(self, source_map, type) -> object
Converts the property map source_map into another property map
with a different element type and returns that new property map.
The old property map is unchanged. If a conversion is not supported,
this routine will return None.
Parameters:
source_map A property map for the vertices or edges of the
given graph.
type The element type of the resulting property map.
This may be any type supported by vertex_property_map
or edge_property_map.
- edge(...)
- edge(self, u, v) -> Edge
Returns an edge (u, v) if one exists, otherwise None.
- edge_property_map(...)
- edge_property_map(self, type) -> EdgePropertyMap
Creates a new property map that maps from edges in the graph to
values of the given type. The type parameter may be any one of:
integer
float
vertex
edge
string
point2d
point3d
object
color
- in_degree(...)
- in_degree(self, u) -> int
Returns the number of incoming edges to u.
- in_edges(...)
- in_edges(self, u) ->InEdgeIterator
Enumerate edges incoming to u.
- is_directed(...)
- is_directed(self) -> bool
Whether the graph is directed or not.
- num_edges(...)
- num_edges(self) -> int
Return the number of edges in the graph.
- num_vertices(...)
- num_vertices(self) -> int
Return the number of vertices in the graph.
- out_degree(...)
- out_degree(self, u) -> int
Returns the number of outgoing edges from u.
- out_edges(...)
- out_edges(self, u) ->OutEdgeIterator
Enumerate edges outgoing from u.
- remove_edge(...)
- remove_edge(self, e)
Removes edge e from the graph.
- remove_vertex(...)
- remove_vertex(self, v)
Removes a vertex from the graph.
Vertex v must have no incoming or outgoing edges. If you aren't sure,
call clear_vertex first.
- source(...)
- source(self, e) -> Vertex
Returns the source of edge e.
- target(...)
- target(self, e) -> Vertex
Returns the target of edge e.
- vertex_property_map(...)
- vertex_property_map(self, type) -> VertexPropertyMap
Creates a new property map that maps from vertices in the graph to
values of the given type. The type parameter may be any one of:
integer
float
vertex
edge
string
point2d
point3d
object
color
- write_graphviz(...)
- write_graphviz(self, filename)
Writes the graph into the file filename (overwriting the file if it
already exists) using the GraphViz DOT format.
See also:
read_graphviz
The GraphViz DOT language is described here:
http://www.graphviz.org/doc/info/lang.html
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/write-graphviz.html
Static methods defined here:
- erdos_renyi_graph(...)
- erdos_renyi_graph(num_vertices, probability, allow_self_loops = False,
random_seed = 1) -> Graph
Constructs a new Erdos-Renyi random graph with num_vertices vertices and
a uniform probability of having an edge (u, v) in the graph for any
vertices u and v. Expect a graph with probability*num_vertices^2 edges.
Parameters:
num_vertices The number of vertices in the graph.
probability The probability of having an edge (u, v).
allow_self_loops Whether self-loops (u, u) will be generated.
random_seed Nonzero seed value for the random number generator.
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/erdos_renyi_generator.html
- plod_graph(...)
- plod_graph(num_vertices, alpha, beta, allow_self_loops = False,
random_seed = 1) -> Graph
Constructs a new power law graph with num_vertices vertices. The number
of connections to a given vertex is beta*x^(-alpha), where alpha and
beta are parameters to the algorithm and x is a random variable between
0 and num_vertices - 1.
Parameters:
num_vertices The number of vertices in the graph.
alpha The exponential fall-off in the degree distribution.
beta Controls how many edges will occur in the graph.
allow_self_loops Whether self-loops (u, u) will be generated.
random_seed Nonzero seed value for the random number generator.
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/plod_generator.html
- read_graphviz(...)
- read_graphviz(filename, node_id = 'node_id') -> Graph
Loads a graph written in GraphViz DOT format from the file filename.
Parameters:
filename The name of the file to load.
node_id The name given to the property map that will store the
identifier associated with each vertex in the DOT file.
Exceptions:
directed_graph_error Thrown if one tries to read a directed graph
into the Graph class.
undirected_graph_error Thrown if one tries to read an undirected
graph into the Digraph class.
See also:
write_graphviz
The GraphViz DOT language is described here:
http://www.graphviz.org/doc/info/lang.html
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/read_graphviz.html
- small_world_graph(...)
- small_world_graph(num_vertices, num_neighbors, rewire_probability,
allow_self_loops = False, random_seed = 1) -> Graph
Constructs a new small-world graph with num_vertices vertices, each
adjacent to its num_neighbors closest neighbors (assume that the
vertcices were arranged in a circle). With probability
rewire_probability, an edge will be rewired randomly.
Parameters:
num_vertices The number of vertices in the graph.
num_neighbors The number of neighbors each vertex starts with.
rewire_probability Probability of rewiring any given edge.
allow_self_loops Whether self-loops (u, u) will be generated.
random_seed Nonzero seed for the random number generator.
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/small_world_generator.html
Properties defined here:
- edge_properties
- A Python dictionary mapping from edge property names to
property maps. These properties are "attached" to the graph
and will be pickled or serialized along with the graph.
- get = (...)
- edges
- edges(self) -> VertexIterator
Enumerate the edges in the graph.
- get = (...)
- vertex_properties
- A Python dictionary mapping from vertex property names to
property maps. These properties are "attached" to the graph
and will be pickled or serialized along with the graph.
- get = (...)
- vertices
- vertices(self) -> VertexIterator
Enumerate the vertices in the graph.
- get = (...)
Data and other attributes defined here:
- __instance_size__ = 68
- __safe_for_unpickling__ = True
Data and other attributes inherited from Boost.Python.instance:
- __dict__ = <dictproxy object at 0x20e550>
- __new__ = <built-in method __new__ of Boost.Python.class object at 0x5f818c>
- T.__new__(S, ...) -> a new object with type S, a subtype of T
- __weakref__ = <member '__weakref__' of 'Boost.Python.instance' objects>
|