-
Notifications
You must be signed in to change notification settings - Fork 67
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Thought: We sometimes don't need to distinct Overlay and Connect #80
Comments
@nobrakal Interesting! Yes, of course you can represent graphs (or any algebraic expressions) simply by trees labelled with operators. In fact, this is similar to what I plan to use for labelled graphs :-) See here: https://github.com/snowleopard/alga/blob/edge-labels/src/Algebra/Graph/Labelled.hs#L62-L71 There is one important advantage of the current data type that you didn't mention: its constructors exactly correspond to the algebra of graphs. This also brings us back to the question: do we need to export the constructors? Maybe we shouldn't. Then we'll be free to choose whatever internal representation we like, including yours. However, I still prefer to keep the 'vanilla' version of the data type in the library simply because it emerges so naturally from the underlying mathematics. If the goal is, however, to find the most efficient representation possible, I'm quite sure it will actually be something else and it will be complex -- more complex than what you suggest. There is also a relevant discussion here: #61. |
Haha, I missed this!
Finally, maybe exporting constructors is not the right idea to have. With some GHC hack, we can allow pattern-matching without constructors, using for example ViewPatterns |
Yes, |
An other option is PatternSynonyms. It is much more like what we need to hide constructors, it provide synonyms. There is a naming problem: A pattern cannot have the same name as the constructor... But one can pose: data Graph a = EmptyG
| VertexG a
| OverlayG (Graph a) (Graph a)
| ConnectG (Graph a) (Graph a)
deriving (Foldable, Functor, Show, Traversable)
pattern Empty :: Graph a
pattern Empty = EmptyG
pattern Vertex :: a -> Graph a
pattern Vertex a = VertexG a
pattern Overlay :: Graph a -> Graph a -> Graph a
pattern Overlay a b = OverlayG a b
pattern Connect :: Graph a -> Graph a -> Graph a
pattern Connect a b = ConnectG a b
{-# COMPLETE Empty, Vertex, Overlay, Connect #-} Some advantages:
|
Yes, this is a promising approach. While we're thinking about a more efficient internal representation, I think it is also important to consider packing arguments to multi-way data Operator = Overlay | Connect
data Graph a = Leaf a | Node Operator [Graph a]
empty = Node Overlay []
vertex = Leaf
overlays = Node Overlay
connects = Node Connect This works thanks to the associativity of both operators. |
I played a bit this afternoon and came to: data Operator = OverlayG | ConnectG deriving (Eq,Show)
data Graph a = Leaf a | Node Operator [Graph a]
deriving (Foldable, Functor, Show, Traversable)
pattern Empty :: Graph a
pattern Empty <- Node _ [] where
Empty = Node OverlayG []
pattern Vertex :: a -> Graph a
pattern Vertex a = Leaf a
pattern Overlay :: Graph a -> Graph a -> Graph a
pattern Overlay a b <- (view -> Node OverlayG [a,b]) where
Overlay a b = Node OverlayG [a,b]
pattern Connect :: Graph a -> Graph a -> Graph a
pattern Connect a b <- (view -> Node ConnectG [a,b]) where
Connect a b = Node ConnectG [a,b]
{-# COMPLETE Empty, Vertex, Overlay, Connect #-}
{-# COMPLETE Empty, Vertex, Node #-}
view :: Graph a -> Graph a
view (Node c [a,b]) = Node c [a,b]
view (Node c (x:xs)) = Node c [x,Node c xs]
view g = g This is passing tests, combining view patterns and patterns synonyms can lead to some interesting results ^^. Sadly, I think this will slow down the whole thing, since the traditional foldg will not be so efficient ! |
The results of the bench suite, even using custom foldg like the don't require the Connect of Overlay information, for example, I redefined foldg'' :: b -> (a -> b) -> ([b] -> b) -> Graph a -> b
foldg'' e v o = go
where
go Empty = e
go (Vertex x ) = v x
go (Node _ xs) = o $ map go xs
hasVertex :: Eq a => a -> Graph a -> Bool
hasVertex x = foldg'' False (==x) or The result of the benchmarking suite
|
We might call such folds "blindfolds" :-) Are numbers > 1 good? I'm sure I'll keep forgetting that :D Maybe should add By the way, have you also done |
I added a small reminder:
So these are very bad values ^^. I just saw that I haven't changed I tired with more specialized I have pushed the try here: https://github.com/nobrakal/alga/tree/betterRepresentation A bench is running: https://travis-ci.com/nobrakal/alga/jobs/130222270 |
I'm afraid this doesn't help me, still takes me a while to understand =) Why not add obvious
It's quite surprising to see such a slowdown here. We should be doing less work to traverse a tree and find all vertices -- do you have any ideas why this happens? By the way, it may be useful to test the whole |
It is done now :)
Corrected now, it was again a problem with foldl :) Now vertexListDescription: Produce a list of the vertices in the graph Mesh
Clique
SUMMARY:
There was 3 ex-aequo ABSTRACT:
My foldgWithoutEmpty' :: (a -> b) -> ([b] -> b) -> ([b] -> b) -> Graph a -> b
foldgWithoutEmpty' f o c = go
where
go (Leaf a) = f a
go (Node co xs) = case co of
OverlayG -> o $ map go xs
_ -> c $ map go xs
induce :: (a -> Bool) -> Graph a -> Graph a
induce p = foldgWithoutEmpty' (\x -> if p x then Vertex x else Empty) (overlays . filter k) (connects . filter k)
where
k (Node _ []) = False -- Constant folding to get rid of Empty leaves
k _ = True removeVertexDescription: Remove a vertex of the graph Mesh
Clique
SUMMARY:
There was 4 ex-aequo ABSTRACT:
Yeah of course. I don't really now where to do that (because I need to extend the configuration file in |
Thanks @nobrakal! Perhaps, for |
Ooops, I spent some time to figure out the the bench-suite was broken. A mesh wasn't a real mesh ! Here is the corrected times: removeVertexDescription: Remove a vertex of the graph Mesh
Clique
Circuit
SUMMARY:
There was 2 ex-aequo ABSTRACT:
So there is a surprising drop for clique. Again, strangely, induce :: (a -> Bool) -> Graph a -> Graph a
induce p = go
where
go (Leaf a) = if p a then Leaf a else Empty
go (Node co xs) = Node co $ filter k $ map go xs
k (Node _ []) = False -- Constant folding to get rid of Empty leaves
k _ = True Is not faster, it is worse: removeVertexDescription: Remove a vertex of the graph Mesh
Clique
Circuit
SUMMARY:
ABSTRACT:
What do you mean ? |
I mean the function signature should be: foldgWithoutEmpty' :: (a -> b) -> (Operator -> [b] -> b) -> Graph a -> b
foldgWithoutEmpty' v op g = ... The function |
Yep you were right, it boost a bit performances, but nothing extraordinary: foldgWithoutEmpty' :: (a -> b) -> (Operator -> [b] -> b) -> Graph a -> b
foldgWithoutEmpty' f h = go
where
go (Leaf a) = f a
go (Node co xs) = h co $ map go xs
induce :: (a -> Bool) -> Graph a -> Graph a
induce p = foldgWithoutEmpty' (\x -> if p x then Vertex x else Empty) (\co t -> Node co $ filter k t)
where
k (Node _ []) = False -- Constant folding to get rid of Empty leaves
k _ = True removeVertexDescription: Remove a vertex of the graph Mesh
Clique
Circuit
SUMMARY:
There was 3 ex-aequo ABSTRACT:
|
Again, this is a problem with The same code benchmarked using alga's clique: Clique
|
I agree: |
So I don't know if we can make a better |
Note that the implementation described in #84 (comment) shows great results here
Even with an algebraic clique:
|
Interesting, that's an impressive speed up. |
Hi,
I did not found a better title, but here is the idea.
Reading the
Algebra.Graph
code, I found there was some functions usingfoldg
with the same two last arguments.For example:
While searching for improvements, I thought that there was actually a duplication of information:
Overlay
andConnect
both kinda join two graphs.So I came to
(Once again I am bad for names)
You only have to change
and then replace every occurrence of the constructor by these counterpart.
Pros
It allows to define:
Which is faster than foldg (hasVertex is about 1.40 times faster for example using
hasEdge = foldg' False (==x) (||)
)Cons
Uses can no more play with constructors, at least not simply.
Foldg become a bit less efficient. I had to redefine
induce
:removeVertex
is1.2
times better in the actual library than with this change, buthasEdge
become faster of2
times. I don't now yet why.There is I think more Cons than Pros, but it can worth some investigation
The text was updated successfully, but these errors were encountered: