Generate Edge Intersection Graph

Header: fiction/physical_design/generate_edge_intersection_graph.hpp

using fiction::physical_design::edge_intersection_graph = undirected_graph<std::size_t, layout_coordinate_path, undirected_pair<std::size_t>, std::size_t>

Define an edge_intersection_graph as an undirected graph of layout_coordinate_path elements assigned to its nodes. Each node (vertex) is identified via a unique ID whereas each edge is an undirected pair of such IDs. Since the implementation demands it, each edge, additionally, is associated with a data field that represents its ID.

struct generate_edge_intersection_graph_params

Parameters for the edge intersection graph generation algorithm.

Public Members

bool crossings = false

Allow crossings by not creating edges between paths that only share single-coordinate sub-paths.

std::optional<uint32_t> path_limit = std::nullopt

If a value is given, for each objective, only up to the path_limit shortest paths will be enumerated (using Yen’s algorithm) instead of all paths.

struct generate_edge_intersection_graph_stats

Statistics for edge intersection graph generation.

Public Members

mockturtle::stopwatch::duration time_total = {0}

Runtime measurement.

std::size_t number_of_unroutable_objectives = {0}

For each routing objective that cannot be fulfilled in the given layout, this counter is incremented.

std::vector<std::vector<std::size_t>> cliques = {}

Stores all cliques in the resulting graph that were created during path enumeration. There might be more cliques in the overall graph but these ones correspond to one routing objective each, which could be useful information to have in certain algorithms.

std::vector<std::size_t> objective_indices = {}

Routing objective index for each vertex ID.

std::size_t num_vertices

Number of vertices in the intersection graph.

std::size_t num_edges

Number of edges in the intersection graph.

template<typename Lyt>
edge_intersection_graph fiction::physical_design::generate_edge_intersection_graph(const Lyt &lyt, const std::vector<routing_objective> &objectives, generate_edge_intersection_graph_params ps = {}, generate_edge_intersection_graph_stats *pst = nullptr)

Creates an edge intersection graph of all paths that satisfy a given list of routing objectives. That is, this function generates an undirected graph whose nodes represent paths in the given layout and whose edges represent intersections of these paths. An intersection is understood as the non-disjunction of paths, i.e., they share at least one coordinate. To generate the paths for the routing objectives, all possible paths from source to target in the layout are enumerated while taking obstructions into consideration. The given layout must be clocked.

Template Parameters:

Lyt – Type of the clocked layout.

Parameters:

• lyt – The layout to generate the edge intersection graph for.

• objectives – Source coordinates and indexed destination inputs.

• ps – Parameters.

• pst – Statistics.

Returns:

An edge intersection graph of paths satisfying the given routing objectives in lyt.