
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070801 13:47:59
Author: asutton
Date: 20070801 13:47:58 EDT (Wed, 01 Aug 2007)
New Revision: 38342
URL: http://svn.boost.org/trac/boost/changeset/38342
Log:
Renaming more files
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_all_cliques.qbk
 copied unchanged from r38339, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_clique.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_all_cycles.qbk
 copied unchanged from r38339, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_cycle.qbk
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_clique.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_cycle.qbk
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_clique.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_clique.qbk 20070801 13:47:58 EDT (Wed, 01 Aug 2007)
+++ (empty file)
@@ 1,61 +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 Bron Kerbosch Cliques]

 template <typename Graph, typename Visitor>
 void
 bron_kerbosch_find_cliques(const Graph& g, Visitor vis)

These functions find all /cliques/ (maximal fully connected subgraphs) of the
given graph, invoking a visitor when each clique is found.

The `bron_kerbosch_visit_cliques()` function is intended for use with undirected
graphs, but will work for directed graphs as well at added cost. In order for a
directed clique to exist, each vertex /u/ must be connected to /v/ and /v/ must
be connected to /u/.

[heading Where Defined]
`boost/graph/clique.hpp`

[heading Parameters]

[table
 [[Type] [Parameter] [Description]]
 [
 [required, in] [`const Graph& g`]
 [
 The graph for which cliques are being visited. The `Graph` type must
 /approximate/ the [BoostAdjacencyMatrix] in that it must implement
 the `edge(u,v,g)` function. It is not, however, required to return
 in constant time. Note that most graph types provide this function,
 including [boost_adjacency_list], [boost_undirected_graph], and
 [boost_directed_graph].
 ]
 ]
 [
 [required, in] [`Visitor vis`]
 [
 The visitor object to the algorithm. This `Visitor` class must
 model the [BoostCliqueVisitor] class.
 ]
 ]
]

[h5 Return Value]
This function does not return a value.

[h5 Complexity]
The complexity of this function was originally approximated as being proportional to
/O(3.14[super V])/. No strict upper bound is reported. If the `Graph` type
approximates the [BoostAdjacencyMatrix] concept, then the algorithm will perform
slower by a factor of V.

[h5 Examples]


[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_cycle.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_cycle.qbk 20070801 13:47:58 EDT (Wed, 01 Aug 2007)
+++ (empty file)
@@ 1,61 +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 Tiernan Cycles]

 template <typename Graph, typename Visitor>
 void
 tiernan_find_cycles(const Graph& g, Visitor vis)

These functions find all /cycles/ within of the given graph, invoking a visitor
when each cycle is found.

The `tiernan_visit_cycles()` function is designed to work on directed graph, but
works for undirected graphs as well. When running on undirected graphs, however,
the algorithm treats each edge connecting two vertices /(u,v)/ as if it were
two edges /(u,v)/ and /(v,u)/. As result the algorithm will report cycles in
both directions.

[heading Where Defined]
`boost/graph/tiernan_find_cycles.hpp`

[heading Parameters]

[table
 [[Type] [Parameter] [Description]]
 [
 [required, in] [`const Graph& g`]
 [
 The graph for which cliques are being visited. The `Graph` type must
 /approximate/ the [BoostAdjacencyMatrix] in that it must implement
 the `edge(u,v,g)` function. It is not, however, required to return
 in constant time. Note that most graph types provide this function,
 including [boost_adjacency_list], [boost_undirected_graph], and
 [boost_directed_graph].
 ]
 ]
 [
 [required, in] [`Visitor vis`]
 [
 The visitor object to the algorithm. This `Visitor` class must
 model the [BoostCliqueVisitor] class.
 ]
 ]
]

[h5 Return Value]
This function does not return a value.

[h5 Complexity]
No complexity has been reported for this algorithm, but it is expected to
run in /O(P(g))/ where /P(g)/ is the number of distinct simple paths in the
graph /g/ (which can be very large).

[h5 Examples]


[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