[Boost-commit] svn:boost r7193

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
URL: http://svn.boost.org/trac/boost/changeset/7193

Log:
Re-adding visitors files

Added:
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/con_visitors.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk
      - copied unchanged from r7192, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/con_graphs.qbk
Removed:
   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 http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[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.
-
-[table
-    [[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`.]]
-]
-
-[*TODO]
-
-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...
-
-[endsect]

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 http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[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
+
+[endsect]
\ No newline at end of file