Skip to content
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

Minimum Spanning Tree for labelled graphs #187

Open
TheChouzanOne opened this issue Apr 7, 2019 · 6 comments
Open

Minimum Spanning Tree for labelled graphs #187

TheChouzanOne opened this issue Apr 7, 2019 · 6 comments

Comments

@TheChouzanOne
Copy link

TheChouzanOne commented Apr 7, 2019

I want to start thinking how to generate a Minimum Spanning Tree. However, a big problem is stopping me.

Both Kruskall and Prim assume that the graph is connected, however, it doesn't seem to be a way to know if that condition holds, or a type safe representation of connected graphs.

I believe that a simple typesafe representation could be implemented for connected labelled graphs by tweaking the way connect zero x y works, as if vertexSet xvertexSet y=Ø, then the resulting graph WILL be disconnected, but if x and y share at least 1 vertex (assuming x and y are connected), then the graph will still be connected.

On the other hand, MST algorithm could just try to add as much edges as possible to connect the vertices, but could generate a disconnected graph (a Forest).

What is the optimal path to tackle this problem?

@TheChouzanOne TheChouzanOne changed the title Kruskall for labelled graphs Minimum Spanning Tree for labelled graphs Apr 7, 2019
@TheChouzanOne
Copy link
Author

After thinking about the simple typesafe representation. Even given that property, we need to stop the user of the API to try and overlay two graphs where their vertexSets intersect in at least one vertex. Implementing a new type (ConnectedAdjacencyMap for example) wouldn't stop that, and using Maybe ConnectedAdjacencyMap is not an acceptable solution.

Maybe just trying to compute a MST with as much edges as possible would be best then.

@snowleopard
Copy link
Owner

@TheChouzanOne I think it's useful to have both the MST algorithm returning Maybe (Tree a) as well as minimum spanning forest algorithm returning Forest a. The former will probably be implemented via the latter as follows:

mst :: (Ord a, Ord e) => AdjacencyMap e a -> Maybe (Tree a)
mst x = case msf x of
    [t] -> Just t
    _   -> Nothing

msf :: (Ord a, Ord e) => AdjacencyMap e a -> Forest a
msf = ...

One aspect which is not clear to me is how to capture edge labels in the resulting trees and forests. Perhaps, we need custom data types for labelled trees and forests, i.e. Tree e a and Forest e a.

@TheChouzanOne
Copy link
Author

@snowleopard I totally forgot about the lack of labels for Data.Tree and Data.Forest.

The first idea that comes to my mind is to slightly change the structure of Tree's subForest like so:

Node
    rootLabel :: a
    subForest :: [(e, Forest a)]

type Forest e a = Tree e a

where subForest would stop being a Forest, so its name might be changed. It now represents a list of tuples, where the first element is the label of the connection between rootLabel and the Forest's rootLabel.

I am not sure how difficult it would be to mimic Data.Trees module for this new type, but if you think the structure makes enough sense, I could start working on it. Or, use another existent data structure to represent the result of mst like a normal AdjancencyMap e a.

@TheChouzanOne
Copy link
Author

TheChouzanOne commented Apr 10, 2019

Update: I implemented a simple starting kruskall algorithm which can handle connected and unconnected graphs. The thing is that it just returns an AdjacencyMap e a, as I haven't thought about how to represent a tree or forest with edge labels.

The current API for the function is

kruskall :: (Monoid e, Ord e, Ord a, Eq a) => (e -> e -> Ordering) -> AdjacencyMap e a -> AdjacencyMap e a

It takes a function to determine how to choose edges and an AdjacencyMap e a to apply the algorithm to.

If you want to take a closer look, here's the code.

@snowleopard
Copy link
Owner

snowleopard commented Apr 13, 2019

@TheChouzanOne Yes, I think we'll need to add a module like Data.Tree.Labelled with the definitions for labelled trees and forests. The msf algorithm will then need to return a Forest e a.

I don't understand why you ask both for dictionary Ord e and a comparison function e -> e -> Ordering. A dictionary alone should be sufficient.

@TheChouzanOne
Copy link
Author

@TheChouzanOne Yes, I think we'll need to add a module like Data.Tree.Labelled with the definitions for labelled trees and forests. The msf algorithm will then need to return a Forest e a.

I will start thinking about that concern then.

I don't understand why you ask both for dictionary Ord e and a comparison function e -> e -> Ordering. A dictionary alone should be sufficient.

This function is just a starting point and might help to build the actual mst and msf functions. About the comparison function, it wast an idea to leave it kind of general to implement more functions on top of it. For example, maybe for some reason, a user would want a "maximum spanning tree" even though he is using distances (I don't really know if this is pausible), so he could call a more general generalMsf which takes a sorting function of his choice to decide which edges should be taken, but I wasn't sure if it was a good idea.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants