search

snowleopard / alga

Algebraic graphs
MIT License
716 stars 68 forks source link

Idea: Add SubGraph data type #61

Open anfelor opened 6 years ago

anfelor commented 6 years ago

The idea is to decouple the graph creation functions from the actual graph creation. In code:

data SubGraph a = Vertex a
  | Clique [a]
  | Biclique [a]
  | ...

clique :: [a] -> Graph (SubGraph a)
clique = vertex . Clique

expand :: Graph (SubGraph a) -> Graph a
expand (Clique as) = -- current clique implementation

This should have the same performance characteristics as the current implementation, since it is just laziness made explicit. It is also very similar to the Cached data type in #19. There could be the following benefits:

  1. The Graph data type could be made strict. I am not sure if it is a good idea, but it would be possible without too much of a performance hit.
  2. Some algorithms could benefit from this, since it gives a direct representation to some induced subgraphs. Diameter, shortest paths,.. some algorithms are more performant if the structure on which they operate is known.
  3. In combination with modular decomposition this would be extremely useful.

A reason not to do it is that it is so far unclear, which algorithms actually benefit from such a structure. Since the SubGraph is not necessarily a module, it is not clear whether a algorithm could take advantage of it.

Ultimately the usefulness of this proposal depends a lot on the subgraphs and algorithms. Do you have some ideas @snowleopard? I have so far experimented with Hanoi and Turan graphs, but I have not found anything useful.

snowleopard commented 6 years ago

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!

anfelor commented 6 years ago

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.

snowleopard commented 6 years ago

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.

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.

snowleopard commented 6 years ago

@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.

nobrakal commented 6 years ago

@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 !