ProgrammingExamples - User contributions [en]

CPP/Boost/Math/uBLAS/determinant

2011-08-14T12:27:39Z

Awallin: lu_factorize determinant example

Note: if you need to calculate the determinant of a 'small' matrix (3x3 or maybe 5x5) I have found that a brute-force method is much faster than using lu_factorize().

<syntaxhighlight lang="cpp">
#include <boost/numeric/ublas/matrix.hpp>
#include <boost/numeric/ublas/io.hpp>
#include <boost/numeric/ublas/lu.hpp>

namespace bnu = boost::numeric::ublas;

int determinant_sign(const bnu::permutation_matrix<std::size_t>& pm)
{
int pm_sign=1;
std::size_t size = pm.size();
for (std::size_t i = 0; i < size; ++i)
if (i != pm(i))
pm_sign *= -1.0; // swap_rows would swap a pair of rows here, so we change sign
return pm_sign;
}

double determinant( bnu::matrix<double>& m ) {
bnu::permutation_matrix<std::size_t> pm(m.size1());
double det = 1.0;
if( bnu::lu_factorize(m,pm) ) {
det = 0.0;
} else {
for(int i = 0; i < m.size1(); i++)
det *= m(i,i); // multiply by elements on diagonal
det = det * determinant_sign( pm );
}
return det;
}

int main () {
bnu::matrix<double> m(3, 3);
for (unsigned i = 0; i < m.size1() ; ++i) {
for (unsigned j = 0; j < m.size2() ; ++j) {
m (i, j) = 3 * i + sqrt(j+1); // fill matrix
m(i,j) = m(i,j)*m(i,j); // with some numbers
}
}
std::cout << "before det() call m= " << m << std::endl;
double det = determinant(m);
std::cout << "after det() call m= " << m << std::endl; // m has changed afted determinant() call!
std::cout << "determinant=" << det << std::endl;
}
</syntaxhighlight>

Boost

2011-08-14T12:24:29Z

Awallin: /* Boost Math Library */ uBLAS determinant example

