Comments (5)
@snowleopard Oops, sorry for this, I copied/pasted my comment is the wrong issue, I just deleted it (here it was totally without sense :p ) and moved to the right issue !
from alga.
Interesting. I haven't though about exactly your version of SubGraph
, but I was exploring ideas of extending the Graph
datatype (in a different module) with some higher-level combinators. For example:
data Graph a where
Empty :: Graph a
Vertex :: a -> Graph a
Overlay :: Graph a -> Graph a -> Graph a
Connect :: Graph a -> Graph a -> Graph a
Fmap :: (a -> b) -> Graph a -> Graph b
Bind :: (a -> Graph b) -> Graph a -> Graph b
...
This also allows some efficient algorithms.
My initial impression is that your SubGraph
will end up containing too many constructors making it quite painful to write algorithms that can efficiently manipulate such graphs... But I may be wrong.
I'd like to explore this direction.
The
Graph
data type could be made strict
I think we could simply have a strict version of this type, e.g. Algebra.Graph.Strict
. I'd like to keep the default implementation lazy, as it's more idiomatic Haskell.
Some algorithms could benefit from this, since it gives a direct representation to some induced subgraphs.
Can you give a specific example?
In combination with modular decomposition this would be extremely useful.
Yes, that would be great!
from alga.
with some higher-level combinators.
Absolutely, but why should they be in Graph
? An algorithm working on graphs would have to consider all of them and there would be no expand
function to eliminate them from the algebra. To me they sound like a perfect fit for a SubGraph
type.
your SubGraph will end up containing too many constructors
That is true, but the algorithm doesn't need to consider all constructors, just call expand
and use the normal algebra of graphs!
I think we could simply have a strict version of this type, e.g. Algebra.Graph.Strict.
Sounds good!
Can you give a specific example?
Only trivial examples so far where we could get constant instead of linear time; topSort
just using the list of a Clique
instead of considering all the unnecessary edges. The speedup probably wouldn't justify the additional boilerplate so I have to admit it's closer to an idea than a proposal at the moment.
from alga.
Absolutely, but why should they be in
Graph
? An algorithm working on graphs would have to consider all of them and there would be noexpand
function to eliminate them from the algebra. To me they sound like a perfect fit for aSubGraph
type.
Right, I see what you mean. Perhaps, this could indeed be useful, but I also can't come up with convincing examples. The topSort
on Clique
speed-up can be achieved in many other ways.
The speedup probably wouldn't justify the additional boilerplate so I have to admit it's closer to an idea than a proposal at the moment.
Let's keep this issue open. Perhaps, we'll come up with a good use for the SubGraph
datatype.
from alga.
@nobrakal Thanks! I didn't really explain what I meant by experiments: I meant to measure performance of graph consumption algorithms: if they take longer, it means some extra work was needed. So you should pick the NFData
instance which leads to fastest graph deconstruction.
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.