First, create a graph which looks like the following:
0 1 2 3 4 .----------- 0 | 0 2 1 | \ / | 2 | 1 | 3 | \ | 4 | 3-4
First we need to add vertices:
util::graph g; for (unsigned i = 0; i < 5; ++i) g.add_vertex(); // Add vertex 'i';
Finally, populate the graph with edges:
g.add_edge(0, 1); // Associated to edge 0. g.add_edge(1, 2); // Associated to edge 1. g.add_edge(1, 3); // Associated to edge 2. g.add_edge(3, 4); // Associated to edge 3. g.add_edge(4, 2); // Associated to edge 4.
Now there is a graph topology and we want to associate elements of this graph to a site in the image. The idea is to use specific site sets such as p_vertices and p_edges. Let’s associate the vertices with sites. To do so we need a function which maps a vertex id to a site, e.g. a point2d here.
typedef fun::i2v::array<point2d> F; F f(5); // We need to map 5 vertices. f(0) = point2d(0, 0); f(1) = point2d(2, 2); f(2) = point2d(0, 4); f(3) = point2d(4, 3); f(4) = point2d(4, 4);
Then declare a p_vertices:
typedef p_vertices<util::graph, F> pv_t;
pv_t pv(g, f);
Thanks to the p_vertices there is now a mapping between vertices and sites. We may want to map data to it. The idea is to provide a function which returns the associated data according to the site given as parameter. Combining this function and the p_vertices, we get an image which can be used with algorithms and for_all loops.
template <typename S> struct viota_t : public mln::Function_v2v< viota_t<S> > { typedef unsigned result; viota_t(unsigned size) { v_.resize(size); for(unsigned i = 0; i < size; ++i) v_[i] = 10 + i; } unsigned operator()(const mln_psite(S)& p) const { return v_[p.v().id()]; } protected: std::vector<result> v_; };
// Constructs an image viota_t<pv_t> viota(pv.nsites()); mln_VAR(graph_vertices_ima, viota | pv); //Prints each vertex and its associated data. mln_piter_(graph_vertices_ima_t) p(graph_vertices_ima.domain()); for_all(p) std::cout << "graph_vertices_ima(" << p << ") = " << graph_vertices_ima(p) << std::endl;
Output:
graph_vertices_ima((0,0)) = 10 graph_vertices_ima((2,2)) = 11 graph_vertices_ima((0,4)) = 12 graph_vertices_ima((4,3)) = 13 graph_vertices_ima((4,4)) = 14
Note that like any image in Olena, graph images share their data. Therefore, while constructing a graph image from a graph and a function, the graph is not copied and this is NOT a costly operation.
Of course, creating a graph image is not necessary and you can work directly with the graph and container/function mapping sites and data.
// Function which maps sites to data. viota_t viota(g.v_nmax()); // Iterator on vertices. mln_vertex_iter_(util::graph) v(g); // Prints each vertex and its associated value. for_all(v) std::cout << v << " : " << viota(v) << std::endl;
0 : 10 1 : 11 2 : 12 3 : 13 4 : 14
Graphs have iterators like any other site sets and also provide specific iterators in order to iterate over graphs in a more intuitive way.
Iteration over the adjacent edges of all the vertices:
// Iterator on vertices. mln_vertex_iter_(util::graph) v(g); // Iterator on v's edges. mln_vertex_nbh_edge_iter_(util::graph) e(v); // Prints the graph // List all edges for each vertex. for_all(v) { std::cout << v << " : "; for_all(e) std::cout << e << " "; std::cout << std::endl; }
0 : (0,1) 1 : (0,1) (1,2) (1,3) 2 : (1,2) (2,4) 3 : (1,3) (3,4) 4 : (3,4) (2,4)
Iteration over the adjacent edges of all the edges:
// Iterator on edges. mln_edge_iter_(util::graph) e(g); // Iterator on edges adjacent to e. mln_edge_nbh_edge_iter_(util::graph) ne(e); // Prints the graph // List all adjacent edges for each edge. for_all(e) { std::cout << e << " : "; for_all(ne) std::cout << ne << " "; std::cout << std::endl; }
(0,1) : (1,2) (1,3) (1,2) : (0,1) (1,3) (2,4) (1,3) : (0,1) (1,2) (3,4) (3,4) : (1,3) (2,4) (2,4) : (1,2) (3,4)
Iteration over the adjacent vertices of all the vertices:
// Iterator on vertices. mln_vertex_iter_(util::graph) v(g); // Iterator on vertices adjacent to v. mln_vertex_nbh_vertex_iter_(util::graph) nv(v); // Prints the graph // List all adjacent edges for each edge. for_all(v) { std::cout << v << " : "; for_all(nv) std::cout << nv << " "; std::cout << std::endl; }
0 : 1 1 : 0 2 3 2 : 1 4 3 : 1 4 4 : 3 2