-2

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
0

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 nodes, and their corresponding edges.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.