CODEWITHSUNDEEP
haskellgraphtypeclass
Lance Pollard
Lance Pollard

Reputation: 79178

How to define a bipartite graph in Haskell

Trying to understand how these parameterized types work in Haskell, such as these:

data List a = Nil | Cons a (List a)
data Either a b = Left a | Right b
data Tree a = Nil | Node a (Tree a) (Tree a)
data Tree = Branch [Tree]
data Tree a = Node a [Tree a]

To make it a little more complicated I wanted to see what the definition looks like for a bipartite graph, basically a graph with two sets of nodes where the nodes only connect to nodes of the other set.

So.. (in JavaScript).... An example of how the data would be connected is like this:

var typeA_node1 = { id: 'a1' }
var typeA_node2 = { id: 'a2' }
var typeA_node3 = { id: 'a3' }

var typeB_node1 = { id: 'b1' }
var typeB_node2 = { id: 'b2' }
var typeB_node3 = { id: 'b3' }

typeA_node1.right = typeB_node3
typeB_node3.right = typeA_node2

typeA_node2.right = typeB_node2
typeB_node2.right = typeA_node3

typeA_node3.right = typeB_node1

Basically, a--b--a--b--a--b--a--b, a is always connected to b only, never to a. An a can be connected to many b nodes, I just didn't show that in the example.

Wondering how to define this properly using data or type in Haskell (or something else).

Upvotes: 2

Views: 221

Answers (1)

Elmex80s
Elmex80s

Reputation: 3504

I would use Data.Set for constructing both sets of vertices and another one for the edges. Now wrap them in a module where you hide them. 

module BiPartiteGraph (create) where


import qualified Data.Set as Set 


data BiPartiteGraph a = BiPartiteGraph (Set.Set a) (Set.Set a) (Set.Set (a, a)) -- (U, V, E)


-- Construct a BiPartiteGraph from a list of edges
create :: Ord a => [(a, a)] -> BiPartiteGraph a
create _ = undefined


-- Implementation of the show function 
instance (Show a) => Show (BiPartiteGraph a) where
    show _ = undefined

Upvotes: 2

Related Questions