#include <cstdlib>#include <string>#include <vector>#include <queue>#include <algorithm>#include <cmath>#include <numeric>#include <iostream>#include <deque>#include "angel_exceptions.hpp"#include "angel_types.hpp"
Go to the source code of this file.
Namespaces | |
| namespace | angel |
Classes | |
| class | angel::write_vertex_op_t |
| class | angel::write_edge_op_t |
| class | angel::write_edge_bool_op_t |
| class | angel::write_edge_name_op_t |
| class | angel::write_face_op_t |
| class | angel::write_face_number_op_t |
| struct | angel::edge_equal_t< Ad_graph_t > |
| Compares edges of different graphs. More... | |
| struct | angel::edge_less_t< Ad_graph_t > |
| Compares edges of different graphs (lexicographically). More... | |
| class | angel::lex_less_face_line_t |
| class | angel::not_lex_less_face_line_t |
| struct | angel::dec_greater< vertex_t > |
| struct | angel::empty_operator_t< operand_t > |
| Empty operator class for dummy arguments. More... | |
Functions | |
| template<typename Ad_graph_t, typename Op_t> | |
| void | angel::for_all_edges (Ad_graph_t &adg, const Op_t &op) |
Applies op to all edges of adg, graph can be changed. | |
| template<typename Ad_graph_t, typename Op_t> | |
| void | angel::for_all_edges (const Ad_graph_t &adg, Op_t &op) |
Applies op to all edges of adg, op can be changed, e.g. for outputs. | |
| template<typename Ad_graph_t, typename Op_t> | |
| void | angel::for_all_in_edges (typename Ad_graph_t::vertex_descriptor v, Ad_graph_t &adg, const Op_t &op) |
Applies op to all in-edges of v, graph can be changed. | |
| template<typename Ad_graph_t, typename Op_t> | |
| void | angel::for_all_out_edges (typename Ad_graph_t::vertex_descriptor v, Ad_graph_t &adg, const Op_t &op) |
Applies op to all out-edges of v, graph can be changed. | |
| template<typename Ad_graph_t, typename Op_t> | |
| int | angel::sum_over_all_in_edges (typename Ad_graph_t::vertex_descriptor v, Ad_graph_t &adg, const Op_t &op) |
Applies op to all in-edges of v and sum it. | |
| template<typename Ad_graph_t, typename Op_t> | |
| int | angel::sum_over_all_out_edges (typename Ad_graph_t::vertex_descriptor v, const Ad_graph_t &adg, const Op_t &op) |
Applies op to all out-edges of v and sum it. | |
| template<typename Ad_graph_t> | |
| void | angel::successor_set (typename Ad_graph_t::vertex_descriptor v, const Ad_graph_t &adg, typename std::vector< typename Ad_graph_t::vertex_descriptor > &vec) |
Returns successor set of v as vector vec. | |
| template<typename Ad_graph_t> | |
| void | angel::sorted_successor_set (typename Ad_graph_t::vertex_descriptor v, const Ad_graph_t &adg, typename std::vector< typename Ad_graph_t::vertex_descriptor > &vec) |
Returns successor set of v as vector vec, vertices are sorted. | |
| template<typename Ad_graph_t> | |
| void | angel::predecessor_set (typename Ad_graph_t::vertex_descriptor v, const Ad_graph_t &adg, typename std::vector< typename Ad_graph_t::vertex_descriptor > &vec) |
Returns successor set of v as vector vec. | |
| template<typename Ad_graph_t> | |
| void | angel::sorted_predecessor_set (typename Ad_graph_t::vertex_descriptor v, const Ad_graph_t &adg, typename std::vector< typename Ad_graph_t::vertex_descriptor > &vec) |
Returns successor set of v as vector vec, vertices are sorted. | |
| bool | angel::reachable (const c_graph_t::vertex_t src, const c_graph_t::vertex_t tgt, c_graph_t &angelLCG) |
| Answers a reachability query from src to tgt. | |
| void | angel::vertex_upset (const c_graph_t::vertex_t v, const c_graph_t &angelLCG, vertex_set_t &upset) |
Returns a set of vertices in adg that depend on v. | |
| void | angel::vertex_downset (const c_graph_t::vertex_t v, const c_graph_t &angelLCG, vertex_set_t &downset) |
Returns a set of vertices in adg that v depends on. | |
| template<typename El_t> | |
| void | angel::unique_vector (std::vector< El_t > &v) |
| Sorts arbitrary vector and removes double elements. | |
| template<typename Ad_graph_t> | |
| void | angel::common_successors (typename Ad_graph_t::vertex_descriptor v, const Ad_graph_t &adg, typename std::vector< typename Ad_graph_t::vertex_descriptor > &vec) |
Returns set of vertices (in vec) that have common successors with v. | |
| template<typename Ad_graph_t> | |
| void | angel::same_successors (typename Ad_graph_t::vertex_descriptor v, const Ad_graph_t &adg, typename std::vector< typename Ad_graph_t::vertex_descriptor > &vec) |
Returns set of vertices (in vec) that have same successor set as v. | |
| template<typename Ad_graph_t> | |
| void | angel::common_predecessor (typename Ad_graph_t::vertex_descriptor v, const Ad_graph_t &adg, typename std::vector< typename Ad_graph_t::vertex_descriptor > &vec) |
Returns set of vertices (in vec) that have common predecessors with v. | |
| template<typename Ad_graph_t> | |
| void | angel::same_predecessors (typename Ad_graph_t::vertex_descriptor v, const Ad_graph_t &adg, typename std::vector< typename Ad_graph_t::vertex_descriptor > &vec) |
Returns set of vertices (in vec) that have same predecessor set as v. | |
| template<typename Ad_graph_t> | |
| void | angel::same_neighbors (typename Ad_graph_t::vertex_descriptor v, const Ad_graph_t &adg, typename std::vector< typename Ad_graph_t::vertex_descriptor > &vec) |
Returns set of vertices (in vec) that have same predecessor and successor set as v. | |
| template<typename It_t, typename Op_t> | |
| std::ostream & | angel::write_iterators (std::ostream &stream, const std::string &s, It_t begin, It_t end, Op_t op) |
| template<typename Ad_graph_t> | |
| graph_traits < Ad_graph_t > ::edge_iterator | angel::same_edge (typename Ad_graph_t::edge_descriptor e, const Ad_graph_t &g1, const Ad_graph_t &g2) |
| Returns same edge in another graph. | |
| template<typename Ad_graph_t> | |
| vertex_type_t | angel::vertex_type (typename Ad_graph_t::vertex_descriptor v, const Ad_graph_t &adg) |
| Functional equivalent for graph class method (more boost-like). | |
| template<typename Ad_graph_t> | |
| int | angel::count_parallel_edges (typename Ad_graph_t::edge_descriptor e, const Ad_graph_t &g) |
| c_graph_t::edge_t | angel::getEdge (unsigned int i, unsigned int j, const c_graph_t &angelLCG) |
Returns the edge in angelLCG that has source i and target j. | |
| bool | angel::lex_greater (c_graph_t::edge_t e1, c_graph_t::edge_t e2, const c_graph_t &cg) |
Returns whether e1 is lexicographically greater than e2 w.r.t. source and target. | |
| bool | angel::lex_less (c_graph_t::edge_t e1, c_graph_t::edge_t e2, const c_graph_t &cg) |
Returns whether e1 is lexicographically less than e2 w.r.t. source and target. | |
| bool | angel::inv_lex_greater (c_graph_t::edge_t e1, c_graph_t::edge_t e2, const c_graph_t &cg) |
Returns whether e1 is lexicographically greater than e2 w.r.t. target and source. | |
| bool | angel::inv_lex_less (c_graph_t::edge_t e1, c_graph_t::edge_t e2, const c_graph_t &cg) |
Returns whether e1 is lexicographically less than e2 w.r.t. target and source. | |
| bool | angel::lex_greater (edge_bool_t eb1, edge_bool_t eb2, const c_graph_t &cg) |
| bool | angel::lex_less (edge_bool_t eb1, edge_bool_t eb2, const c_graph_t &cg) |
| bool | angel::lex_less_face (line_graph_t::face_t e1, line_graph_t::face_t e2, const line_graph_t &lg) |
| int | angel::random (int min, int max) |
Random value between min and max, i.e. from [min, max]. | |
| double | angel::random (double n) |
| Random value from [0, n). | |
| int | angel::random (int n) |
| Random value between 0 and n-1, i.e. from [0, n). | |
| int | angel::random_high (int n, int exp=2) |
| Random value from [0, n) where larger values have higher probability (increases with exp). | |
| int | angel::random (const std::vector< double > &p) |
Random number characterized by p, the accumulated probabities. | |
| void | angel::in_out_path_lengths (const c_graph_t &cg, std::vector< int > &vni, std::vector< int > &vli, std::vector< int > &vno, std::vector< int > &vlo) |
| Returns for each vertex the number of paths and their overall length. | |
| bool | angel::find_edge (int s, int t, const line_graph_t &lg, std::vector< line_graph_t::edge_t > &ev) |
| Searches an edge in line graph that corresponds to (s,t). | |
| bool | angel::is_bipartite (const c_graph_t &cg) |
Tests if cg is bi-partite. | |
| bool | angel::is_tripartite (const line_graph_t &lg) |
Tests if lg is tri-partite. | |
| void | angel::number_dependent_vertices (const c_graph_t &cg, std::vector< int > &v) |
| Returns for each vertex how many dependent vertices depent on it. | |
| void | angel::number_independent_vertices (const c_graph_t &cg, std::vector< int > &v) |
| Returns for each vertex on how many independent vertices it depends. | |
| template<typename Ad_graph_t> | |
| void | angel::reachable_vertices (const Ad_graph_t &adg, std::vector< bool > &rv) |
| Computes all reachable vertices for c- and line graphs. | |
| template<typename Ad_graph_t> | |
| void | angel::relevant_vertices (const Ad_graph_t &adg, std::vector< bool > &rv) |
| Computes all relevant vertices for c- and line graphs. | |
| template<typename Neighbor_t> | |
| bool | angel::search_path (const std::vector< c_graph_t::vertex_t > &from, const std::vector< c_graph_t::vertex_t > &to, const Neighbor_t &n, std::vector< c_graph_t::vertex_t > &path, bool breadth_first=false) |
| template<typename Neighbor_t> | |
| int | angel::maximal_paths (c_graph_t::vertex_t v, const Neighbor_t &nin, std::vector< std::vector< c_graph_t::vertex_t > > &paths) |
| template<typename Neighbor_t> | |
| int | angel::minimal_in_out_degree (c_graph_t::vertex_t v, const Neighbor_t &nin) |
| void | angel::minimal_markowitz_degree (const c_graph_t &cg, std::vector< int > &v) |
| Minimal Markowitz degree for each vertex. | |
| int | angel::overall_minimal_markowitz_degree (const c_graph_t &cg) |
| Sum of minimal Markowitz degrees. | |
| void | angel::permutate_vertices (const c_graph_t &gin, const std::vector< c_graph_t::vertex_t > &p, c_graph_t &gout) |
Permutates vertices, vertex v in gin becomes p[v] in gout. | |
| void | angel::independent_vertices_to_front (const c_graph_t &gin, const std::vector< c_graph_t::vertex_t > &indeps, c_graph_t &gout) |
Independent vertices, given by indeps, becomes first vertices in gout. | |
| void | angel::put_unit_vertex_weight (line_graph_t &lg) |
| Sets all vertex labels (in ed) to 1. | |
| void | angel::put_unit_edge_weight (c_graph_t &cg) |
| Sets all edge labels (in ew) to 1. | |
| int | angel::renumber_edges (c_graph_t &cg) |
Renumber edges of cg continously, i.e. to [0..num_edges-1]. | |
| void | angel::take_over_successors (c_graph_t::vertex_t v1, c_graph_t::vertex_t v2, int offset, const c_graph_t &g1, int &edge_number, c_graph_t &g2) |
| template<typename Ad_graph_t> | |
| int | angel::remove_irrelevant_edges (typename Ad_graph_t::vertex_descriptor i, Ad_graph_t &adg, bool fast=false) |
Removes irrelevant edges from adg starting with i. | |
| template<typename Ad_graph_t> | |
| int | angel::remove_unreachable_edges (typename Ad_graph_t::vertex_descriptor i, Ad_graph_t &adg, bool fast=false) |
Removes unreachable edges from adg starting with i. | |
| template<typename Ad_graph_t> | |
| int | angel::remove_edges (typename Ad_graph_t::vertex_descriptor i, Ad_graph_t &adg) |
Removes irrelevant and unreachable edges from adg starting with i. | |
| int | angel::remove_hoisting_vertices (c_graph_t &cg) |
Removes all vertices with one predecessor and one successor from cg. | |
| void | angel::remove_parallel_edges (c_graph_t &cg) |
| Removes parallel edges. | |
| void | angel::remove_trivial_edges (c_graph_t &cg) |
| Eliminates all edges with label 1, front elimination is preferred. | |
| size_t | angel::block_begin (size_t i, size_t p, size_t n) |
First index in ith of p blocks where overall size is n (indices 0..n-1). | |
| double | angel::gen_prob () |
| Returns a random number between zero and one. | |
| unsigned int | angel::chooseTarget_sa (std::vector< double > &deltaE) |
Randomly chooses an index into the vector deltaE. | |
| int | angel::chooseEdgeElimRandomly (std::vector< double > &deltaE) |
| int | angel::chooseEdgeElimRandomlyGreedy (std::vector< double > &deltaE) |
1.5.3