Right off the bat it seems obvious to me that your datastructure represent a graph (with attributed vertices and edges connecting them).
Furthermore when you say "These relations are stored on a matrix." you apparently mean "I visualize this as a matrix", since a true matrix representation¹ would become horrifically space-inefficient for larger number of vertices and sparse edge coverage.
Boost has a library for that: Boost Graph Library (BGL)
If we assume you want to be able to read a graph like²
graph X {
element1; element12; element166; element1780; element3; element4;
element45 -- element3 [ label="[3,1;1,4]" ];
element45 -- element12 [ label="[1,1;1,1]" ];
element45 -- element1780 [ label="[8,1;1,4]" ];
element1661 -- element1 [ label="[1,1;1,9]" ];
element1661 -- element3 [ label="[3,1;6,4]" ];
element1661 -- element1780 [ label="[8,1;1,1]" ];
}
Into a BGL compatible model, use typedefs like e.g.:
struct Vertex {
std::string node_id;
};
struct Edge {
Box box;
};
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Vertex, Edge>;
Now you leverage the full facilities of the BGL:
Reading the graph from a file
Reading from a graphviz file is a feature³:
std::ifstream ifs("input.txt");
Graph result;
boost::dynamic_properties dp;
dp.property("node_id", boost::get(&Vertex::node_id, result));
dp.property("label", boost::get(&Edge::box, result));
read_graphviz(ifs, result, dp);
Manipulating the graph
The many algorithms (dijkstra, flow, spanning trees, connected components, etc.) are at your disposal. Or you can mix and match. For example let's filter the nodes that have no connections out:
struct Filter {
Graph const* _g;
bool operator()(Graph::vertex_descriptor v) const {
return boost::size(boost::adjacent_vertices(v, *_g))>0;
}
template <typename T>
bool operator()(T&&) const { return true; /*catch-all*/ }
};
using Filtered = filtered_graph<Graph, Filter, Filter>;
Filter filter { &graph };
Filtered filtered(graph, filter, filter);
Let's write it to graphviz again:
boost::dynamic_properties dp;
dp.property("node_id", boost::get(&Vertex::node_id, filtered));
dp.property("label", boost::get(&Edge::box, filtered));
write_graphviz_dp(std::cout, filtered, dp);
DEMO TIME
The full demo takes your input graph:
And filters it into:
Full Code
Live On Coliru
// http://stackoverflow.com/questions/32279268/using-two-objects-as-hash-key-for-an-unordered-map-or-alternatives
#include <cassert>
#include <iostream>
template <typename T> struct BasicBox {
struct Point { T x, y; };
Point tl, br;
friend std::ostream& operator<<(std::ostream& os, Point const& p) { return os << p.x << ',' << p.y; }
friend std::ostream& operator<<(std::ostream& os, BasicBox const& b) { return os << '[' << b.tl << ';' << b.br << ']'; }
friend std::istream& operator>>(std::istream& is, Point& p) {
char comma;
if (!(is >> p.x >> comma >> p.y) && (comma == ',')) {
is.setstate(std::ios::failbit | is.rdstate());
}
return is;
}
friend std::istream& operator>>(std::istream& is, BasicBox& b) {
char lbrace, semi, rbrace;
if (!(
(is >> lbrace >> b.tl >> semi >> b.br >> rbrace) &&
(lbrace == '[' && semi == ';' && rbrace == ']')
)) {
is.setstate(std::ios::failbit | is.rdstate());
}
return is;
}
};
using Box = BasicBox<int>;
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <libs/graph/src/read_graphviz_new.cpp>
struct Vertex {
std::string node_id;
};
struct Edge {
Box box;
};
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Vertex, Edge>;
#include <fstream>
#include <boost/graph/filtered_graph.hpp>
struct Filter {
Graph const* _g;
bool operator()(Graph::vertex_descriptor v) const {
return boost::size(boost::adjacent_vertices(v, *_g))>0;
}
template <typename T>
bool operator()(T&&) const { return true; /*catch-all*/ }
};
int main() {
using namespace boost;
Graph const graph = []{
std::ifstream ifs("input.txt");
Graph result;
boost::dynamic_properties dp;
dp.property("node_id", boost::get(&Vertex::node_id, result));
dp.property("label", boost::get(&Edge::box, result));
read_graphviz(ifs, result, dp);
return result;
}();
// let's do some random task. Like. You know. Like... Filter out the unconnected nodes
using Filtered = filtered_graph<Graph, Filter, Filter>;
Filter filter { &graph };
Filtered filtered(graph, filter, filter);
boost::dynamic_properties dp;
dp.property("node_id", boost::get(&Vertex::node_id, filtered));
dp.property("label", boost::get(&Edge::box, filtered));
write_graphviz_dp(std::cout, filtered, dp);
}
¹ like e.g. BGL's AdjacencyMatrix
² the format chosen being Graphviz' DOT format: http://www.graphviz.org/
³ Of course you can also use Boost Serialization with BGL models, so you can opt for a more compact binary representation e.g.
