At Wed, 24 Apr 2013 13:02:39 +0100,
Francesco Mazzoli wrote:
> Hi list,
>
> I’ve been lately thinking about how to implement an algorithm efficiently,
> and I
> need a directed graph that can perform the following tasks:
>
> 1. Finding the strongly connected components
> 2. Condensing strong
Hi list,
I’ve been lately thinking about how to implement an algorithm efficiently, and I
need a directed graph that can perform the following tasks:
1. Finding the strongly connected components
2. Condensing strongly connected components
3. Contract single edges
The condensing shouldn’t p
Hi John.
> What are the prospects for Haskell supporting Structured Graphs as defined
> here?
> http://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf
>
> Is there an interest by developers of GHC in doing this?
Could you be more specific about the kind of "support&qu
What are the prospects for Haskell supporting Structured Graphs as defined here?
http://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf
Is there an interest by developers of GHC in doing this?
-John___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
On 21/09/2012, Takayuki Muranushi wrote:
> Yes Pointers. I've forgotten that. I have once dealt with structures,
> with lots of IORefs. It was smooth and fast. Thank you for reminding
> me!
>
> On the other hand, use of pointers means that our values are not
> algebraic data type any more. We hav
Yes Pointers. I've forgotten that. I have once dealt with structures,
with lots of IORefs. It was smooth and fast. Thank you for reminding
me!
On the other hand, use of pointers means that our values are not
algebraic data type any more. We have to derive operations such as
map, fold, serialize b
Pointers.
Seriously.
In Haskell one could use STRef rather than the cumbersome Foreign.Ptr,
though STRef too can be kludgy.
I know not whether safe, pure, immutable pointers would be possible in
Haskell, but in my experience STRef can work well enough.
Cheers,
Strake
__
> I can try to use the nodes/specs you provide to give you an estimate
> of what my framework can handle. If that works for you, I'll clean up
> my code and you can give it a shot. Send me whatever other details you
> think are relevant.
Benjamin,
I had a few moments, so I made a sparse graph of
Benjamin,
> - Immutable structure, mutable labels. After initially reading in the
> graphs, their shape doesn't change, but information "flows" around the graph,
> changing the labels on nodes and edges.
I have been working on a similar problem for a while no
I had issues with FGL in the past, too. Although FGL is really nice to
work with, it just uses a ridiculous amount of memory for large
graphs.
In the end, I used Data.Graph from containers [1]. This was a lot more
reasonable, and let me finish my project relatively easily.
Regards,
- Clark
[1
formance bug in my code. I tried looking around for concrete information
> about the scalability of Haskell's graph libraries, but didn't find much. So
> here are the characteristics of the problem I'm working on:
>
> - Large directed graphs. Mostly 10k-100k nodes, but
nd for concrete information
about the scalability of Haskell's graph libraries, but didn't find much. So
here are the characteristics of the problem I'm working on:
- Large directed graphs. Mostly 10k-100k nodes, but some in the low 100ks.
- Sparse graphs. The number of edges is
Using something like zippers it is easy to navigate an acyclic graph
in O(1) operations per arc you follow. Inspired by Chris Okasaki's
work on queues I wondered if there is a similar approach to navigating
cyclic graphs.
If the graph you are navigating is static (i.e. does not have to
su
Emil Axelsson writes:
> Yes, that's probably close to what I want. It would of course be nice
> to also have a monadic/applicative interface for building the
> graphs. In libraries like Wired where you're in a monad anyway, this
> would get rid of the need for IO.
IIRC, do
Yes, that's probably close to what I want. It would of course be nice to
also have a monadic/applicative interface for building the graphs. In
libraries like Wired where you're in a monad anyway, this would get rid
of the need for IO.
Koen Claessen has made a sketch of a generic gra
r to yours (but more complicated).
I think it would be nice to have a single library for defining such
graphs (or maybe there is one already?). The graph structure in
Wired could probably be divided into a purely structural part and a
hardware-specific part.
[1] http://citeseerx.ist.psu.edu/
for defining such
graphs (or maybe there is one already?). The graph structure in Wired
could probably be divided into a purely structural part and a
hardware-specific part.
[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.5221
[2] http://www.cs.chalmers.se/~dave/papers/observable
Neat
Surely there is somewhere in the haskell Twiki that something like
this should live?
Neil
On 12 Dec 2009, at 21:00, Soenke Hahn wrote:
Hi!
Some time ago, i needed to write down graphs in Haskell. I wanted to
be able
to write them down without to much noise, to make them easily
Hi!
Some time ago, i needed to write down graphs in Haskell. I wanted to be able
to write them down without to much noise, to make them easily maintainable. I
came up with a way to define graphs using monads and the do notation. I thought
this might be interesting to someone, so i wrote a
Hi *^o^*,
I'm working on a source code transformation project for numerical automatic
differentiation for Fortran and C.
I would love to know the best Haskell way/package available today to
represent procedural (non-OO) code in a language-independent manner. Any
tips or resource, paper references
gt; launchMissiles will require something with fast rendering.
There was a Haskell-written graph editor in Dazzle, which the authors
kindly open-sourced, to become the rudimentary application Blobs:
http://www.cs.york.ac.uk/fp/darcs/Blobs/
The GUI is implemented in wxHaskell, graphs are saved as
o O
6b. right-click-drag as in 6a, when released on a highlighted target,
joins the graphs together, such that the original node fills that
target, and all other targets are unhighlighted:
* * *
: | => |
[O] [*]
:
7. when a connected componen
>
> We don't seem to have a binding to any of the foreign language libs for
> very large graphs.
>
> Do you know of any stand-out libraries in this regard worth binding?
When I looked in to this last year, the best I could find was the boost
library. It depends very heav
gt; Has anything even been published on the topic since Erwig's paper?
>
I think fgl is pretty much the main work on purely functional graphs,
though Data.Graph ships in the containers package (Launchbury et al).
A quick google also turned up:
http://www.osl.iu.edu/research/comparing/h
Hey,
Besides fgl, are there any graph libraries in Haskell that are still
maintained? Are there other papers (or books) besides Erwig's that I
could use to understand how graph algorithms have been implemented in
functional languages?
Has anything even been published on the topic since Erwig'
In model checking, transition matrices (ie weighted adjacency
matrices) are often represented by binary decision diagrams. They're a
very compact way of representing sparse or regular vectors/matrices
(where graphs can be thought of as adjacency matrices). Theres some
good lecture notes on
(Forgot to send to haskell-cafe- sorry Alistair!)
Martin Erwig wrote a paper [1] that defines an inductive graph type and
implements some common algorithms with it.
Also, it isn't very Haskellish but if you can label your nodes with an
instance of Ix you might be able to use an Array to get const
(OT, but I'm hoping some of you might have some ideas on this anyway...)
I was wondering what alternative representations there are for graphs,
or maybe if there might be a way to derive one/some from some insightful
observations. For the purposes of storing and exmaining (querying)
graphs
On Friday July 11 2008, Don Stewart wrote:
> Do you have the bencmark code? I'd like to try a couple of variants on
> the underlying structures.
It's not a thorough test but I suppose it gives an impression about
performance.
-- Gokhan
$ ghc -O -prof --make TestGraph
$ ./TestGraph +RTS -s -P -R
gsan:
> On Friday July 11 2008, Andre Nathan wrote:
> > On Thu, 2008-07-10 at 16:52 -0700, Don Stewart wrote:
> > > Well, they're radically different graph representations, and fgl
> > > hasn't been designed for large graphs.
> >
> > Do you know if
On Friday July 11 2008, Andre Nathan wrote:
> On Thu, 2008-07-10 at 16:52 -0700, Don Stewart wrote:
> > Well, they're radically different graph representations, and fgl
> > hasn't been designed for large graphs.
>
> Do you know if King and Launchbury's impleme
On Thu, 2008-07-10 at 16:52 -0700, Don Stewart wrote:
> Well, they're radically different graph representations, and fgl
> hasn't been designed for large graphs.
Do you know if King and Launchbury's implementation (Data.Graph) scales
better?
> What C library is Ruby&#
idering p is low. Is the internal representation of
> inductive graphs perhaps not very memory-efficient? I still haven't read
> Erwig's paper...
>
> I know this is probably not fair, but I'm comparing these numbers with a
> C implementation which uses Ruby's C API
tation of
inductive graphs perhaps not very memory-efficient? I still haven't read
Erwig's paper...
I know this is probably not fair, but I'm comparing these numbers with a
C implementation which uses Ruby's C API for its complex data
structures, and a 10,000 nodes graph
On Thu, Jul 10, 2008 at 4:57 PM, Andre Nathan <[EMAIL PROTECTED]> wrote:
> Hello
>
> I'm trying to create a directed graph using the Data.Graph.Inductive.
> The graph is a random graph using the G(n, p) model, that is, each of
> the n nodes is linked to every other node with probability p.
So the
Hello
I'm trying to create a directed graph using the Data.Graph.Inductive.
The graph is a random graph using the G(n, p) model, that is, each of
the n nodes is linked to every other node with probability p.
I'm seeing a large increase of memory usage when n grows (this is using
p = 0.1):
n = 10
Hello,
It's a _complete_ graph, i.e. there is an edge between every two nodes.
I want to compute the minimum spanning tree. Eventually I want to have a
sub-optimal solution for the travelling salesman problem (TSP).
A direct solution for this problem would be:
-- | place a f-minimal elem
Hi Christian,
On Jan 21, 2008 10:57 AM, Christian Maeder <[EMAIL PROTECTED]> wrote:
> Thanks for pointing out this proposal. The actual problem is mkGraph
> that needs all the many edges created beforehand (that's what I wanted
> to avoid).
Well, uh, at the risk of being obvious, if you can avoid
Benja Fallenstein wrote:
> However, if you'd be able to live with
>
> data CGraph a b = CGraph [LNode a] (Node -> Node -> b)
>
> then you should be able to write the instance like this--
>
> instance Graph CGraph where
> empty = CGraph [] (const $ error "Node not in graph")
> isEmpty (CGraph
Thomas Hartman wrote:
> I don't think this will work.
>
> From
>
> http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/src/Data-Graph-Inductive-Graph.html
>
> the minimal implementatin for Graph is
>
> -- | Minimum implementation: 'empty', 'isEmpty', 'match', 'mkGraph',
> 'labNodes'
> ..
Hi,
On Jan 19, 2008 6:05 PM, Thomas Hartman <[EMAIL PROTECTED]> wrote:
> Do you just assume that every two nodes have an edge between them [...]?
Since that's what "complete graph" means, I assume so =-)
- Benja
___
Haskell-Cafe mailing list
Haskell-Ca
Hi Christian,
On Jan 18, 2008 1:55 PM, Christian Maeder <[EMAIL PROTECTED]> wrote:
> data CGraph a b = CGraph [a] (a -> a -> b)
>
> Can I define an instance for the fgl Graph class?
>
> I had no idea how to define empty (except using undefined).
Well, presumably the function does not need to be d
I don't get where the graph edges (Node,Node) are specified.
Do you just assume that every two nodes have an edge between them and
calculate the edge label from the function?
Also, is there a real world / motivating use for a graph defined this way?
thomas.
2008/1/18, Christian Maeder <[EMAIL P
Hi,
Given a complete graph as a list of nodes whose edge labels are given by
a function over two nodes:
data CGraph a b = CGraph [a] (a -> a -> b)
Can I define an instance for the fgl Graph class?
import Data.Graph.Inductive.Graph
instance Graph CGraph where
empty = CGraph [] -- and now?
I
tools/sstderr.pl are two scripts that together
generate bar graphs for an existing measurement tarball. I used the following
shell code to generate graphs for 7 different ghc/bytestring combinations:
(for F in ghc-thorough-6.6.1.tgz \
ghc-thorough-6.8.2.tgz ghc-thorough-6.8.2-bs090
This report combines the measurements from 7 ghc/bytestring combinations on a
single machine, namely:
ghc 6.6.1
ghc 6.8.2
ghc 6.8.2 + bytestring 0.9.0.2
ghc 6.9.20071119
ghc 6.9.20071119 + bytestring 0.9.0.2
ghc head-as-of-noon-2007-12-19
ghc head-as-of-noon-2007-12-19 + bytestring 0.9.0.2
This report compares the hand-tweaked assembly programs with the original
untweaked programs on two vastly different microarchitectures.
This is the command I ran to generate the report:
EXCLUDE='(|-bsl|chunk|count|acc-[23]|fold|lenfil|^c/)' \
tools/merge.pl \
ghc-armada-thorough-6.9.tgz
lusion of the three
benchmarks from Don Stewart (hs/space-bs-c8-count, hs/space-bslc8-count, and
hs/space-bslc8-chunk-4) so they are a couple of holes in the graphs.
The speed pattern is more fun. It makes no sense to compare absolute times
here so the graphs were not rescaled. One would naïvely ex
rday-around-noon + bytestring 0.9.0.2
> One thing that shows up very clearly in the graphs is that the memory
> situation is bad and that Don's recent fix only really solves the
> problem on 6.8.2, not on head.
Can you pinpoint specific programs, with either ghc 6.8.2 or
head, th
o get the draft emails with intro, methodology, discussion, and
conclusion completed yesterday but my brain simply wasn't up to it.
Unfortunately, it still isn't quite up to it :(
Since the perfect is the enemy of the good, I'll post the graphs for all
the above 7 runs now.
The rest
Paul Hudak wrote:
Brian Hulley wrote:
Anyway to get to my point, though all this sounds great, I'm
wondering how to construct an arbitrary graph of Fudgets just from a
fixed set of combinators, such that each Fudget (node in the graph)
is only mentioned once in the expression. To simplify the qu
Taral wrote:
On 12/1/06, Brian Hulley <[EMAIL PROTECTED]> wrote:
This problem is so general (ie converting a cyclic graph into an
expression tree such that each node appears no more than once) that
I'm sure someone somewhere must already have determined whether or
not there can be a solution, th
If you consider just Dags, I believe that this question is equivalent to
asking what set of combinators will allow you to create an arbitrary
composition of functions that allow sharing inputs and returning
multiple results. And I think that one answer to that is the set of
combinators that ma
On 12/1/06, Brian Hulley <[EMAIL PROTECTED]> wrote:
This problem is so general (ie converting a cyclic graph into an expression
tree such that each node appears no more than once) that I'm sure someone
somewhere must already have determined whether or not there can be a
solution, though I don't k
Brian Hulley wrote:
Anyway to get to my point, though all this sounds great, I'm
wondering how to construct an arbitrary graph of Fudgets just from a
fixed set of combinators, such that each Fudget (node in the graph)
is only mentioned once in the expression. To simplify the question,
assume we h
[Broadcast "A" ["B", "C"], Series "B" "D", Series "A" "D"]
=== ???
The Fudgets library provides many combinators eg for looping, but even so, I
don't think there are sufficient combinators to express the above graph
(thou
Josef Svenningsson wrote:
> Devastating! Hence we will need a strict list to do this or some other
> strict data structure.
Seems like the relation between the planets is better described as a
graph, instead of a list. Maybe there's something in Data.Graph that'll
help us make a more straight
[to Haskell-cafe]
At 19:29 17/02/04 -0500, S. Alexander Jacobson wrote:
Thank you for the link to FGL. I also looked at
the boilerplate stuff. If *feels* like there
should be a way to embed the graph stuff in the
boilerplate stuff to allow non-destructive update
of arbitrary object graphs
[Moved to Haskell-Cafe]
Hello!
Cycles sure make it difficult to transform graphs in a pure non-strict
language. Cycles in a source graph require us to devise a way to mark
traversed nodes -- however we cannot mutate nodes and cannot even
compare nodes with a generic ('derived'
David Feuer writes:
> I seem to remember an article about functional graph algorithms using
> extra-lazy arrays. Anyone know if these arrays have appeared in any
> mainstream implementation?
You might mean my paper
"Efficient Graph Algorithms Using Lazy Monolithic Arrays", (a JFP paper),
whi
On Sat, Feb 23, 2002, Jan-Willem Maessen wrote:
> David Feuer <[EMAIL PROTECTED]> writes:
> > I seem to remember an article about functional graph algorithms using
> > extra-lazy arrays. Anyone know if these arrays have appeared in any
> > mainstream implementation?
>
> I assume you're referring
David Feuer <[EMAIL PROTECTED]> writes:
> I seem to remember an article about functional graph algorithms using
> extra-lazy arrays. Anyone know if these arrays have appeared in any
> mainstream implementation?
I assume you're referring to this paper by Thomas Johnsson:
@Article{lazyArray,
au
I seem to remember an article about functional graph algorithms using
extra-lazy arrays. Anyone know if these arrays have appeared in any
mainstream implementation?
David Feuer
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mail
Hi Wojciech,
> I would like to ask you, if you do not know any graph library for
> haskell. I would like to use haskell for prototyping some of
> algorithms on graphs and finite state automata/transducers. In fact
> what I'm looking for is a good (efficient and easy re
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
I used graphs in haskell, but I don't think you'll get anywhere the kind of
efficiency of a language like C++ where you have exact control over
operations and structures
There is the graph code in "functional a
Hi everybody,
I would like to ask you, if you do not know any graph library for
haskell. I would like to use haskell for prototyping some of
algorithms on graphs and finite state automata/transducers. In fact
what I'm looking for is a good (efficient and easy readable) data type
definitio
66 matches
Mail list logo
