Skip to content
Snippets Groups Projects
graph.cpp 1.18 KiB
Newer Older
#include <gp-bnb/graph.hpp>

p-hamann's avatar
p-hamann committed
graph::graph(std::vector<std::vector<unsigned int>> a) : nodes_(a.size()), adjacency_list_(a), indexed_edges_(a) {
	// indexes the edges
p-hamann's avatar
p-hamann committed
	std::vector<std::pair<node_id,node_id>> edge_list;
p-hamann's avatar
p-hamann committed
	for (node_id u = 1; u <= nodes_; u++) {
p-hamann's avatar
p-hamann committed
		for (node_id v : get_adjacency(u)) {			
            if (u < v) {
p-hamann's avatar
p-hamann committed
                edge_list.push_back(std::make_pair(u,v));
p-hamann's avatar
p-hamann committed
	
	edges_ = edge_list.size();

	for (edge_id e = 1; e <= edges_; e++) {
		node_id u = edge_list[e-1].first;
		node_id v = edge_list[e-1].second;
		const std::vector<node_id>& u_neighbors = get_adjacency(u);
		const std::vector<node_id>& v_neighbors = get_adjacency(v);
		for (unsigned int i = 0; i < u_neighbors.size(); i++) {
			if (u_neighbors[i] == v) {
				indexed_edges_[u-1][i] = e;
				break;
			}
		}
		for (unsigned int i = 0; i < v_neighbors.size(); i++) {
			if (v_neighbors[i] == u) {
				indexed_edges_[v-1][i] = e;
				break;
			}
		}
	}
p-hamann's avatar
p-hamann committed
edge_id graph::get_edge_id(node_id u, node_id v) const {
p-hamann's avatar
p-hamann committed
	const std::vector<node_id>& neighbors = get_adjacency(u);
	for (unsigned int i = 0; i < neighbors.size(); ++i) {
		if (neighbors[i] == v) return indexed_edges_[u-1][i];
	}
	return 0;
}