Boost logo

Boost-Commit :

From: asutton_at_[hidden]
Date: 2007-06-27 08:25:35

Author: asutton
Date: 2007-06-27 08:25:35 EDT (Wed, 27 Jun 2007)
New Revision: 7193

Re-adding visitors files

      - copied unchanged from r7192, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/con_graphs.qbk

Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/con_graphs.qbk
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/con_graphs.qbk 2007-06-27 08:25:35 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,110 +0,0 @@
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at
- /]
-[section Graph Concepts]
-The heart of the Boost Graph Library (BGL) is the interface, or concepts (in the
-parlance of generic programming), that define how a graph can be examined and
-manipulated in a data-structure neutral fashion. In fact, the BGL interface need
-not even be implemented using a data-structure, as for some problems it is easier
-or more efficient to define a graph implicitly based on some functions.
-The Boost.Graph interface does not appear as a single graph concept. Instead it is
-factored into much smaller peices. The reason for this is that the purpose of a
-concept is to summarize the requirements for particular algorithms. Any one algorithm
-does not need every kind of graph operation, typically only a small subset. Furthermore,
-there are many graph data-structures that can not provide efficient implementations of
-all the operations, but provide highly efficient implementations of the operations
-necessary for a particular algorithm . By factoring the graph interface into many smaller
-concepts we provide the graph algorithm writer with a good selection from which to choose
-the concept that is the closest match for their algorithm.
-Figure 1 shows the refinements relations between the graph concepts. The reason for
-factoring the graph interface into so many concepts is to encourage algorithm interfaces
-to require and use only the minimum interface of a graph, thereby increasing the
-usability of the algorithm.
-Figure 1: The graph concepts and refinement relationships.
-Table 1 gives a summary of the valid expressions and associated types for the graph
-concepts and provides links to the detailed descriptions of each of the concepts.
-The notation used in the table is as follows.
- [[Expression] [Return Type or Description]]
- [[*Graph*]]
- [[`graph_traits<G>::vertex_descriptor`] [The type for vertex representative objects.]]
- [[`graph_traits<G>::edge_descriptor`] [The type for edge representative objects.]]
- [[`graph_traits<G>::directed_category`] [Graph is directed or undirected?]]
- [[`graph_traits<G>::edge_parallel_category`] [Graph allows parallel edges?]]
- [[`graph_traits<G>::traversal_category`] [The ways in which the vertices and edges can be traversed.]]
- [[*Incidence Graph* refines Graph]]
- [[`graph_traits<G>::degree_size_type`] [The integer type for vertex degree.]]
- [[`graph_traits<G>::out_edge_iterator`] [Type for iterating over out edges.]]
- [[`out_edges(v,g)`] [`std::pair<out_edge_iterator, out_edge_iterator>`]]
- [[`out_degree(v,g)`] [`degree_size_type`]]
- [[`source(e,g)`] [`vertex_descriptor`]]
- [[`target(e,g)`] [`vertex_descriptor`]]
- [[*BidirectionalGraph* refines IncidenceGraph]]
- [[`graph_traits<G>::in_edge_iterator`] [Type for iterating over in edges.]]
- [[`in_edges(v,g)`] [`std::pair<in_edge_iterator,in_edge_iterator>`]]
- [[`in_degree(v,g)`] [`degree_size_type`]]
- [[`degree(v,g)`] [`degree_size_type`]]
- [[*AdjacencyGraph* refines Graph]]
- [[`graph_traits<G>::adjacency_iterator`] [Type for iterating over adjacent vertices.]]
- [[`adjacent_vertices(v,g)`] [`std::pair<adjacency_iterator,adjacency_iterator>`]]
- [[*VertexListGraph* refines IncidenceGraph and AdjacencyGraph]]
- [[`graph_traits<G>::vertex_iterator`] [Type for iterating over vertices.]]
- [[`graph_traits<G>::vertices_size_type`] [Unsigned integer type for the number of vertices.]]
- [[`vertices(g)`] [`std::pair<vertex_iterator,vertex_iterator>`]]
- [[`num_vertices(g)`] [`vertices_size_type`]]
- [[*EdgeListGraph* refines Graph]]
- [[`graph_traits<G>::edge_iterator`] [Type for iterating over edges.]]
- [[`graph_traits<G>::edges_size_type`] [Unsigned integer type for the number of edges.]]
- [[`edges(g)`] [`std::pair<edge_iterator, edge_iterator>`]]
- [[`num_edges(g)`] [`edges_size_type`]]
- [[`source(e,g)`] [`vertex_descriptor`]]
- [[`target(e,g)`] [`vertex_descriptor`]]
- [[*AdjacencyMatrix* refines Graph]]
- [[`edge(u,v,g)`] [`std::pair<edge_descriptor,boo>`]]
- [[*MutableGraph* refines Graph]]
- [[`add_vertex(g)`] [`vertex_descriptor`]]
- [[`clear_vertex(v,g)`] [`void`]]
- [[`clear_out_edges(v,g)`] [`void`]]
- [[`clear_in_edges(v,g)`] [`void`]]
- [[`add_edge(u,v,g)`] [`std::pair<edge_descriptor,bool>`]]
- [[`remove_edge(u,v,g)`] [`void`]]
- [[`remove_edge(e,g)`] [`void`]]
- [[`remove_edge(ei,g)`] [`void`]]
- [[`remove_edge_if(pred,g)`] [`void`]]
- [[`remove_out_edge_if(v,pred,g)`] [`void`]]
- [[`remove_in_edge_if(v,pred,g)`] [`void`]]
- [[*MutablePropertyGraph* refines Graph]]
- [[`add_vertex(vp,g)`] [`vertex_descriptor`]]
- [[`add_edge(u,v,ep,g)`] [`std::pair<edge_descriptor,bool>`]]
- [[*PropertyGraph* refines Graph]]
- [[`property_map<G,Property>::type`] [Type for a mutable property map.]]
- [[`property_map<G,Property>::const_type`] [Type for a non-mutable property map.]]
- [[`get(p,g)`] [Function to get a property map.]]
- [[`get(p,g,x)`] [Get the property value for vertex or edge `x`]]
- [[`put(p,g,x,v`)] [Set the property value for vertex or edge `x` to value `v`.]]
-There are some functions missing like `get_property()` and `put/set_property()`.
-These occur in some documentation somewhere but are in no means pervasive, complete
-or accurate.
-It should also be worth pointing out that we can redefine the entire concept hierarchy
-based on a) vertex or edge operations, b) directed/undirected or c) simple or multigraphs.
-Basically, there are some interesting ways to conceptualize the Boost.Graph interface.
-[h3 Undirected Graphs]
-Lots of stuff here on undirected graphs...

Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/con_visitors.qbk
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/con_visitors.qbk 2007-06-27 08:25:35 EDT (Wed, 27 Jun 2007)
@@ -0,0 +1,26 @@
+ / Copyright (c) 2007 Andrew Sutton
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at
+ /]
+[section Visitor Concepts]
+The visitor concepts plays the same role in Boost.Graph as functors play in the STL.
+Functors provide a mechanism for extending an algorithm; for customizing what is done
+at each step of the algorithm. Visitors allow the user to insert their own operations
+at various steps within a graph algorithm. Unlike the STL algorithms, graph algorithms
+typically have multiple event points where one may want to insert a call-back via a
+functor. Therefore visitors do not have a single operator() method like a functor, but
+instead have several methods that correspond to the various event points. Each
+algorithm has a different set of event points, which are described by the following
+visitor concepts:
+* BFS Visitor
+* DFS Visitor
+* Dijkstra Visitor
+* Bellman Ford Visitor
+* A* Visitor
+* Event Visitor
\ No newline at end of file

Boost-Commit list run by bdawes at, david.abrahams at, gregod at, cpdaniel at, john at