Computer Science

« first day (1633 days earlier) ← previous day next day → last day (3102 days later) »

Raphael

00:21

Those of you who work with LaTeX may want to check out its section in the new documentation thingy on SO.

18 hours later…

Jonathan Dickinson

18:08

Hey all. I've found a way to store a cyclic directed graph in a flat array with constant element length. Recursion happens (obviously), but it's near the optimal amount (FEs, BEs and CEs cause it).

I have no applicable formal tertiary education, would any of you be able to help me get this information out?

D.W.

18:43

What are the advantages of your representation over standard graph representations (e.g., adjacency list)? I'm not sure what you mean by recursion happens or by optimal amount.

Anyway, to answer your question about how to 'get the word out', one standard answer is to create a blog of your own and write a blog post. Another is to try to see if there is any problem anyone has that you can solve better with your scheme than with the currently standard/known approaches.

@JonathanDickinson ^

Jonathan Dickinson

An adjancency list doesn't have constant element length. An adjacency list recurses once per node, where-as this representation recurses only when it encounters a forward edge, back edge or cross edge.

Otherwise it iterates

Evil

19:38

Something weird is at room stats - D.W's stats are totally empty, no last message or count or plot. Is this some kind of cache issue?

Raphael

@JonathanDickinson I'm confident that I can implement graphs using only recursion, no recursion, or a mixture. I don't understand what you are proposing exactly, and what the advantages should be.

Jonathan Dickinson

A binary heap for graphs, if you will.

Raphael

What is the advantage of your "flat array" vs adjacency and incidence matrix, respectively?

Jonathan Dickinson

It's high entropy: 4 ints are used for each edge. It consists of two structures, one is length N, the other length E. Each element in each structure has a constant length, no pointers to additional arrays or such: flat. It supports cyclic graphs, with far less recursion than you'd expect with an adjancency matrix or list (it tends to iterate: good for the cache)...

Depending on the exact configuration, it can be queried both fowards along directions and backwards. It can by cryptographically hashed.

It's also sparse (unlike the matrix)

Raphael

What do you mean by recursion here? Pointer dereferencing?

Jonathan Dickinson

19:54

So, adjacency list: each list is essentially a list of nodes that need to be recursed to (while memoizing nodes that you have visited). So a pointer dereference, and then a recurse.

Raphael

What are the running times of the common operations, 1) check if (u,v) is an edge, 2) get all neighbours of u, 3) add an edge, 4) remove an edge?

Jonathan Dickinson

The same applies to the matrix (albiet skipping over empty cells)

Raphael

@JonathanDickinson No, you do not need to recurse. In practice, you can use ArrayList or similar and happily iterate.

Jonathan Dickinson

For descendants-of and ancestors-of?

Gilles

@JonathanDickinson I don't know about the precise topic, I'm not a data structure expert, but here's some general advice

First, read some textbooks or course materials about the topic just so that you absord the standard terminology.

When you present your work, it's up to you to make yourself understood, so it's important that you speak their language.

Then read up on existing literature, which if I understand correctly would be on cache-efficient representations of graphs.

Work out some basic properties regarding asymptotic complexity (the question Raphael just asked).

Jonathan Dickinson

19:56

It's based on existing work, which took me weeks to digest :). There's a difference between reading it and writing it.

Gilles

Implement your algorithm and compare it with other decent ones on some typical data.

Raphael

Seconded.

Reading your less-than-expert-sounding statements about the standard data structures, I have little confidence that you've found something fundamentally better. That does not say anything about you -- you *may* have done so -- but is a matter of experience. Most laymen who think they've found something cool have made a mistake, or reinvented a wheel (which certainly is a personal achievement).

That said, if you can share a concise explanation and pseudo-code write-up of your data structure, I'd be interested to have a look. (So far, you have not shared anything.)

Jonathan Dickinson

I can't just give it away like that. That's why I'm looking to find out if anyone is willing to put my name on the paper. I'm cautiously optimistic, I only grokked Tarjan's Strongly Connected Components Algorithm a few months back.

I know full-well it could be nothing.

My twitter handle is up on my exchange profile.

Evil

@JonathanDickinson so you are going to send it to someone who will write paper on your behalf?

« first day (1633 days earlier) ← previous day next day → last day (3102 days later) »

all rooms