Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #43892 > unrolled thread

Nice graphs, how to write?

Back to article view | Back to comp.lang.c++

Contents

  Nice graphs, how to write? malcolm.mclean5@btinternet.com - 2016-07-25 03:00 -0700
    Re: Nice graphs, how to write? Nobody <nobody@nowhere.invalid> - 2016-07-25 12:47 +0100
      Re: Nice graphs, how to write? malcolm.mclean5@btinternet.com - 2016-07-25 04:58 -0700
    Re: Nice graphs, how to write? Paavo Helde <myfirstname@osa.pri.ee> - 2016-07-25 15:30 +0300
      Re: Nice graphs, how to write? malcolm.mclean5@btinternet.com - 2016-07-25 06:01 -0700
        Re: Nice graphs, how to write? Paavo Helde <myfirstname@osa.pri.ee> - 2016-07-25 17:55 +0300
    Re: Nice graphs, how to write? Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2016-07-25 15:43 +0200
      Re: Nice graphs, how to write? malcolm.mclean5@btinternet.com - 2016-07-25 07:18 -0700
    Re: Nice graphs, how to write? Frank Tetzel <s1445051@mail.zih.tu-dresden.de> - 2016-07-26 00:12 +0200
    Re: Nice graphs, how to write? Öö Tiib <ootiib@hot.ee> - 2016-07-26 01:11 -0700

#43892 — Nice graphs, how to write?

How to make nice graphs in modern, effective C++?

(By graph, I mean a data structure consisting of nodes and edges or links, not a histogram, bar chart, or visual representation of a function).

First thing is that we need lots of nodes of the same size. So provide a fixed-size block allocator and overload the new delete operators? 
Second thing, the node should be templated with the user-speciifed data.
Third thing, code to attach and detach elements to change the topology should be common.
Fourth thing, graph traversal must be easy and efficient, without unnecessary recursive
function calls. 

Now if we use shared pointers
1) The shared pointers themselves make calls to memory allocation functions, so the efficient block allocator goes out of the window.
2) Graphs tend to have circular dependencies. Garbage collection algorithms usually deal with
this, shared pointers don't.

If we use unique pointers
1) we're declaring some of the pointers to be "owners", but that's not necessarily logical or intuitive.
2) when the root unique pointer goes out of scope, you generate a massive cascade of
recursive destructor calls.
3) if we used a fixed block allocator, create only one graph from it, and the data member
contains no dynamic memory, we can destroy the structure in a few machine instructions
anyway, unless we use unique pointers.

So how would people write a  general-purpose, but tweakable (I'm not asking for something suitable for boost or the standard library, that would be ideal but the problem is difficult) modern, effective C++ graph?

[toc] | [next] | [standalone]

#43893

On Mon, 25 Jul 2016 03:00:31 -0700, malcolm.mclean5 wrote:

> Now if we use shared pointers

Are nodes with zero incoming edges allowed? If they are, then there
wouldn't seem to be much point in using shared pointers. And if you allow
nodes with neither incoming nor outgoing edges, then node lifetime is
dictated by the application rather than by topology.

If you want to be able to clone a graph, it's probably easier to
use integer indices for node references, rather than pointers.

[toc] | [prev] | [next] | [standalone]

#43894

On Monday, July 25, 2016 at 12:47:23 PM UTC+1, Nobody wrote:
> On Mon, 25 Jul 2016 03:00:31 -0700, malcolm.mclean5 wrote:
> 
> > Now if we use shared pointers
> 
> Are nodes with zero incoming edges allowed? If they are, then there
> wouldn't seem to be much point in using shared pointers. And if you allow
> nodes with neither incoming nor outgoing edges, then node lifetime is
> dictated by the application rather than by topology.
> 
Often there's root node which is a special case, and doesn't have any
incoming edges.
Then often you'll need a temporary node which is in the process of
being attached or detached, and has no incoming connections.

Sometimes it might also be possible to split the graph into islands.
Other times, that operation will implicitly destroy any nodes that no 
longer have a connection to the root.
The actual situations are bit domain-specific.

[toc] | [prev] | [next] | [standalone]

#43895

On 25.07.2016 13:00, malcolm.mclean5@btinternet.com wrote:
> How to make nice graphs in modern, effective C++?
>
> (By graph, I mean a data structure consisting of nodes and edges or links, not a histogram, bar chart, or visual representation of a function).
>
> First thing is that we need lots of nodes of the same size. So provide a fixed-size block allocator and overload the new delete operators?
> Second thing, the node should be templated with the user-speciifed data.
> Third thing, code to attach and detach elements to change the topology should be common.
> Fourth thing, graph traversal must be easy and efficient, without unnecessary recursive
> function calls.
>
> Now if we use shared pointers
> 1) The shared pointers themselves make calls to memory allocation functions, so the efficient block allocator goes out of the window.
> 2) Graphs tend to have circular dependencies. Garbage collection algorithms usually deal with
> this, shared pointers don't.
> If we use unique pointers
> 1) we're declaring some of the pointers to be "owners", but that's not necessarily logical or intuitive.
> 2) when the root unique pointer goes out of scope, you generate a massive cascade of
> recursive destructor calls.
> 3) if we used a fixed block allocator, create only one graph from it, and the data member
> contains no dynamic memory, we can destroy the structure in a few machine instructions
> anyway, unless we use unique pointers.

