[CGraph] Fastest way to create a subgraph containing the entire graph

[chtenb]

I'm writing application code that does some graph computations before lay-outing anything. I create subgraph structures to do these computations and manipulations. This often has the following form:

1. Create a subgraph that contains the entire graph.
2. Remove some nodes.
3. Perform some domain specific graph search algorithms.
4. Remove the temporary subgraph again.

This is done very often. The results are aggregated into a new graph, which is then being layed-out by dot.

According to some profiling, the major performance bottleneck is caused by step 1. (The next most critical bottleneck is step 4)

I currently use the following code to create such a subgraph. Are there faster ways to do it?

Agraph_t* clone_g_to_subg(Agraph_t* from, char* name)
{
    auto result = agsubg(from, name, 1);

    auto node = agfstnode(from);
    while (node)
    {
        agsubnode(result, node, 1);
        auto edge = agfstedge(from, node);
        while (edge)
        {
            agsubedge(result, edge, 1);
            edge = agnxtedge(from, edge, node);
        }
        node = agnxtnode(from, node);
    }

    return result;
}

[chtenb]

Maybe using the agclone function that @emden has talked about earlier? Could that be of help?

[magneticnorth]

This looks reasonable.

Conceptually, what could make it faster? If we had agclone() we would probably just do something very much like your code.

libcdt has a notion of viewpathing of dictionaries (sets) so you could possibly in constant time create a subgraph that has a view of its parent objects, but deletion seems like a complication. Would we need internal stub objects to record deletions? That seems like it would involve a lot of our code - basically every edge iterator inside cgraph would have to hide these. The code for handling object insertion would need to look for them, etc.

I don’t see a good way to approach this.

On Sep 27, 2017, at 5:14 AM, Chiel ten Brinke [email protected] wrote:

I'm writing application code that does some graph computations before lay-outing anything. I create subgraph structures to do these computations and manipulations. This often has the following form:

Create a subgraph that contains the entire graph. Remove some nodes. Perform some domain specific graph search algorithms. Remove the temporary subgraph again. This is done very often. The results are aggregated into a new graph, which is then being layed-out by dot.

According to some profiling, the major performance bottleneck is caused by step 1. (The next most critical bottleneck is step 4)

I currently use the following code to create such a subgraph. Are there faster ways to do it?

Agraph_t* clone_g_to_subg(Agraph_t* from, char* name) { auto result = agsubg(from, name, 1);

auto node = agfstnode(from);
while (node)
{
    agsubnode(result, node, 1);
    auto edge = agfstedge(from, node);
    while (edge)
    {
        agsubedge(result, edge, 1);
        edge = agnxtedge(from, edge, node);
    }
    node = agnxtnode(from, node);
}

return result;

} — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/ellson/MOTHBALLED-graphviz/issues/1285, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWz__vr3QhQbQCTRat_83Mg7bmN_PXks5smhH6gaJpZM4PldLE.