OKlibrary  0.2.1.6
OrthogonalTriples.cpp File Reference

Handling orthogonal triples in 3-dimensional Euclidean space. More...

#include <utility>
#include <vector>
#include <iostream>
#include <limits>
#include <cassert>
#include <cstdlib>
#include <tr1/array>
#include <boost/rational.hpp>
#include <boost/range/distance.hpp>
#include <boost/range/size_type.hpp>
#include <boost/range/const_iterator.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/utility.hpp>
#include <boost/numeric/ublas/vector.hpp>
#include <boost/numeric/ublas/io.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/property_map/property_map.hpp>

Go to the source code of this file.

Classes

class  SAT_translation< Graph >
 Creating a CNF in DIMACS format encoding the 101-colouring conditions. More...

Typedefs

typedef
boost::numeric::ublas::vector
< double > 
vector_type
typedef std::vector< vector_typevector2_type
typedef std::vector< unsigned int > Hyperedge
typedef std::vector< HyperedgeHypergraph
typedef boost::adjacency_list
< boost::listS, boost::vecS,
boost::undirectedS > 
UndirectedGraph
typedef
boost::adjacency_matrix
< boost::undirectedS,
boost::no_property,
boost::property
< boost::edge_index_t, bool > > 
UndirectedGraphM

Functions

template<class Vector >
void vector_product (Vector &p, const Vector &a, const Vector &b)
template<class Vector >
Vector vector_product (const Vector &a, const Vector &b)
template<class Vector >
bool orthogonal (const Vector &a, const Vector &b)
bool read (vector2_type &ev)
template<class Graph >
void output_graph (const Graph &g)
template<class Graph , class EliminatedEdges , class Hypergraph >
void output_remaining_edges (const Graph &g, const EliminatedEdges &map, const Hypergraph &G)
template<class Hypergraph >
void output_hypergraph (const Hypergraph &G)
template<class Graph , class Range >
Graph orthogonality_relation (const Range &r)
 The function for computing the orthogonality graph.
template<class AdjacencyGraph , class Hypergraph , class EdgeContained >
void extract_triangles (const AdjacencyGraph &g, Hypergraph &hg, EdgeContained &map)
 The function for extracting all orthogonal triples.
template<class MatrixGraph , class ListGraph >
MatrixGraph adapt (const ListGraph &g)
 Copying a graph.
int main ()

Detailed Description

Handling orthogonal triples in 3-dimensional Euclidean space.

Reads from standard input a list of vectors in 3-dimensional space (first entry the number of vectors, then triplets for each vector; everything space-separated), and outputs

  • first the graph, whose vertices are the vectors, joined by an edge if they are orthogonal
  • then all orthogonal triplets
  • followed by those edges not contained in some triplet
  • and finally the SAT-encoding (DIMACS) of assigning boolean values to the vertices so that every triplet has exactly 2 ones, while in no remaining edge we have 2 zeros.

Definition in file OrthogonalTriples.cpp.


Typedef Documentation

typedef std::vector<unsigned int> Hyperedge

Definition at line 259 of file OrthogonalTriples.cpp.

typedef std::vector<Hyperedge> Hypergraph

Definition at line 260 of file OrthogonalTriples.cpp.

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> UndirectedGraph

Definition at line 262 of file OrthogonalTriples.cpp.

typedef boost::adjacency_matrix<boost::undirectedS, boost::no_property, boost::property<boost::edge_index_t, bool> > UndirectedGraphM

Definition at line 263 of file OrthogonalTriples.cpp.

typedef std::vector<vector_type> vector2_type

Definition at line 70 of file OrthogonalTriples.cpp.

typedef boost::numeric::ublas::vector<double> vector_type

Definition at line 69 of file OrthogonalTriples.cpp.


Function Documentation

template<class MatrixGraph , class ListGraph >
MatrixGraph adapt ( const ListGraph &  g)

Copying a graph.

Definition at line 246 of file OrthogonalTriples.cpp.

template<class AdjacencyGraph , class Hypergraph , class EdgeContained >
void extract_triangles ( const AdjacencyGraph &  g,
Hypergraph hg,
EdgeContained &  map 
)

The function for extracting all orthogonal triples.

Definition at line 218 of file OrthogonalTriples.cpp.

References H.

Referenced by main().

template<class Vector >
bool orthogonal ( const Vector &  a,
const Vector &  b 
) [inline]

Definition at line 61 of file OrthogonalTriples.cpp.

Referenced by orthogonality_relation().

template<class Graph , class Range >
Graph orthogonality_relation ( const Range &  r) [inline]

The function for computing the orthogonality graph.

Definition at line 192 of file OrthogonalTriples.cpp.

References end, and orthogonal().

template<class Graph >
void output_graph ( const Graph &  g)

Definition at line 89 of file OrthogonalTriples.cpp.

Referenced by main().

template<class Hypergraph >
void output_hypergraph ( const Hypergraph G)

Definition at line 116 of file OrthogonalTriples.cpp.

References Latex_Handler::begin(), and end.

Referenced by main().

template<class Graph , class EliminatedEdges , class Hypergraph >
void output_remaining_edges ( const Graph &  g,
const EliminatedEdges &  map,
const Hypergraph G 
)

Definition at line 98 of file OrthogonalTriples.cpp.

Referenced by main().

bool read ( vector2_type ev)

Definition at line 74 of file OrthogonalTriples.cpp.

Referenced by main(), and SystemHandling::System::operator()().

template<class Vector >
void vector_product ( Vector &  p,
const Vector &  a,
const Vector &  b 
) [inline]

Definition at line 45 of file OrthogonalTriples.cpp.

Referenced by vector_product().

template<class Vector >
Vector vector_product ( const Vector &  a,
const Vector &  b 
) [inline]

Definition at line 54 of file OrthogonalTriples.cpp.

References vector_product().