
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070627 08:25:35
Author: asutton
Date: 20070627 08:25:35 EDT (Wed, 27 Jun 2007)
New Revision: 7193
URL: http://svn.boost.org/trac/boost/changeset/7193
Log:
Readding 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 20070627 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 datastructure neutral fashion. In fact, the BGL interface need
not even be implemented using a datastructure, 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 datastructures 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 nonmutable 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 20070627 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 callback 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
BoostCommit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk