Class graph::Graph

Graph representation as a collection of nodes and edges.

It assumes that:

  • nodes are identified with a NodeId 0..(N-1) and
  • edges are identified with an EdgeId 0..(M-1),

where N (M) is the number of nodes (edges). This is a concurrent adjacency list AND edge list representation of the graph (slightly slower than using a single representation, but more versatile).

Note

We use a templated approach such that the accessors for nodes and edges can return the actual type rather than a limited base class view of it. Repetition of a node_id in an edge is explicitly allowed and implies a duplication of the corresponding edge_id in the node. This can be used for, e.g., squared terms in a cost function represented as a graph. Hoewever, this approach is not efficient for very high order terms.

Inheritance
utils::Component
graph::Graph
Inherited Members

Constructors

Graph()

Declaration
graph::Graph<Edge, Node>::Graph()

Methods

set_allow_dup_merge()

Declaration
void graph::Graph<Edge, Node>::set_allow_dup_merge(bool value)

get_const_cost()

Declaration
double graph::Graph<Edge, Node>::get_const_cost() const

is_empty()

Declaration
bool graph::Graph<Edge, Node>::is_empty() const

node()

Get a node by NodeId.

Declaration
const Node&graph::Graph<Edge, Node>::node(size_t node_indx) const

nodes()

Access the vector of all edges.

Declaration
const std::vector<Node>&graph::Graph<Edge, Node>::nodes() const

edge()

Get an edge by EdgeId.

Declaration
const Edge&graph::Graph<Edge, Node>::edge(size_t edge_id) const

edges()

Access the vector of all edges.

Declaration
const std::vector<Edge>&graph::Graph<Edge, Node>::edges() const

sort()

Sort each node and edge.

This invokes sort_edge_ids() and sort_node_ids() on all nodes and edges, respectively. It does NOT modify the order of the nodes and edges in the graph (i.e., the node_ids and edge_ids are stable under this operation). The order in which nodes are listed in each edge (and vice-versa) should not matter for the typical application (and can be unsorted either from intial input or from calls to {add,remove}_{node,edge}). This functionality is provided in case an implementation relies on either ascending order or being able to identify repetitions easily. Node::sort_edge_ids

Edge::sort_node_ids

Declaration
virtual void graph::Graph<Edge, Node>::sort()

validate()

Validate the Graph.

Ensure that Nodes, Edges and their references are consistent. validate_edge

validate_node

validate_counts

Declaration
virtual bool graph::Graph<Edge, Node>::validate() const

validate_node()

Validate a Node

Ensure that

  • the Node participates in at least one Edge,
  • all edges listed have a valid edge_ids, and
  • the Node is referenced in those Edges.
Declaration
virtual bool graph::Graph<Edge, Node>::validate_node(int node_indx) const

validate_edge()

Validate an Edge

Ensure that

  • the Edge includes at least one Node,
  • all nodes listed have a valid edge_ids, and
  • the node is referenced in those Edges.
Declaration
virtual bool graph::Graph<Edge, Node>::validate_edge(size_t edge_id) const

validate_counts()

Declaration
virtual bool graph::Graph<Edge, Node>::validate_counts(int node_id, size_t edge_id) const

configure()

Configure the graph by configuring its components.

{
  "terms": [...],
  "variables": [...],
}
Note

The group name terms is a side effect of the cost_function input format.

Declaration
void graph::Graph<Edge, Node>::configure(const utils::Json&json) override

configure()

Declaration
void graph::Graph<Edge, Node>::configure(Configuration_T&config)

render()

render the object in structured form

Return a structured representation of the object. This is intended for output purposes. For instance, the solution your solver finds should have a render method which allows it to be returned as part of the result. Example:

{c++}
 MySolution : public Component {
  public:
   // Represent the internal bool vector as +-1 output.
   utils::Structure render() const override {
     utils::Structure rendered;
     for (bool item : solution_) rendered.push_back(item ? 1 : -1);
     return rendered;
   }

  private:
   std::vector<bool> solution_;
 }

 MySolution solution;
 std::cout << solution.render().to_string() << std::endl;

utils::Structure

Declaration
utils::Structure graph::Graph<Edge, Node>::render() const override

map_output()

Declaration
int graph::Graph<Edge, Node>::map_output(int internal_id) const

output_map()

Declaration
const std::map<int, int>&graph::Graph<Edge, Node>::output_map() const

nodes_size()

Declaration
size_t graph::Graph<Edge, Node>::nodes_size() const

edges_size()

Declaration
size_t graph::Graph<Edge, Node>::edges_size() const

get_locality()

Declaration
uint32_t graph::Graph<Edge, Node>::get_locality() const

get_min_locality()

Declaration
uint32_t graph::Graph<Edge, Node>::get_min_locality() const

get_avg_locality()

Declaration
double graph::Graph<Edge, Node>::get_avg_locality() const

get_accumulated_dependent_vars()

Declaration
uint64_t graph::Graph<Edge, Node>::get_accumulated_dependent_vars() const

get_max_coupling_magnitude()

Declaration
double graph::Graph<Edge, Node>::get_max_coupling_magnitude() const

get_min_coupling_magnitude()

Declaration
double graph::Graph<Edge, Node>::get_min_coupling_magnitude() const

get_sum_coefficient_degrees_total()

Declaration
uint64_t graph::Graph<Edge, Node>::get_sum_coefficient_degrees_total() const

get_scale_factor()

Declaration
double graph::Graph<Edge, Node>::get_scale_factor() const

is_rescaled()

Declaration
bool graph::Graph<Edge, Node>::is_rescaled() const

get_properties()

Declaration
const GraphProperties&graph::Graph<Edge, Node>::get_properties() const

rescale()

Declaration
void graph::Graph<Edge, Node>::rescale()

estimate_max_cost_diff()

Declaration
double graph::Graph<Edge, Node>::estimate_max_cost_diff() const

get_node_name_to_id_map()

Declaration
const std::map<int, int>&graph::Graph<Edge, Node>::get_node_name_to_id_map() const

populate_node_edge_ids()

Build the adjacency list from the edge list.

This is used when the graph input is represented solely as an edge list to infer the corresponding adjacencly list representation.

Declaration
void graph::Graph<Edge, Node>::populate_node_edge_ids()

configure_memory_check()

Declaration
void graph::Graph<Edge, Node>::configure_memory_check(const utils::Json&json)

init_memory_check()

Declaration
void graph::Graph<Edge, Node>::init_memory_check()

init()

Declaration
void graph::Graph<Edge, Node>::init()