[boost] customizing complex data structures such as graphs and meshes

13 Mar 2008


      I discovered an interesting pattern that makes it easy to customize elements
in complex data structures. For example, customizing nodes and edges of a
graph, or vertices edges and faces of a mesh. I found it interesting and
wanted to share it. I have attached an example involving graphs, although I
currently use it to customize 3D meshes. Maybe it is of interest to anyone.
I am open for comments and suggestions.

-- 
Ares Lagae
Computer Graphics Research Group, Katholieke Universiteit Leuven
http://www.cs.kuleuven.be/~ares/


// -----------------------------------------------------------------------------
// general node, edge, graph

#include <vector>

template <typename GraphType>
class node
{
public:
  node() {}
};

template <typename GraphType>
class edge
{
public:
  typedef GraphType graph_type;
  typedef typename graph_type::node_iterator node_iterator;
  edge() {}
  edge(node_iterator node_0, node_iterator node_1)
    { nodes_[0] = node_0; nodes_[1] = node_1; }
private:
  node_iterator nodes_[2];
};

template <
  template <typename> class NodeType,
  template <typename> class EdgeType
...
class graph
{
public:
  typedef graph graph_type;
  typedef node<graph_type> node_base_type;
  typedef edge<graph_type> edge_base_type;
  typedef NodeType<graph_type> node_type;
  typedef EdgeType<graph_type> edge_type;
  typedef typename std::vector<node_type>::iterator node_iterator;
  typedef typename std::vector<edge_type>::iterator edge_iterator;
  node_iterator insert(const node_type& node)
    { return nodes_.insert(nodes_.end(), node); }
  edge_iterator insert(const edge_type& edge)
    { return edges_.insert(edges_.end(), edge); }
private:
  std::vector<node_type> nodes_;
  std::vector<edge_type> edges_;
};

// -----------------------------------------------------------------------------
// custom my_node, my_edge

template <typename GraphType>
class my_node : public GraphType::node_base_type
{
public:
  typedef GraphType graph_type;
  typedef typename graph_type::node_base_type node_base_type;
  my_node() : node_base_type() {}
  // custom members
};

template <typename GraphType>
class my_edge : public GraphType::edge_base_type
{
public:
  typedef GraphType graph_type;
  typedef typename graph_type::edge_base_type edge_base_type;
  typedef typename graph_type::node_iterator node_iterator;
  my_edge() : edge_base_type() {}
  my_edge(node_iterator node_0, node_iterator node_1)
    : edge_base_type(node_0, node_1) {}
  // custom members
};

// -----------------------------------------------------------------------------
// main

int main(int argc, char* argv[])
{
  { // graph using node and edge
    typedef graph<node, edge> graph_type;
    graph_type g;
    graph_type::node_iterator ni1 = g.insert(graph_type::node_type());
    graph_type::node_iterator ni2 = g.insert(graph_type::node_type());
    graph_type::edge_iterator ei = g.insert(graph_type::edge_type(ni1,
ni2));
  }

  { // graph using my_node and edge
    typedef graph<my_node, edge> graph_type;
    graph_type g;
    graph_type::node_iterator ni1 = g.insert(graph_type::node_type());
    graph_type::node_iterator ni2 = g.insert(graph_type::node_type());
    graph_type::edge_iterator ei = g.insert(graph_type::edge_type(ni1,
ni2));
  }

  { // graph using my_node and my_edge
    typedef graph<my_node, my_edge> graph_type;
    graph_type g;
    graph_type::node_iterator ni1 = g.insert(graph_type::node_type());
    graph_type::node_iterator ni2 = g.insert(graph_type::node_type());
    graph_type::edge_iterator ei = g.insert(graph_type::edge_type(ni1,
ni2));
  }

  { // graph using node and my_edge
    typedef graph<node, my_edge> graph_type;
    graph_type g;
    graph_type::node_iterator ni1 = g.insert(graph_type::node_type());
    graph_type::node_iterator ni2 = g.insert(graph_type::node_type());
    graph_type::edge_iterator ei = g.insert(graph_type::edge_type(ni1,
ni2));
  }
}