# How to obtain and store a subgraph of a graph in C++?

I have implemented a graph structure (for graphs having ~30,000 nodes and ~300,000 edges) as follows:

``````class graph;
class node;
class edge;

class graph
{
public:
graph(){};
vector<node*> nodeS;
vector<edge*> edgeS;
};

class node
{
public:
node(){};
vector<edge*> my_edgeS;
double weight;
};

class edge
{
public:
edge(){};
node *start, *end;
double weight;
};
``````

where `nodeS` stores the nodes, `edgeS` contains the edges, `start` and `end` points to the starting and ending nodes of a specific edge, respectively, weight is the node (edge) weight, and `my_edgeS` consists of the edges incident to a given node.

I would like to obtain a lot of subgraphs of the original graph defined by some of its edges (the incidences of the edges are unchanged and all the nodes of the original graph are included in the subgraphs). How to build and store these subgraphs (especially their `my_edgeS` vectors) in C++ in the most efficient way? Or is there any other structure which is more suitable for deriving subgraphs from a graph?

• With that exact definition, you will have to clone the nodes and edges of each subgraph from the source graph. If you have a different structure, you could get away with copying pointers. – Caleth Mar 27 at 10:19
• Also why `weight` for the data on a node? – Caleth Mar 27 at 10:21
• Yes, you are right. Actually, the weights of the `node` instances are potentials of the nodes. – TobiR Mar 27 at 20:00

I'd suggest removing the `my_edgeS` data member from `node`. Replace it with a method `edges_for (node * n)` in `graph`. In that way, a subgraph is populated with pointers to some of the same `node`s, and their corresponding `edge`s.

I strongly suggest you not to use owning raw pointers.

As a sketch

``````struct node
{
double data;
};

using node_ptr = std::shared_ptr<node>;

struct edge
{
node_ptr start, end;
double weight;
};

using edge_ptr = std::shared_ptr<edge>;

struct graph
{
vector<node_ptr> nodes;
vector<edge_ptr> edges;

std::vector<edge_ptr> edges_for(node_ptr n)
{
std::vector<edge_ptr> result;
std::copy_if(edges.begin(), edges.end(), [n](edge_ptr e) { return (e->start == n) || (e->end == n); });
return result;
}

std::vector<edge_ptr> in_edges_for(node_ptr n)
{
std::vector<edge_ptr> result;
std::copy_if(edges.begin(), edges.end(), [n](edge_ptr e) { return e->end == n; });
return result;
}

std::vector<edge_ptr> out_edges_for(node_ptr n)
{
std::vector<edge_ptr> result;
std::copy_if(edges.begin(), edges.end(), [n](edge_ptr e) { return e->start == n; });
return result;
}

graph subgraph(std::vector<node_ptr> sub_nodes)
{
std::vector<edge_ptr> sub_edges;
for (node_ptr n : sub_nodes)
{
auto n_edges = in_edges_for(n);
sub_edges.insert(n_edges.begin(), n_edges.end());
}
return { sub_nodes, sub_edges };
}

graph subgraph(std::vector<edge_ptr> sub_edges)
{
std::unordered_set<node_ptr> sub_nodes;
std::transform(sub_edges.begin(), sub_edges.end(), std::inserter(sub_nodes, sub_nodes.end()), [](edge_ptr e){ return e->start; });
return { { sub_nodes.begin(), sub_nodes.end() }, sub_edges };
}
};
``````
• Thank you very much! If I understand you correctly, the functions `graph::subgraph()` overwrite the vectors nodes and edges of `graph`. So, if I have to create a subgraph of a `graph` instance, denoted with `g`, then I should copy `g` to `sg` and call one of the functions of the form `sg::subgraph()`. Is this true? – TobiR Mar 27 at 20:05
• No, 'subgraph' creates a new graph. I've accidentally shadowed the member names, fixed – Caleth Mar 27 at 21:16