Allocating each node separately is clearly not the right thing to do. 
What you need to allocate and destroy are graph objects, how they manage 
the nodes internally (probably with some pooled allocator) should not be 
a worry for the application level code. I guess this matches your option 3).

>
> So how would people write a  general-purpose, but tweakable (I'm not asking for something suitable for boost or the standard library, that would be ideal but the problem is difficult) modern, effective C++ graph?

You mention Boost so I assume you have looked at the Boost.Graph library 
and how they do things there(?) I suspect their implementation is hard 
to beat.

Cheers
Paavo

[toc] | [prev] | [next] | [standalone]

#43896

On Monday, July 25, 2016 at 1:31:09 PM UTC+1, Paavo Helde wrote:
> On 25.07.2016 13:00, malcolm.mclean5@btinternet.com wrote:
> > How to make nice graphs in modern, effective C++?
> >
> > (By graph, I mean a data structure consisting of nodes and edges or links, not a histogram, bar chart, or visual representation of a function).
> >
> > First thing is that we need lots of nodes of the same size. So provide a fixed-size block allocator and overload the new delete operators?
> > Second thing, the node should be templated with the user-speciifed data.
> > Third thing, code to attach and detach elements to change the topology should be common.
> > Fourth thing, graph traversal must be easy and efficient, without unnecessary recursive
> > function calls.
> >
> > Now if we use shared pointers
> > 1) The shared pointers themselves make calls to memory allocation functions, so the efficient block allocator goes out of the window.
> > 2) Graphs tend to have circular dependencies. Garbage collection algorithms usually deal with
> > this, shared pointers don't.
> > If we use unique pointers
> > 1) we're declaring some of the pointers to be "owners", but that's not necessarily logical or intuitive.
> > 2) when the root unique pointer goes out of scope, you generate a massive cascade of
> > recursive destructor calls.
> > 3) if we used a fixed block allocator, create only one graph from it, and the data member
> > contains no dynamic memory, we can destroy the structure in a few machine instructions
> > anyway, unless we use unique pointers.
> 
> Allocating each node separately is clearly not the right thing to do. 
> What you need to allocate and destroy are graph objects, how they manage 
> the nodes internally (probably with some pooled allocator) should not be 
> a worry for the application level code. I guess this matches your option 3).
> 
> >
> > So how would people write a  general-purpose, but tweakable (I'm not asking for something suitable for boost or the standard library, that would be ideal but the problem is difficult) modern, effective C++ graph?
> 
> You mention Boost so I assume you have looked at the Boost.Graph library 
> and how they do things there(?) I suspect their implementation is hard 
> to beat.
> 
Boost is doing rather a different thing.

It's proving a very generic interface of nodes and edges which can describe any
topologically possible graph, which can then be passed to general purpose
but quite sophisticated 'graph algorithms".

What I'm after is a design pattern or template for a graph object which has
specialised but probably restricted topology (e.g. it might be essentially a tree
with the odd shared branch link), and where caller is likely to build his own
algorithms on top of basic facilities for inserting / detaching nodes and following
edges. Usually those algorithms will be simpler than things like shortest path
and clique finding.

The answer might be "just use Boost" but the Boost graph page itself suggests
that this won't be the case.

[toc] | [prev] | [next] | [standalone]

#43899

On 25.07.2016 16:01, malcolm.mclean5@btinternet.com wrote:
> On Monday, July 25, 2016 at 1:31:09 PM UTC+1, Paavo Helde wrote:
>> On 25.07.2016 13:00, malcolm.mclean5@btinternet.com wrote:
>>> How to make nice graphs in modern, effective C++?
>>>
>>> (By graph, I mean a data structure consisting of nodes and edges or links, not a histogram, bar chart, or visual representation of a function).
>>>
>>> First thing is that we need lots of nodes of the same size. So provide a fixed-size block allocator and overload the new delete operators?
>>> Second thing, the node should be templated with the user-speciifed data.
>>> Third thing, code to attach and detach elements to change the topology should be common.
>>> Fourth thing, graph traversal must be easy and efficient, without unnecessary recursive
>>> function calls.
>>>
>>> Now if we use shared pointers
>>> 1) The shared pointers themselves make calls to memory allocation functions, so the efficient block allocator goes out of the window.
>>> 2) Graphs tend to have circular dependencies. Garbage collection algorithms usually deal with
>>> this, shared pointers don't.
>>> If we use unique pointers
>>> 1) we're declaring some of the pointers to be "owners", but that's not necessarily logical or intuitive.
>>> 2) when the root unique pointer goes out of scope, you generate a massive cascade of
>>> recursive destructor calls.
>>> 3) if we used a fixed block allocator, create only one graph from it, and the data member
>>> contains no dynamic memory, we can destroy the structure in a few machine instructions
>>> anyway, unless we use unique pointers.
>>
>> Allocating each node separately is clearly not the right thing to do.
>> What you need to allocate and destroy are graph objects, how they manage
>> the nodes internally (probably with some pooled allocator) should not be
>> a worry for the application level code. I guess this matches your option 3).
>>
>>>
>>> So how would people write a  general-purpose, but tweakable (I'm not asking for something suitable for boost or the standard library, that would be ideal but the problem is difficult) modern, effective C++ graph?
>>
>> You mention Boost so I assume you have looked at the Boost.Graph library
>> and how they do things there(?) I suspect their implementation is hard
>> to beat.
>>
> Boost is doing rather a different thing.
>
> It's proving a very generic interface of nodes and edges which can describe any
> topologically possible graph, which can then be passed to general purpose
> but quite sophisticated 'graph algorithms".
>
> What I'm after is a design pattern or template for a graph object which has
> specialised but probably restricted topology (e.g. it might be essentially a tree
> with the odd shared branch link), and where caller is likely to build his own
> algorithms on top of basic facilities for inserting / detaching nodes and following
> edges. Usually those algorithms will be simpler than things like shortest path
> and clique finding.
>
> The answer might be "just use Boost" but the Boost graph page itself suggests
> that this won't be the case.

I see. So you believe BGL is an overkill and too complicated, but at the 
same time you want to have super performance and ease of use. This might 
a fine goal indeed.

When building this kind of thing myself I would probably start super 
simple. First, dynamic memory allocation is the first performance killer 
for such type of thing, so I would first try to create a vertex class 
which has no dynamic allocations (or at least no dynamic allocations for 
vertices with typical attributes and number of links).

These objects could be held in a pooled allocator or even in a 
std::vector, for that matter. If everything is held in a std::vector 
then I would use integer indices instead of pointers and potentially 
save lots of memory thereby (if I can use smaller integers then the 
pointer size).

Just some random ideas.

HTH
Paavo

[toc] | [prev] | [next] | [standalone]

#43897

malcolm.mclean5@btinternet.com writes:

> (By graph, I mean a data structure consisting of nodes and edges or
> links, not a histogram, bar chart, or visual representation of a
> function).
>
> First thing is that we need lots of nodes of the same size. So provide
> a fixed-size block allocator and overload the new delete operators?

It all depends on what you mean by "lots of".

> Second thing, the node should be templated with the user-speciifed data.
> Third thing, code to attach and detach elements to change the topology
> should be common.
> Fourth thing, graph traversal must be easy and efficient, without
> unnecessary recursive
> function calls. 

I don't really see how a recursive call can be "unnnecessary" on a graph
structure, unless your topology is very specific.

> Now if we use shared pointers
> 1) The shared pointers themselves make calls to memory allocation
> functions, so the efficient block allocator goes out of the window.
> 2) Graphs tend to have circular dependencies. Garbage collection
> algorithms usually deal with
> this, shared pointers don't.

