Add Graph datatype

[snowleopard]

Graph is a key datatype for the scenco project as well as for some others. Some implementations are available in https://github.com/tuura/process-mining and https://github.com/tuura/compote.

This may well be put in a separate library graph for all projects to rely upon.

[allegroCoder]

This might be useful: https://hackage.haskell.org/package/containers-0.5.7.1/docs/Data-Graph.html

[allegroCoder]

An idea:

Wadler, for defining a tree, defines a set which can contain either nothing or a Node, which is iteratively composed by a left set, a value and a right set.

data Set a = Nil | Node (Set a) a (Set a)

Since in a graph, every node could be potentially connected to several nodes. each node should be a list, then:

data Graph a = Nil | [Node [Graph a]]

We could therefore refine such a data type by providing a name and a Boolean function to each of the node:

data Graph a = Nil | [Node Name Function [Graph a]]

@snowleopard could I ask your opinion? Do you think the above to be something which makes sense at least?

edit: It probably does not make sense. I am not sure how to deal with an object which can be a single object or a list of object. I am trying to write a function for listing all the nodes from the data type above, but I am having some problems.

[allegroCoder]

Another idea I am trying to implement. The general idea is: the Graph is seen as a list of Piece which can either be a Node or an Edge. I am still implementing it, but we should not allow the insertion of multiple nodes with the same name, as well as cyclic arcs.

I am not sure if it is the best possible representation, likely not, but it should at least a starting point. Any idea on how I could improve it is welcome!

module Graph (visualise, insertNode, insertArc) where

--import Tuura.Formula

type Name = String
type Function = String -- Formula

data Vertex = Vertex Name Function
data Piece = Node Vertex | Edge Vertex Vertex

type Graph = [Piece]

visualise :: Graph -> String
visualise []                                             = []
visualise ((Node (Vertex n _)):ps)                       = n ++ " " ++ visualise ps
visualise ((Edge (Vertex source _) (Vertex dest _) ):ps) = source ++ "->" ++ dest ++ " " ++ visualise ps

insertNode :: Piece -> Graph -> Graph
insertNode (Edge _ _) gs = gs
insertNode v gs          | (exist v gs == False)   = v:gs
                         | otherwise            = gs

insertArc :: Piece -> Graph -> Graph
insertArc (Node _) gs = gs
insertArc e gs        = e:gs

exist :: Piece -> Graph -> Bool
exist (Node (Vertex n f)) gs = or [ name == n | node <- gs, isNode node, name <- nodeName node]

isNode :: Piece -> Bool
isNode Node _   = True
isNode Edge _ _ = False

isArc :: Piece -> Bool
isArc Node _   = False
isArc Edge _ _ = True

getName ::
...

[snowleopard]

@allegroCoder Interesting ideas! You can certainly give them a try! Even if we end up using a different design this may be a useful exercise :-) The second approach is a bit similar to what I had in compote: https://github.com/tuura/compote/blob/master/src/haskell/PG.hs#L41-L44.

When I started this issue I actually had in mind something like this: https://github.com/tuura/process-mining/blob/master/src/Tuura/Graph.hs.

[allegroCoder]

I kept developing the second approach. And I came up with the file below: https://github.com/allegroCoder/Graph/blob/master/graph.hs

Features of the module:

• Following graph: g = A -> B -> C + D -> (E F) + G (Figure below) will be represented as follows: {(A,B); (B,C); (D,E); (D,F); G}
• Node / Edges repetitions are not allowed: {(A,B); (B,C);(D,E); (D,F); G; D; E} -> {D} and {E} nodes are removed if the edge in between is inserted.
• Transitive and Cyclic edges are not allowed. Conditions for an edge to be inserted: 1) The two vertices must not be connected already (also via other vertices in between) 2) The two vertices must not be connected backward (cyclic edge) 3) The arc must not exist already
• Conditions for a node to be inserted: 1) The node must not be present already 2) The node must not be present as a source / destination of an edge

@snowleopard: Could you take a look at the file, and let me know what I can improve. I tested the model a bit and it seems working ok. However, I want to prepare a proper test before trying to insert this module into SCENCO, as well as developing other functions which can be useful in the future.

[snowleopard]

This is good effort, but there is a lot of room for improvement. I suggest we meet and go through the code together.