|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-01 13:45:24
Author: asutton
Date: 2007-08-01 13:45:22 EDT (Wed, 01 Aug 2007)
New Revision: 38339
URL: http://svn.boost.org/trac/boost/changeset/38339
Log:
Moving some files around
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_clique.qbk
- copied, changed from r38332, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_cycle.qbk
- copied, changed from r38332, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/cycle.qbk
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/cycle.qbk
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_clique.qbk | 4 ++--
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk | 18 +++++++++---------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_cycle.qbk | 8 ++++----
3 files changed, 15 insertions(+), 15 deletions(-)
Copied: sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_clique.qbk (from r38332, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk)
==============================================================================
--- /sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_clique.qbk 2007-08-01 13:45:22 EDT (Wed, 01 Aug 2007)
@@ -5,11 +5,11 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
-[section Clique]
+[section Bron Kerbosch Cliques]
template <typename Graph, typename Visitor>
void
- bron_kerbosch_visit_cliques(const Graph& g, Visitor vis)
+ 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.
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk 2007-08-01 13:45:22 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 Clique]
-
- template <typename Graph, typename Visitor>
- void
- bron_kerbosch_visit_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/cycle.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/cycle.qbk 2007-08-01 13:45:22 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 Clique]
-
- template <typename Graph, typename Visitor>
- void
- tiernan_visit_cycles(const Graph& g, Visitor vis)
-
-These functions find all /cycles/ within of the given graph, invoking a visitor
-when each clique 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/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]
-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
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk 2007-08-01 13:45:22 EDT (Wed, 01 Aug 2007)
@@ -39,21 +39,21 @@
[include depth_first_search.qbk]
[endsect]
-[section Shortest Paths]
-[endsect]
-
-[section Minimum Spanning Tree]
-[endsect]
-
[section Connectivity]
[include connected_components.qbk]
[include strong_components.qbk]
[include connectivity.qbk]
[endsect]
-[section Subgraph Finding]
-[include clique.qbk]
-[include cycle.qbk]
+[section Shortest Paths]
+[endsect]
+
+[section Minimum Spanning Tree]
+[endsect]
+
+[section Subgraph]
+[include bron_kerbosch_clique.qbk]
+[include tiernan_cycle.qbk]
[endsect]
[section Maximum Flow]
Copied: sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_cycle.qbk (from r38332, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/cycle.qbk)
==============================================================================
--- /sandbox/SOC/2007/graphs/libs/graph/doc/reference/cycle.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_cycle.qbk 2007-08-01 13:45:22 EDT (Wed, 01 Aug 2007)
@@ -5,14 +5,14 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
-[section Clique]
+[section Tiernan Cycles]
template <typename Graph, typename Visitor>
void
- tiernan_visit_cycles(const Graph& g, Visitor vis)
+ tiernan_find_cycles(const Graph& g, Visitor vis)
These functions find all /cycles/ within of the given graph, invoking a visitor
-when each clique is found.
+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,
@@ -21,7 +21,7 @@
both directions.
[heading Where Defined]
-`boost/graph/clique.hpp`
+`boost/graph/tiernan_find_cycles.hpp`
[heading Parameters]
Boost-Commit 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