You would need a special allocator and special deleters, but anyway you
are right about reference counting.

> If we use unique pointers
> 1) we're declaring some of the pointers to be "owners", but that's not
> necessarily logical or intuitive.
> 2) when the root unique pointer goes out of scope, you generate a
> massive cascade of
> recursive destructor calls.
> 3) if we used a fixed block allocator, create only one graph from it,
> and the data member
> contains no dynamic memory, we can destroy the structure in a few
> machine instructions
> anyway, unless we use unique pointers.

unique_ptr is actually really tricky, and I don't think they match your
requirements.

> So how would people write a general-purpose, but tweakable (I'm not
> asking for something suitable for boost or the standard library, that
> would be ideal but the problem is difficult) modern, effective C++
> graph?

I would keep a per-graph linked list of nodes via a raw pointer member
(for deallocation), and either allocate from a pool, or keep one or more
free-lists.

If you need, e.g., frequent topological traversals without interfering
topology changes, you can even arrange to keep your graph-wide list of
nodes in the correct order, and use that for the traversals.

-- Alain.

[toc] | [prev] | [next] | [standalone]

#43898

On Monday, July 25, 2016 at 2:44:11 PM UTC+1, Alain Ketterlin wrote:
> malcolm.mclean5@btinternet.com writes:
> 
> I don't really see how a recursive call can be "unnnecessary" on a graph
> structure, unless your topology is very specific.
> 
Often you can rewrite a recursive function as a 'spider" which crawls about 
the graph, maybe marking edges it has traversed to avoid getting caught in 
loops. That's often more efficient.
>
> unique_ptr is actually really tricky, and I don't think they match your
> requirements.
> 
Maybe just the root should be unique_ptr ?
>
> I would keep a per-graph linked list of nodes via a raw pointer member
> (for deallocation), and either allocate from a pool, or keep one or more
> free-lists.
> 
> If you need, e.g., frequent topological traversals without interfering
> topology changes, you can even arrange to keep your graph-wide list of
> nodes in the correct order, and use that for the traversals.
> 
That's the sort of stuff you need, though it would tend to be a late
optimisation introduced during refactoring.

