Graphs and images

Description

Olena enables the possibility of using graphs with images. Graphs can help you to handle directly parts of an image and represent their relationship. Specific data can be associated to each vertex and/or edges.

Example

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;

Output:

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;
    }

Output:

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;
    }

Output:

(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;
    }

Output: