On Aug 25, 2009, at 10:22 AM, Julien Signoles wrote:
Benjamin Ylvisaker a écrit :
I have been using ocamlgraph for a while, and have been generally
happy with it. I experienced some poor performance with moderately
large graphs (10-100k vertices) recently, which led me to look
through th
Hi,
Benjamin Ylvisaker wrote:
> I have been using ocamlgraph for a while, and have been generally happy
> with it. I experienced some poor performance with moderately large
> graphs (10-100k vertices) recently, which led me to look through the
> source code a little. It seems that doing anything
Edgar Friendly a écrit :
This is another solution to the slow predecessor performance, and will
have different performance characteristics than predecessor
lookup-tables. Note that the lookup table solution is isomorphic to
building a second graph with all the arrows reversed, and using the
effi
Benjamin Ylvisaker a écrit :
I have been using ocamlgraph for a while, and have been generally happy
with it. I experienced some poor performance with moderately large
graphs (10-100k vertices) recently, which led me to look through the
source code a little. It seems that doing anything with
In your previous mail you wrote:
By the way, BSD uses lots of singly-linked lists, probably because it
comes from a time when there was not so much memory.
=> no, BSDs use an include ([/usr/include]/sys/queue.h) which provides
C macros for singly-linked lists, singly-linked tail queues,
In further performance debugging, I discovered that vertex removal is
also an O(|V|) operation. This makes sense given the fact that
accessing predecessors is O(|V|), because the predecessor links have
to be removed in order to properly remove a vertex. Stepping back,
however, I still thi
Perhaps something like that in ConcreteBidirectional
be implemented for general Digraph so predecessors
can be accessed in O(1)? If I am not mistaken, that
will double the storage and running time of most of
the operations. This implementation could be added
as an additional variant without modif
From: ri...@happyleptic.org
> > What you're asking is similar to the problem of finding the predecessor
> > of an arbitrary node in a singly-linked-list. You have no option but to
> > scan the whole list to find its predecessor. If you had a
> > doubly-linked-list, predecessor lookups would work
> What you're asking is similar to the problem of finding the predecessor
> of an arbitrary node in a singly-linked-list. You have no option but to
> scan the whole list to find its predecessor. If you had a
> doubly-linked-list, predecessor lookups would work easily, but that's a
> different dat
Benjamin Ylvisaker wrote:
>
> On Aug 8, 2009, at 6:35 AM, Edgar Friendly wrote:
>
>> Benjamin Ylvisaker wrote:
>>> I have been using ocamlgraph for a while, and have been generally happy
>>> with it. I experienced some poor performance with moderately large
>>> graphs (10-100k vertices) recently
On Aug 8, 2009, at 6:35 AM, Edgar Friendly wrote:
Benjamin Ylvisaker wrote:
I have been using ocamlgraph for a while, and have been generally
happy
with it. I experienced some poor performance with moderately large
graphs (10-100k vertices) recently, which led me to look through the
source
Benjamin Ylvisaker wrote:
> I have been using ocamlgraph for a while, and have been generally happy
> with it. I experienced some poor performance with moderately large
> graphs (10-100k vertices) recently, which led me to look through the
> source code a little. It seems that doing anything with
I have been using ocamlgraph for a while, and have been generally
happy with it. I experienced some poor performance with moderately
large graphs (10-100k vertices) recently, which led me to look through
the source code a little. It seems that doing anything with the
predecessors of a ver
13 matches
Mail list logo