[toc] | [prev] | [next] | [standalone]

#43915

> So how would people write a  general-purpose, but tweakable (I'm not
> asking for something suitable for boost or the standard library, that
> would be ideal but the problem is difficult) modern, effective C++
> graph?

Not everything has to be an object. Take a step back and just look at
the data you want to process. An adjancency list is an easy
representation of a graph and most often good enough. The simplest way
to implement it is a vector of vectors. That's it. Simple solutions are
good for you.

[toc] | [prev] | [next] | [standalone]

#43919

On Monday, 25 July 2016 13:00:45 UTC+3, malcolm...@btinternet.com  wrote:
> How to make nice graphs in modern, effective C++?
> 
> (By graph, I mean a data structure consisting of nodes and edges or
> links, not a histogram, bar chart, or visual representation of a function).
> 
> First thing is that we need lots of nodes of the same size. So provide
> a fixed-size block allocator and overload the new delete operators? 

That vertices are of same size feels significant simplification of the
issue. You do not mention edges (and properties of edges) so that may be 
can of worms or it may bring some significant simplification of the
issue. Details about "how?" (how to manage memory?) are for lot *after*
you have full list of "what?".

> Second thing, the node should be templated with the user-speciifed data.

That I do not understand. Node should contain user-specified data? 
One object? May it be polymorphic?

> Third thing, code to attach and detach elements to change the topology
> should be common.

Is it somehow meant as subtle performance requirement? Most important
about such collections like graph data structure is how those scale
and so you better form such requirements as running time complexity
(typically constant, logarithmic or linear).

> Fourth thing, graph traversal must be easy and efficient, without
> unnecessary recursive function calls. 

Same here. If something is done with loop or recursion is about "how?".
What are the "traversal" operations? What is expected running time
complexity for those?

> 
> Now if we use shared pointers
> 1) The shared pointers themselves make calls to memory allocation functions, so the efficient block allocator goes out of the window.
> 2) Graphs tend to have circular dependencies. Garbage collection algorithms usually deal with
> this, shared pointers don't.
> 
> If we use unique pointers
> 1) we're declaring some of the pointers to be "owners", but that's not necessarily logical or intuitive.
> 2) when the root unique pointer goes out of scope, you generate a massive cascade of
> recursive destructor calls.
> 3) if we used a fixed block allocator, create only one graph from it, and the data member
> contains no dynamic memory, we can destroy the structure in a few machine instructions
> anyway, unless we use unique pointers.

If you want the nodes to own user-specified polymorphic data then you likely
need 'std::unique_ptr' for it. Otherwise I do not see why you need owning
smart pointers in context of graph that you describe.

> 
> So how would people write a  general-purpose, but tweakable (I'm not
> asking for something suitable for boost or the standard library, that
> would be ideal but the problem is difficult) modern, effective C++ graph?

I would first take 'adjacency_list' of Boost.Graph and use it. It feels
somewhat over-engineered but works fine on most cases. If it does not suit
badly then it must be some rather special requirement and likely close to
impossible to solve for general purpose. On such cases however I write
special-purpose classes (and dump the term "general-purpose").

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web