Comments (10)
It's fine, I don't feel strongly about it.
from alga.
Released: http://hackage.haskell.org/package/algebraic-graphs-0.0.5.
from alga.
There is one performance aspect to consider: constructing GraphKL
from AdjacencyMap
takes time, so if the user would like to run multiple Data.Graph
algorithms, it would be better to construct GraphKL
once and then reuse it. If we drop GraphKL
, we'll need to somehow cache it within AdjacencyMap
.
from alga.
If we drop GraphKL, we'll need to somehow cache it within AdjacencyMap.
Good point. Probably the easiest way is to have a lazy pair (AdjacencyMap, GraphKL)
(or an equivalent data type) where one field is lazily constructed in terms of the other.
from alga.
@feuerbach Is this what you had in mind?
https://github.com/snowleopard/alga/blob/master/src/Algebra/Graph/AdjacencyMap/Internal.hs#L90-L102
I hope I'll finish the refactoring by the end of this week and will release the new version.
from alga.
Yes, it is what I had mind. I think you may want to make the adjacencyMap
field strict.
from alga.
I think you may want to make the
adjacencyMap
field strict.
Good point! I'll do this.
This brings me to the question I've been thinking about for some time (which probably deserves a separate issue, but I'll start here).
Another interesting implementation to consider is:
data AdjacencyMap a = Empty
| Vertex a
| Overlay (AdjacencyMap a) (AdjacencyMap a)
| Connect (AdjacencyMap a) (AdjacencyMap a)
| Cached a
data Cached a = Cached
{ expression :: AdjacencyMap a -- subexpression
, adjacencyMap :: !(Map a (Set a)) -- cached adjacency map representation
, graphKL :: !(GraphKL a) } -- cached Data.Graph representation
(Or something isomorphic).
Here we keep the expression tree lazy, which is cheap (unless it contains a lot of cached subtrees).
In this way, I think, we can make AdjacencyMap
an instance of higher-kinded graphs with standard Functor
and Monad
instances, by keeping expressions Cache
-free during most of the tree transformations.
When an expression needs to be "evaluated", we turn it into a Cached
one, which will require the Ord a
constraint, but at this point we don't care.
from alga.
This reminds me of various attempts to turn Set into a Functor/Monad — there were a few papers on this topic you may want to check out.
from alga.
Yes, indeed. I found a good write-up on this by Oleg Kiselyov: http://okmij.org/ftp/Haskell/set-monad.html. I'll see if anything can be adapted to our case.
It just occurred to me, that my above data type can be generalised as follows:
-- Generic graphs with tagged subgraphs
-- For example, TaggedGraph String a can be used to attach names to selected subgraphs of a graph
data TaggedGraph t a = Empty
| Vertex a
| Overlay (TaggedGraph t a) (TaggedGraph t a)
| Connect (TaggedGraph t a) (TaggedGraph t a)
| Subgraph t (TaggedGraph t a)
instance Functor (TaggedGraph t) where ...
instance Monad (TaggedGraph t) where ...
-- We can now define AdjacencyMap as a TaggedGraph
data Cache a = Cache !(Map a (Set a)) !(GraphKL a)
type AdjacencyMap a = TaggedGraph (Cache a) a
But wait -- TaggedGraph
is exactly one of the data types I proposed for edge-labelled graphs in #17!
I think something interesting is going on here.
from alga.
@feuerbach Note that I flipped the order of arguments to dfsForestFrom
in the last commit -- the new one seems to be more natural/convenient. Let me know if you disagree.
from alga.
Related Issues (20)
- Hackage Release HOT 5
- How to handle goodness inherited from other libraries HOT 2
- Bump upper bound for base-compat for version 0.4 on Hackage HOT 4
- Unable to use ghcid HOT 6
- Algorithms should be in terms of typeclasses not data structures HOT 15
- Acyclic graphs with Int labels HOT 5
- Tests failed to build with QuickCheck 2.14.2
- Multitree HOT 3
- Monoid instance HOT 6
- support for GraphViz "HTML strings" for node or edge labels HOT 1
- Add benchmarks to CI HOT 2
- Supporting different node and edge types HOT 7
- v0.6 fails to build with GHC 8.0 and 8.2 HOT 3
- Doubt about decorating a Graph HOT 4
- Compatibility with mtl-2.3 HOT 2
- Smart constructor for Symbol rather than requiring -XOverloadedLists HOT 1
- Proposal : foldgM HOT 2
- Algebra.Graph.Labelled.AdjacencyMap.edges appears to be broken HOT 2
- Semigroup version of Algebra.Graph.Labelled.AdjacencyMap HOT 7
- Bump "deepseq" dependency bounds to 1.5.0.0 HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from alga.