graphs.hpp File Reference

Graph/flow-graph type aliases, subgraph/component helpers, and demo graph generators used by cunningham.hpp. More...

#include <cmath>
#include <map>
#include <random>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/filtered_graph.hpp>

Include dependency graph for graphs.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	discrete_modulus::NonCriticalEdge
	Edge filter selecting edges not in a given critical/tight set. More...

Namespaces
namespace	discrete_modulus

Typedefs
using	discrete_modulus::Traits = adjacency_list_traits< vecS, vecS, undirectedS >
	Traits for Graph.
using	discrete_modulus::Graph = adjacency_list< vecS, vecS, undirectedS, property< vertex_name_t, Traits::vertex_descriptor >, property< edge_index_t, int, property< edge_weight_t, long > > >
	The undirected graph type used throughout this library.
using	discrete_modulus::Vertex = graph_traits< Graph >::vertex_descriptor
using	discrete_modulus::Edge = graph_traits< Graph >::edge_descriptor
using	discrete_modulus::VertexIterator = graph_traits< Graph >::vertex_iterator
using	discrete_modulus::EdgeIterator = graph_traits< Graph >::edge_iterator
using	discrete_modulus::FlowTraits = adjacency_list_traits< vecS, vecS, directedS >
	Traits for FlowGraph.
using	discrete_modulus::FlowVertex = FlowTraits::vertex_descriptor
using	discrete_modulus::FlowEdge = FlowTraits::edge_descriptor
using	discrete_modulus::FlowGraph = adjacency_list< vecS, vecS, directedS, no_property, property< edge_capacity_t, long, property< edge_residual_capacity_t, long, property< edge_reverse_t, FlowTraits::edge_descriptor > > > >
	The directed, capacitated graph type used for the max-flow subproblem in Cunningham's algorithm (see create_flow_graph in cunningham.hpp). edge_reverse records, for every directed edge, its paired reverse-residual edge, as required by boost::push_relabel_max_flow.

Functions
template<typename G >
Graph	discrete_modulus::subgraph (const G &g, std::vector< Vertex > v)
	Builds the subgraph of g induced by the given vertices.
template<typename G >
std::vector< Graph >	discrete_modulus::connected_component_graphs (const G &g)
	Splits g into one Graph per connected component.
std::vector< Graph >	discrete_modulus::induced_components (Graph &g, const std::set< Edge > &A)
	Splits g into connected components after removing the critical edge set A.
template<typename G >
bool	discrete_modulus::is_simple_graph (const G &g)
	Checks whether g is a simple graph: no self-loops, no parallel edges between the same pair of vertices.
Graph	discrete_modulus::cycle_plus_triangle (int n)
	A cycle on n vertices plus one extra chord (between vertices 1 and n-1).
Graph	discrete_modulus::complete_graph (int n)
	The complete graph on n vertices.
Graph	discrete_modulus::wheel_graph (int n)
	The wheel graph: a cycle on n-1 vertices plus one hub vertex n-1.
Graph	discrete_modulus::growing_multipartite (int n_layers)
	A multipartite graph with growing layer sizes (1, 2, ..., n_layers) and complete bipartite connections between consecutive layers.
Graph	discrete_modulus::complete_plus_triangle (int n)
	The complete graph on n-1 vertices, plus one extra vertex attached to two of them.
Graph	discrete_modulus::permuted_graph (const Graph &g, const std::vector< int > &perm)
	g with vertices relabeled according to perm.
Graph	discrete_modulus::disconnected_graph ()
	Two disjoint triangles: a minimal example of a disconnected graph.
Graph	discrete_modulus::random_gnp_graph (int n, double p, int seed)
	An Erdos-Renyi G(n,p) random graph.
Graph	discrete_modulus::random_geometric_graph (int n, double r, int seed=381928)
	A random geometric graph: n uniform points in the unit square, connected within radius r.

Detailed Description

Graph/flow-graph type aliases, subgraph/component helpers, and demo graph generators used by cunningham.hpp.