The following examples are frequent use cases of parts of the Boost (http://www.boost.org/) library. Each example includes a CMakeLists.txt file so it can be easily compiled.

* [[CPP/Boost/Bimap|Bidirectional (both ways) map]]
* [[CPP/Boost/Function|Glorified function pointers (function.hpp and bind.hpp)]]
* [[CPP/Boost/Histogram|Create a histogram (accumulator)]]
* [[CPP/Boost/Numeric/Matrix|Matrix]]
* [[CPP/Boost/Numeric/MultiArray|Multi dimensional array]]
* [[CPP/Boost/ProgramOptions/Simple|Simple command line argument parsing (ProgramOptions)]]
* [[CPP/Boost/ProgramOptions/MultipleArguments|Multiple command line argument parsing (ProgramOptions)]]
* [[CPP/Boost/ProgressBar|ProgressBar]]
* [[CPP/Boost/Threads|Threads]]
* [[CPP/Boost/ThreadsMember|Threads with member functions]]
* [[CPP/Boost/ThreadCommunication|ThreadCommunication]]
* [[CPP/Boost/Timer|Timer]]
* [[CPP/Boost/Signals/Basic|Signal/slot pattern]]
* [[CPP/Boost/Signals/Class|Signal/slot pattern with member functions]]
* [[CPP/Boost/Signals/ClassMember|Signal/slot pattern with member classes]]
* [[CPP/Boost/Signals/ClassMemberWithParameters|Signal/slot pattern with member classes which have parameters]]
* [[CPP/Boost/Signals2/Basic|Signals2: Signal/slot pattern with type safety]]
* [[CPP/Boost/Signals2/Parameters|Signals2: Signal/slot pattern with parameters type safety]]

== Boost Graph Library (BGL) ==
=== Basics ===
* [[CPP/Boost/CreateGraph|Create a graph]] - This is the most fundamental process of using BGL - creating a graph. This example explains 3 methods of creating a graph, using adjacency_list directly, and also using the directed_graph and undirected_graph subclasses.
* [[CPP/Boost/BGL/IterateEdges|Iterate over all edges in the graph]]
* [[CPP/Boost/BGL/EdgeExists|Check if an edge exists]] - If it does, you also get the edge_descriptor
* [[CPP/Boost/BGL/CopyAGraph|Copy a graph]]
* [[CPP/Boost/BGL/Directed/Weighted|Access an edge]]
* [[CPP/Boost/RemoveVertex|Remove a vertex from a graph]]
* [[CPP/Boost/RemoveEdge|Remove an edge from a graph]]
* [[CPP/Boost/BGL/EdgeProperties|Add properties to edges]]
* [[CPP/Boost/BGL/VertexProperties|Add properties to vertices]]
* [[CPP/Boost/BGL/BundledProperties|Bundled properties]]
* [[CPP/Boost/BGL/AdjacentVertices|Get a list of neighboring (adjacent) vertices]]
* [[CPP/Boost/BGL/DirectedGraph|Directed graphs only give access to out edges]]
* [[CPP/Boost/BGL/BidirectionalGraph|Bidirectional graphs give access to both in and out edges]]
* [[CPP/Boost/BGL/NumberOfNeighbors|Number of incoming, outgoing, and total edges]]
* [[CPP/Boost/BGL/BreadthFirstSearch|Breadth first search (BFS with a custom visitor)]]
* [[CPP/Boost/BGL/MakeBFSVisitor|Breadth first search with make_bfs_visitor]]
* [[CPP/Boost/BGL/DepthFirstSearch|Depth first search (DFS)]]

=== I/O ===
* [[CPP/Boost/BGL/ReadGraph|Read a graph from a file]]
* [[CPP/Boost/BGL/WriteGraph|Write a graph to a file]]
* [[CPP/WishList/Boost/BGL/RelabelInputVertices|Relabel input vertices read from a dot file so they match the labels used in the file]]

=== Algorithms ===

* [[CPP/Boost/BGL/DijkstraDirected|Find the shortest path (Dijkstra) from a specified vertex to all other vertices in a directed graph]]
* [[CPP/Boost/BGL/DijkstraUndirected|Find the shortest path (Dijkstra) from a specified vertex to all other vertices in an undirected graph]]
* [[CPP/Boost/BGL/DijkstraComputePath|Find the shortest path (Dijkstra) from one specified vertex to another specified vertex in a graph]]
* [[CPP/Boost/BGL/BetweennessCentralityClustering|Cluster a graph using betweenness centrality]]

=== Visualization ===

* [[CPP/Boost/BGL/InvisibleEdges|Create a graph with invisible edges]]

=== Wish List ===
Examples in this section are either shells or something is wrong with them that must be fixed before they can graduate into real examples.

== Boost (Generic) Geometry Library ==
* [[CPP/Boost/Geometry/DistanceBetweenPoints|Compute the distance between two points]]
* [[CPP/Boost/Geometry/PointInPolygon|Determine if a point is inside of a polygon (within() function)]]
* [[CPP/Boost/Geometry/Simplify|Simplify a polyline]]

== Boost Math Library ==
=== uBLAS ===
* [[CPP/Boost/Math/uBLAS/determinant]] Calculating the determinant of a matrix using boost::numeric::lu_factorize
=== Tools ===
* [[CPP/Boost/Math/Tools/brent_find_minima|brent_find_minima]] Find a bracketed minimum of a function
* [[CPP/Boost/Math/Tools/TOMS748|TOMS748 root finding algorithm]] Find a bracketed root(zero) of a function

CPP/Boost/Math/Tools/brent find minima

2011-08-14T12:10:51Z

Awallin: simple brent_find_minima example

<syntaxhighlight lang="cpp">
#include <iostream>
#include <sstream>
#include <string>

#include <boost/math/tools/minima.hpp>

double f(double x) { return x * cos(x); }

int main(int argc, char** argv)
{
typedef std::pair<double, double> Result;
// find a root of the function f in the interval x=[3.0, 4.0] with 20-bit precision
Result r2 = boost::math::tools::brent_find_minima(f, 3.0, 4.0, 20);
std::cout << "x=" << r2.first << " f=" << r2.second << std::endl;
return 0;
}

// output:
// x=3.42562 f=-3.28837

/* CMakeLists.txt
cmake_minimum_required(VERSION 2.6)

Project(brent_test)

FIND_PACKAGE(Boost)

INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${Boost_INCLUDE_DIRS})
LINK_DIRECTORIES(${LINK_DIRECTORIES} ${Boost_LIBRARY_DIRS})

ADD_EXECUTABLE(brent_test main.cpp)
*/
</syntaxhighlight>

Boost

2011-08-14T12:08:48Z

Awallin: /* Tools */

The following examples are frequent use cases of parts of the Boost (http://www.boost.org/) library. Each example includes a CMakeLists.txt file so it can be easily compiled.

* [[CPP/Boost/Bimap|Bidirectional (both ways) map]]
* [[CPP/Boost/Function|Glorified function pointers (function.hpp and bind.hpp)]]
* [[CPP/Boost/Histogram|Create a histogram (accumulator)]]
* [[CPP/Boost/Numeric/Matrix|Matrix]]
* [[CPP/Boost/Numeric/MultiArray|Multi dimensional array]]
* [[CPP/Boost/ProgramOptions/Simple|Simple command line argument parsing (ProgramOptions)]]
* [[CPP/Boost/ProgramOptions/MultipleArguments|Multiple command line argument parsing (ProgramOptions)]]
* [[CPP/Boost/ProgressBar|ProgressBar]]
* [[CPP/Boost/Threads|Threads]]
* [[CPP/Boost/ThreadsMember|Threads with member functions]]
* [[CPP/Boost/ThreadCommunication|ThreadCommunication]]
* [[CPP/Boost/Timer|Timer]]
* [[CPP/Boost/Signals/Basic|Signal/slot pattern]]
* [[CPP/Boost/Signals/Class|Signal/slot pattern with member functions]]
* [[CPP/Boost/Signals/ClassMember|Signal/slot pattern with member classes]]
* [[CPP/Boost/Signals/ClassMemberWithParameters|Signal/slot pattern with member classes which have parameters]]
* [[CPP/Boost/Signals2/Basic|Signals2: Signal/slot pattern with type safety]]
* [[CPP/Boost/Signals2/Parameters|Signals2: Signal/slot pattern with parameters type safety]]

== Boost Graph Library (BGL) ==
=== Basics ===
* [[CPP/Boost/CreateGraph|Create a graph]] - This is the most fundamental process of using BGL - creating a graph. This example explains 3 methods of creating a graph, using adjacency_list directly, and also using the directed_graph and undirected_graph subclasses.
* [[CPP/Boost/BGL/IterateEdges|Iterate over all edges in the graph]]
* [[CPP/Boost/BGL/EdgeExists|Check if an edge exists]] - If it does, you also get the edge_descriptor
* [[CPP/Boost/BGL/CopyAGraph|Copy a graph]]
* [[CPP/Boost/BGL/Directed/Weighted|Access an edge]]
* [[CPP/Boost/RemoveVertex|Remove a vertex from a graph]]
* [[CPP/Boost/RemoveEdge|Remove an edge from a graph]]
* [[CPP/Boost/BGL/EdgeProperties|Add properties to edges]]
* [[CPP/Boost/BGL/VertexProperties|Add properties to vertices]]
* [[CPP/Boost/BGL/BundledProperties|Bundled properties]]
* [[CPP/Boost/BGL/AdjacentVertices|Get a list of neighboring (adjacent) vertices]]
* [[CPP/Boost/BGL/DirectedGraph|Directed graphs only give access to out edges]]
* [[CPP/Boost/BGL/BidirectionalGraph|Bidirectional graphs give access to both in and out edges]]
* [[CPP/Boost/BGL/NumberOfNeighbors|Number of incoming, outgoing, and total edges]]
* [[CPP/Boost/BGL/BreadthFirstSearch|Breadth first search (BFS with a custom visitor)]]
* [[CPP/Boost/BGL/MakeBFSVisitor|Breadth first search with make_bfs_visitor]]
* [[CPP/Boost/BGL/DepthFirstSearch|Depth first search (DFS)]]

=== I/O ===
* [[CPP/Boost/BGL/ReadGraph|Read a graph from a file]]
* [[CPP/Boost/BGL/WriteGraph|Write a graph to a file]]
* [[CPP/WishList/Boost/BGL/RelabelInputVertices|Relabel input vertices read from a dot file so they match the labels used in the file]]

=== Algorithms ===

* [[CPP/Boost/BGL/DijkstraDirected|Find the shortest path (Dijkstra) from a specified vertex to all other vertices in a directed graph]]
* [[CPP/Boost/BGL/DijkstraUndirected|Find the shortest path (Dijkstra) from a specified vertex to all other vertices in an undirected graph]]
* [[CPP/Boost/BGL/DijkstraComputePath|Find the shortest path (Dijkstra) from one specified vertex to another specified vertex in a graph]]
* [[CPP/Boost/BGL/BetweennessCentralityClustering|Cluster a graph using betweenness centrality]]

=== Visualization ===

* [[CPP/Boost/BGL/InvisibleEdges|Create a graph with invisible edges]]

=== Wish List ===
Examples in this section are either shells or something is wrong with them that must be fixed before they can graduate into real examples.

== Boost (Generic) Geometry Library ==
* [[CPP/Boost/Geometry/DistanceBetweenPoints|Compute the distance between two points]]
* [[CPP/Boost/Geometry/PointInPolygon|Determine if a point is inside of a polygon (within() function)]]
* [[CPP/Boost/Geometry/Simplify|Simplify a polyline]]

== Boost Math Library ==
=== Tools ===
* [[CPP/Boost/Math/Tools/brent_find_minima|brent_find_minima]] Find a bracketed minimum of a function
* [[CPP/Boost/Math/Tools/TOMS748|TOMS748 root finding algorithm]] Find a bracketed root(zero) of a function

CPP/Boost/Math/Tools/TOMS748

2011-08-14T12:05:15Z

Awallin: Created page with '<syntaxhighlight lang="cpp"> #include <iostream> #include <sstream> #include <string> #include <boost/math/tools/roots.hpp> class Test { public: double operator()(const do…'

<syntaxhighlight lang="cpp">
#include <iostream>
#include <sstream>
#include <string>

#include <boost/math/tools/roots.hpp>

class Test {
public:
double operator()(const double x) {
return x * cos(x);
}
};

// see:
// http://www.boost.org/doc/libs/1_47_0/libs/math/doc/sf_and_dist/html/math_toolkit/toolkit/internals1/roots2.html

int main(int argc, char** argv) {
Test t;
typedef std::pair<double, double> Result;
boost::uintmax_t max_iter=500;
boost::math::tools::eps_tolerance<double> tol(30);

Result r1 = boost::math::tools::toms748_solve(t, 1.0, 2.0, tol, max_iter);
std::cout << "root bracketed: [ " << r1.first << " , " << r1.second << " ]" << std::endl;
std::cout << "f("<< r1.first << ")=" << t(r1.first) << std::endl;
std::cout << "f("<< r1.second << ")=" << t(r1.second) << std::endl;
std::cout << "max_iter=" << max_iter << std::endl;
return 0;
}

/* Output:
root bracketed: [ 1.5708 , 1.5708 ]
f(1.5708)=9.61835e-17
f(1.5708)=-1.99654e-15
max_iter=9
*/

/* CMakeLists.txt:
cmake_minimum_required(VERSION 2.6)
Project(toms748_test)
FIND_PACKAGE(Boost)

INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${Boost_INCLUDE_DIRS})
LINK_DIRECTORIES(${LINK_DIRECTORIES} ${Boost_LIBRARY_DIRS})

ADD_EXECUTABLE(toms748_test main.cpp)
*/
</syntaxhighlight>

Boost

2011-08-14T12:04:45Z

Awallin: correct algorithm name

The following examples are frequent use cases of parts of the Boost (http://www.boost.org/) library. Each example includes a CMakeLists.txt file so it can be easily compiled.

* [[CPP/Boost/Bimap|Bidirectional (both ways) map]]
* [[CPP/Boost/Function|Glorified function pointers (function.hpp and bind.hpp)]]
* [[CPP/Boost/Histogram|Create a histogram (accumulator)]]
* [[CPP/Boost/Numeric/Matrix|Matrix]]
* [[CPP/Boost/Numeric/MultiArray|Multi dimensional array]]
* [[CPP/Boost/ProgramOptions/Simple|Simple command line argument parsing (ProgramOptions)]]
* [[CPP/Boost/ProgramOptions/MultipleArguments|Multiple command line argument parsing (ProgramOptions)]]
* [[CPP/Boost/ProgressBar|ProgressBar]]
* [[CPP/Boost/Threads|Threads]]
* [[CPP/Boost/ThreadsMember|Threads with member functions]]
* [[CPP/Boost/ThreadCommunication|ThreadCommunication]]
* [[CPP/Boost/Timer|Timer]]
* [[CPP/Boost/Signals/Basic|Signal/slot pattern]]
* [[CPP/Boost/Signals/Class|Signal/slot pattern with member functions]]
* [[CPP/Boost/Signals/ClassMember|Signal/slot pattern with member classes]]
* [[CPP/Boost/Signals/ClassMemberWithParameters|Signal/slot pattern with member classes which have parameters]]
* [[CPP/Boost/Signals2/Basic|Signals2: Signal/slot pattern with type safety]]
* [[CPP/Boost/Signals2/Parameters|Signals2: Signal/slot pattern with parameters type safety]]

== Boost Graph Library (BGL) ==
=== Basics ===
* [[CPP/Boost/CreateGraph|Create a graph]] - This is the most fundamental process of using BGL - creating a graph. This example explains 3 methods of creating a graph, using adjacency_list directly, and also using the directed_graph and undirected_graph subclasses.
* [[CPP/Boost/BGL/IterateEdges|Iterate over all edges in the graph]]
* [[CPP/Boost/BGL/EdgeExists|Check if an edge exists]] - If it does, you also get the edge_descriptor
* [[CPP/Boost/BGL/CopyAGraph|Copy a graph]]
* [[CPP/Boost/BGL/Directed/Weighted|Access an edge]]
* [[CPP/Boost/RemoveVertex|Remove a vertex from a graph]]
* [[CPP/Boost/RemoveEdge|Remove an edge from a graph]]
* [[CPP/Boost/BGL/EdgeProperties|Add properties to edges]]
* [[CPP/Boost/BGL/VertexProperties|Add properties to vertices]]
* [[CPP/Boost/BGL/BundledProperties|Bundled properties]]
* [[CPP/Boost/BGL/AdjacentVertices|Get a list of neighboring (adjacent) vertices]]
* [[CPP/Boost/BGL/DirectedGraph|Directed graphs only give access to out edges]]
* [[CPP/Boost/BGL/BidirectionalGraph|Bidirectional graphs give access to both in and out edges]]
* [[CPP/Boost/BGL/NumberOfNeighbors|Number of incoming, outgoing, and total edges]]
* [[CPP/Boost/BGL/BreadthFirstSearch|Breadth first search (BFS with a custom visitor)]]
* [[CPP/Boost/BGL/MakeBFSVisitor|Breadth first search with make_bfs_visitor]]
* [[CPP/Boost/BGL/DepthFirstSearch|Depth first search (DFS)]]

=== I/O ===
* [[CPP/Boost/BGL/ReadGraph|Read a graph from a file]]
* [[CPP/Boost/BGL/WriteGraph|Write a graph to a file]]
* [[CPP/WishList/Boost/BGL/RelabelInputVertices|Relabel input vertices read from a dot file so they match the labels used in the file]]

=== Algorithms ===

* [[CPP/Boost/BGL/DijkstraDirected|Find the shortest path (Dijkstra) from a specified vertex to all other vertices in a directed graph]]
* [[CPP/Boost/BGL/DijkstraUndirected|Find the shortest path (Dijkstra) from a specified vertex to all other vertices in an undirected graph]]
* [[CPP/Boost/BGL/DijkstraComputePath|Find the shortest path (Dijkstra) from one specified vertex to another specified vertex in a graph]]
* [[CPP/Boost/BGL/BetweennessCentralityClustering|Cluster a graph using betweenness centrality]]

=== Visualization ===

* [[CPP/Boost/BGL/InvisibleEdges|Create a graph with invisible edges]]

=== Wish List ===
Examples in this section are either shells or something is wrong with them that must be fixed before they can graduate into real examples.

== Boost (Generic) Geometry Library ==
* [[CPP/Boost/Geometry/DistanceBetweenPoints|Compute the distance between two points]]
* [[CPP/Boost/Geometry/PointInPolygon|Determine if a point is inside of a polygon (within() function)]]
* [[CPP/Boost/Geometry/Simplify|Simplify a polyline]]

== Boost Math Library ==
=== Tools ===
* [[CPP/Boost/Math/Tools/TOMS748|TOMS748 root finding algorithm]]

Boost

2011-08-14T12:01:59Z

Awallin: section for boost/math and link to toms748-example

The following examples are frequent use cases of parts of the Boost (http://www.boost.org/) library. Each example includes a CMakeLists.txt file so it can be easily compiled.

* [[CPP/Boost/Bimap|Bidirectional (both ways) map]]
* [[CPP/Boost/Function|Glorified function pointers (function.hpp and bind.hpp)]]
* [[CPP/Boost/Histogram|Create a histogram (accumulator)]]
* [[CPP/Boost/Numeric/Matrix|Matrix]]
* [[CPP/Boost/Numeric/MultiArray|Multi dimensional array]]
* [[CPP/Boost/ProgramOptions/Simple|Simple command line argument parsing (ProgramOptions)]]
* [[CPP/Boost/ProgramOptions/MultipleArguments|Multiple command line argument parsing (ProgramOptions)]]
* [[CPP/Boost/ProgressBar|ProgressBar]]
* [[CPP/Boost/Threads|Threads]]
* [[CPP/Boost/ThreadsMember|Threads with member functions]]
* [[CPP/Boost/ThreadCommunication|ThreadCommunication]]
* [[CPP/Boost/Timer|Timer]]
* [[CPP/Boost/Signals/Basic|Signal/slot pattern]]
* [[CPP/Boost/Signals/Class|Signal/slot pattern with member functions]]
* [[CPP/Boost/Signals/ClassMember|Signal/slot pattern with member classes]]
* [[CPP/Boost/Signals/ClassMemberWithParameters|Signal/slot pattern with member classes which have parameters]]
* [[CPP/Boost/Signals2/Basic|Signals2: Signal/slot pattern with type safety]]
* [[CPP/Boost/Signals2/Parameters|Signals2: Signal/slot pattern with parameters type safety]]

== Boost Graph Library (BGL) ==
=== Basics ===
* [[CPP/Boost/CreateGraph|Create a graph]] - This is the most fundamental process of using BGL - creating a graph. This example explains 3 methods of creating a graph, using adjacency_list directly, and also using the directed_graph and undirected_graph subclasses.
* [[CPP/Boost/BGL/IterateEdges|Iterate over all edges in the graph]]
* [[CPP/Boost/BGL/EdgeExists|Check if an edge exists]] - If it does, you also get the edge_descriptor
* [[CPP/Boost/BGL/CopyAGraph|Copy a graph]]
* [[CPP/Boost/BGL/Directed/Weighted|Access an edge]]
* [[CPP/Boost/RemoveVertex|Remove a vertex from a graph]]
* [[CPP/Boost/RemoveEdge|Remove an edge from a graph]]
* [[CPP/Boost/BGL/EdgeProperties|Add properties to edges]]
* [[CPP/Boost/BGL/VertexProperties|Add properties to vertices]]
* [[CPP/Boost/BGL/BundledProperties|Bundled properties]]
* [[CPP/Boost/BGL/AdjacentVertices|Get a list of neighboring (adjacent) vertices]]
* [[CPP/Boost/BGL/DirectedGraph|Directed graphs only give access to out edges]]
* [[CPP/Boost/BGL/BidirectionalGraph|Bidirectional graphs give access to both in and out edges]]
* [[CPP/Boost/BGL/NumberOfNeighbors|Number of incoming, outgoing, and total edges]]
* [[CPP/Boost/BGL/BreadthFirstSearch|Breadth first search (BFS with a custom visitor)]]
* [[CPP/Boost/BGL/MakeBFSVisitor|Breadth first search with make_bfs_visitor]]
* [[CPP/Boost/BGL/DepthFirstSearch|Depth first search (DFS)]]

=== I/O ===
* [[CPP/Boost/BGL/ReadGraph|Read a graph from a file]]
* [[CPP/Boost/BGL/WriteGraph|Write a graph to a file]]
* [[CPP/WishList/Boost/BGL/RelabelInputVertices|Relabel input vertices read from a dot file so they match the labels used in the file]]

=== Algorithms ===

* [[CPP/Boost/BGL/DijkstraDirected|Find the shortest path (Dijkstra) from a specified vertex to all other vertices in a directed graph]]
* [[CPP/Boost/BGL/DijkstraUndirected|Find the shortest path (Dijkstra) from a specified vertex to all other vertices in an undirected graph]]
* [[CPP/Boost/BGL/DijkstraComputePath|Find the shortest path (Dijkstra) from one specified vertex to another specified vertex in a graph]]
* [[CPP/Boost/BGL/BetweennessCentralityClustering|Cluster a graph using betweenness centrality]]

=== Visualization ===

* [[CPP/Boost/BGL/InvisibleEdges|Create a graph with invisible edges]]

=== Wish List ===
Examples in this section are either shells or something is wrong with them that must be fixed before they can graduate into real examples.

== Boost (Generic) Geometry Library ==
* [[CPP/Boost/Geometry/DistanceBetweenPoints|Compute the distance between two points]]
* [[CPP/Boost/Geometry/PointInPolygon|Determine if a point is inside of a polygon (within() function)]]
* [[CPP/Boost/Geometry/Simplify|Simplify a polyline]]

== Boost Math Library ==
=== Tools ===
* [[CPP/Boost/Math/Tools/TOMS749|TOMS748 root finding algorithm]]

Boost/BGL/CreateGraph

2011-06-12T07:03:49Z

Awallin: template params for adjacency_list

==CreateGraph.cpp==
<source lang="cpp">
#include <iostream> // for std::cout
#include <utility> // for std::pair
#include <algorithm> // for std::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS> Graph;

// up to 7 template parameters can be given, for example:
// typedef boost::adjacency_list< boost::listS, // out-edges stored in a std::list
// boost::vecS, // vertex set stored here
// boost::undirectedS, // bidirectional graph.
// boost::no_property, // vertex properties
// EdgeWeightProperty, // edge properties
// boost::no_property, // graph properties
// boost::listS // edge storage
// > graph_t;

int main(int,char*[])
{
// Construct a graph
Graph g(3); // 3 vertices

add_edge(0, 1, g);
add_edge(1, 2, g);

// Get the vertices
typedef boost::property_map<Graph, boost::vertex_index_t>::type IndexMap;

// "Ask a question" of a graph. The IndexMap is the solution set.
IndexMap index = get(boost::vertex_index, g);

std::cout << "vertices = ";
typedef boost::graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vertexPair;
// The call to vertices(g) sets vp to (0, numberOfElements)
// The loop, therefore, starts at 0, and increments the 'first' of the vertexPair
// until it equals the 'second', which again is the numberOfElements.
for (vertexPair = vertices(g); vertexPair.first != vertexPair.second; ++vertexPair.first)
{
// You can see what is going on with this:
//std::cout << "first: " << index[*vertexPair.first] << " second: " << index[*vp.second] << std::endl; // the vertex iterator

// Or just output the vertex ids
std::cout << index[*vertexPair.first] << " ";
}
std::cout << std::endl;

std::cout << "edges = ";
typedef boost::graph_traits<Graph>::edge_iterator edge_iter;
std::pair<edge_iter, edge_iter> edgePair;
for(edgePair = edges(g); edgePair.first != edgePair.second; ++edgePair.first)
{
std::cout << "(" << index[source(*edgePair.first, g)]
<< "," << index[target(*edgePair.first, g)] << ") ";
}
std::cout << std::endl;
return 0;
}

</source>

==CMakeLists.txt==
<source lang="cmake">
cmake_minimum_required(VERSION 2.6)

Project(ConstructGraph)

set(Boost_USE_MULTITHREADED ON)
FIND_PACKAGE(Boost 1.38 COMPONENTS required)

INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${Boost_INCLUDE_DIRS})
LINK_DIRECTORIES(${LINK_DIRECTORIES} ${Boost_LIBRARY_DIRS})

ADD_EXECUTABLE(ConstructGraph ConstructGraph.cpp)
target_link_libraries(ConstructGraph)

</source>

Boost/BGL/BundledProperties

2011-06-11T21:53:28Z

Awallin: with bundled properties, using operator[] is more elegant (?)

==BundledProperties.cpp==
<source lang="cpp">
#include <iostream>
#include <boost/graph/adjacency_list.hpp>

// Create a struct to hold several properties
struct MyProperty
{
int MyIntProperty;
std::string MyStringProperty;
};

// Define the type of the graph - this specifies a bundled property for vertices
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, MyProperty> Graph;

// Define the type of the graph - this specifies a bundled property for edges
//typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, MyProperty> Graph;

int main(int,char*[])
{
// Create a graph object
Graph g(2);

boost::property_map<Graph, int MyProperty::*>::type MyIntPropertyMap = boost::get(&MyProperty::MyIntProperty, g);
boost::put(MyIntPropertyMap, 0, 5);
boost::put(MyIntPropertyMap, 1, 10);

boost::property_map<Graph, std::string MyProperty::*>::type MyStringPropertyMap = boost::get(&MyProperty::MyStringProperty, g);
boost::put(MyStringPropertyMap, 0, "TestName0");
boost::put(MyStringPropertyMap, 1, "TestName1");

// NOTE: the above code is equivalent to the slightly more elegant:
// g[0].MyIntProperty = 5
// g[1].MyIntProperty = 10
// g[0].MyStringProperty = "TestName0"
// g[1].MyStringProperty = "TestName1"

typedef boost::property_map<Graph, boost::vertex_index_t>::type IndexMap;
IndexMap index = get(boost::vertex_index, g);

typedef boost::graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vertexPair;
for (vertexPair = vertices(g); vertexPair.first != vertexPair.second; ++vertexPair.first)
{
std::cout << index[*vertexPair.first] << " : " << MyIntPropertyMap[*vertexPair.first] << " : " << MyStringPropertyMap[*vertexPair.first] << std::endl;
}

return 0;
}

</source>

==CMakeLists.txt==
<source lang="cmake">
cmake_minimum_required(VERSION 2.6)

Project(BundledProperties)

set(Boost_USE_MULTITHREADED ON)
FIND_PACKAGE(Boost 1.38 COMPONENTS required)

INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${Boost_INCLUDE_DIRS})
LINK_DIRECTORIES(${LINK_DIRECTORIES} ${Boost_LIBRARY_DIRS})

ADD_EXECUTABLE(BundledProperties BundledProperties.cpp)
target_link_libraries(BundledProperties)

</source>

Boost/BGL/Directed/Weighted

2011-06-11T21:49:06Z

Awallin: 3rd method using boost::get

==Edge.cpp==
<source lang="cpp">
#include <iostream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/directed_graph.hpp>

typedef boost::property<boost::edge_weight_t, float> EdgeWeightProperty;

typedef boost::directed_graph<boost::no_property, EdgeWeightProperty> Graph;

int main(int,char*[])
{
// Create a graph object
Graph g;

// Add vertices to the graph
Graph::vertex_descriptor v0 = g.add_vertex();
Graph::vertex_descriptor v1 = g.add_vertex();
Graph::vertex_descriptor v2 = g.add_vertex();

// Create weighted edges
EdgeWeightProperty weight0 = 5;
boost::add_edge(v0,v1,weight0,g);

EdgeWeightProperty weight1 = 6;
boost::add_edge(v1,v2,weight1,g);

// Retrieve the weight of an edge (method 1, works)
{
typedef boost::property_map<Graph, boost::edge_weight_t>::type EdgeWeightMap;
EdgeWeightMap edgeWeightMap = get(boost::edge_weight, g);

std::pair<Graph::edge_descriptor, bool> edgePair = boost::edge(v0, v1, g);
Graph::edge_descriptor edge = edgePair.first;

std::cout << "Edge (" << v0 << ", " << v1 << ") has weight " << edgeWeightMap[edge] << std::endl;
}

// Retrieve the weight of an edge (method 2, doesn't work)
{
std::pair<Graph::edge_descriptor, bool> edgePair = boost::edge(v0, v1, g);
Graph::edge_descriptor edge = edgePair.first;
std::cout << "Edge (" << v0 << ", " << v1 << ") has weight " << g[edge]->edge_weight << std::endl;
}

// method 3
std::cout << std::cout << "Edge (" << v0 << ", " << v1 << ") has weight " << boost::get( boost::edge_weight, g, edge ) << std::endl;

return 0;
}

</source>

==CMakeLists.txt==
<source lang="cmake">
cmake_minimum_required(VERSION 2.6)

Project(Weighted)

set(Boost_USE_MULTITHREADED ON)
FIND_PACKAGE(Boost 1.38 COMPONENTS required)

INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${Boost_INCLUDE_DIRS})
LINK_DIRECTORIES(${LINK_DIRECTORIES} ${Boost_LIBRARY_DIRS})

ADD_EXECUTABLE(Weighted Weighted.cpp)

</source>