|
Boost Users :
|
Hi everyone,
In the documentation it is stated for the "CSRG" that the template
parameter must obey the following :
"A graph type modeling VertexMutableGraph
and EdgeMutableGraph. Also
the graph must have internal vertex_index and
edge_index properties. The vertex indices must be maintained
automatically by the graph, whereas the edge indices will be
assigned by the subgraph class implementation"
Does this mean that I can not "extract" subgraphs from a Compressed
Sparse Row Graph ??
Jacques
---------------------------
This email contains information that is private and confidential and is intended only for the addressee. If you are not the intended recipient please delete it and notify us immediately by e-mailing the sender.
Note: All email sent to or from this address may be accessed by someone other than the recipient, for system management and security reasons.
Aircraft Research Association Ltd. Registered in England, Registration No 503668 Registered Office: Manton Lane, Bedford MK41 7PF England VAT No GB 196351245
Vertex Mutable Graph
A vertex mutable graph can be changed by adding or removing
vertices. The memory management is the responsibility of the graph
implementation. The graph user need only make calls to
add_vertex and remove_vertex and the graph
implementation does the rest.
Refinement of
Graph and DefaultConstructible
Associated Types
No additional associated types.
Valid Expressions
- add_vertex(g)
returns vertex_descriptor
Semantics: Add a new vertex to the graph. The
vertex_descriptor for the new vertex is returned.
- remove_vertex(u, g)
returns void
Semantics: Remove u from the vertex set of the graph.
Preconditions: u is a valid vertex descriptor of graph g
and there are no edges incident to vertex u. The function
clear_vertex can be used to remove all incident edges.
Postconditions: num_vertices(g) is one less; u
no longer appears in the vertex set of the graph and it
is no longer a valid vertex descriptor.
Complexity guarantees
- Vertex insertion is guaranteed to be amortized constant time.
- Vertex removal is at most O(|E| + |V|).
Edge Mutable Graph
The Edge Mutable Graph concept defines the interface for a
graph that supports the addition and removal of edges.
Refinement of
Graph
Associated Types
No additional associated types.
Valid Expressions
- add_edge(u, v, g)
returns std::pair<edge_descriptor, bool>
Semantics: Try to insert the edge (u,v) into the graph,
returning the inserted edge or a parallel edge and a flag that
specifies whether an edge was inserted. This operation must not
invalidate vertex descriptors or vertex iterators of the graph, though
it may invalidate edge descriptors or edge iterators.
Preconditions: u and v are vertices in the
graph.
Postconditions: (u,v) is in the edge set of
the graph. The returned edge descriptor will have u in the
source position and v in the target position. If the graph
allows parallel edges, then the returned flag is always
true. If the graph does not allow parallel edges, if
(u,v) was already in the graph then the returned flag is
false. If (u,v) was not in the graph then the returned
flag is true.
- remove_edge(u, v, g)
returns void
Semantics: Remove the edge (u,v) from the graph. If the
graph allows parallel edges this removes all occurrences of (u,v).
Precondition: (u,v) is in the edge set of the graph.
Postcondition: (u,v) is no longer in the edge set of the graph.
-
remove_edge(e, g)
returns void
Semantics: Remove the edge e from the graph.
Precondition: e is an edge in the graph.
Postcondition: e is no longer in the edge set for g.
-
clear_vertex(u, g)
returns void
Semantics: Remove all edges to and from vertex u from the graph.
Precondition: u is a valid vertex descriptor of
g.
Postconditions: u does not appear as a
source or target of any edge in g.
Complexity guarantees
UNDER CONSTRUCTION
See Also
Graph concepts
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net