Basic Operations On Graphs

For a targeted application, characterization can be posed as a graph query operation using three graph-based algorithms:

  • finding connected components, and

  • computing the shortest paths.

  • the graph filtering operation which enables the query definitions that capture some aspects of underlying physics.

Identifying connected components of a graph

We start by explaining the link between the question of quantifying the number of individual domains and the graph queries. Here, we aim to identify the sub-domains of the morphology, where the sub-domain is part of the morphology that is surrounded by sub-domains of other color(s). We accomplish it by assigning an index of their connected component (CC) to each vertex. The process requires two steps. First, we define the filtered graph by masking the edges connecting vertices of different labels/colors. In other words, we ensure that only the edges connecting vertices of the same label are considered. In the second step, we invoke the the connected components algorithm on the filtered graph.

Translating this process into the code requires only few lines of code (included below). We use data structure and functions from the boost library. First, the code defines the predicate to facilitate graph filtering via class edge_same_color_predicate. This class has operator() that checks if a given edge satisfies the filtering condition (returns a true or a false value if the condition is satisfied or not). In this case, we check the condition whether the colors of the two vertices that build the edge e (source and target) are the same. To look up the labels of vertices constituting the edge, the class additionally stores pointers to the graph G_ and the vector of vertices labels (color_).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class edge_same_color_predicate {
public:
    edge_same_color_predicate() : G_(0), color_(0) { }
    edge_same_color_predicate(const gt::graph_t& G, const std::vector<COLOR>& color)
           : G_(&G), color_(&color) { }
     bool operator()(const gt::edge_t& e) const {
            return ((*color_)[boost::source(e, *G_)] == (*color_)[boost::target(e, *G_)]);
      }
      private:
      const gt::graph_t* G_;
      const std::vector<COLOR>* color_;
      };

Once the graph filtering is defined, it is used to filter the original graph. The function to determine the connected components in the graph is included below. It consists of three lines:

  1. the declaration of the object p of type defined above,

  2. the declaration of the filtered graph FG of type filtered_graph defined in boost::graph library and

  3. the call of function connected_components from boost::graph library that determines connected components in the filtered graph.

The outcome from this procedure is stored in the vector components with integer values that corresponds to the index of the connected components.

1
2
3
4
5
6
void DetermineConnectedComponents(gt::graph_t* G, const std::vector<COLOR>& color,
       std::vector<int>& components){
    edge_same_color_predicate p( *G, color);
    boost::filtered_graph<gt::graph_t, edge_same_color_predicate> FG(*G, p);
    boost::connected_components(FG, &components[0]);
    }