Change to ByteString to Text and move it into a Value sum type also discuss how to Parameterize the Pangraph type

[thisiswhereitype]

As discussed in #29 (Support for GML) a change to Text is needed and using a Value Sum type will useful for working with many kinds of data.

type Attribute = [(Text, Value)]
data Value = Integer Integer | Double Double | Boolean Boolean | Text Text

The Pangraph type could be changed:

data Pangraph v e = Pangraph [(Int, v)] [(Int, e)] deriving (Eq)
-- With the 'Value' as before
type ValueGraph = Pangraph Value Value

How will current default implementations work?

• GraphML has fields for keys with values such as n1 where it is nearly a num. Perhaps users can provide a function to return an Int type for their file or if they are not concerned just use Text?

• In the patch (still to be pushed to my fork) preceding this there is a ProtoGraph type which has functions implementing boilerplate code currently required to construct a Graph. A pair of functions completeGraph :: Protograph -> (ProtoVertex -> VertexID) -> (ProtoEdge -> (VertexID, VertexID)) -> Maybe Pangraph and completeGraphWithDefault :: Protograph -> Maybe Pangraph. This could be changed in 0.3.0 to include the value types and return a ValueGraph

[thisiswhereitype]

Additionally my tests did not find increase in runtime to construct or pattern match on Sum types with -O2.

#29

[zouroboros]

Another thing that maybe worth considering is how to properly represent undirected, directed (I noticed this while implementing #39) and multiple edges. By multiple edges I mean edges that share the same endpoints.

[snowleopard]

@zouroboros Regarding multiple edges: we could switch from a list of attributes, to a set of lists of arguments, where each element of the set would correspond to a single edge.

As for undirected graphs, it feels like we could just add a Boolean flag to indicate this.

[zouroboros]

@snowleopard I think that should work (Sets for multi edges and boolean flags). Maybe there is also a way of pushing pushing this into a type parameter of the Pangraph. So that that the base case of a simple graph is not affected by the additional complexity of the multi edge graph case.

[zouroboros]

@thisiswhereitype Regarding the n1 parameter from GraphML files, I think there are two ways:

1. Allow to user to supply a function that turns the n1 values into valid (Integer) Ids
2. Let the parser generate the Ids for edges and nodes and save the n1 parameter as attribute.

[zouroboros]

I played a little bit with different graph representations. You can find my work here. Maybe we can use this as a starting point to make the pangraph type more flexible.

[thisiswhereitype]

1. Allow to user to supply a function that turns the n1 values into valid (Integer) Ids
2. Let the parser generate the Ids for edges and nodes and save the n1 parameter as attribute.

When I implemented this, I opted for 2 but hiding generated ids (almost) entirely from the user. My two reasons being:

1. Assuming a guarantee for uniqueness was better.
2. It seemed more conducive to (parse . seralise === id)

My first step to implementing this was with Pangraph.Internal.ProtoGraph and its BuildGraph interface. Aimed at writing boilerplate needed to bootstrap Pangraph construction.

I played a little bit with different graph representations. You can find my work here. Maybe we can use this as a starting point to make the pangraph type more flexible.

The purpose of this code is the unify un-directed, directed and multi-edge graphs under one type?
type Arrow a b e = (a, b, e) connects a to b with label e?

Is it possible to do this with one container by using a sum type on the edge?

[zouroboros]

I updated the file to make my points more clear.

The purpose of this code is the unify un-directed, directed and multi-edge graphs under one type?
type Arrow a b e = (a, b, e) connects a to b with label e?
Is it possible to do this with one container by using a sum type on the edge?

Actually my aim was more than this: I wanted to find a a type to represent graphs such that as much as possible about the graph can be deduced from the concrete type.

Thats why the graph type is parameterized not only over the edge and vertex labels but also over their container. For example if we consider an (un) directed graph that can be represented as an adjacency matrix. The type of this graph would be: (v is the vertex type): Graph v (None (Undirected v v e)) (S.Set (Directed v v e))
This type makes clear that all edges in this graph are directed and moreover are unique (Set).

Now consider a graph that comes from a pajek file. Pajek files can contain graphs with multiple undirected and directed edges. Hence its type would be Graph v [Undirected v v e] [Directed v v e].

Having such a graph type would allow the parse and write functions to more clearly show what kind of graphs they can process. A function that writes graphs into an adjacency matrix would use the type Graph Int (None (Undirected Int Int ())) (Set Directed Int Int ()) -> Text. The function to write pajek files would have a type Graph v [Undirected v v e] [Directed v v e] -> Text.

Having a sum type of the undirected and directed edges would defeat this purpose. In case all edges for a graph are needed one can retrieve them via the allEdges function.

[snowleopard]

Having a sum type of the undirected and directed edges would defeat this purpose

@zouroboros Why? Sorry I don't understand the reason.

If you need to support graphs that contain a mix of directed and undirected edges, it feels simpler and more direct to have a special edge attribute (e.g. data Direction = Directed | Undirected) associated with every edge. Then if you need to extract only directed ones, just filter by direction.

Perhaps, you'd like to be able to write a function that can only accept graphs with directed edges? Then couldn't you simply treat every undirected edge as two directed?

[zouroboros]

@zouroboros Why? Sorry I don't understand the reason.

I am sorry you are right, I totally forget that we could have three types (undirected, directed and undirected + directed), I somehow thought about only having the sum type.

[thisiswhereitype]

Having such a graph type would allow the parse and write functions to more clearly show what kind of graphs they can process.

Pangraph.Internal.Protograph contains some functions and an interface for reducing boilerplate code - this idea should go into the types used there at least.

The motivation for the Pangraph type is to capture as much detail about every graph entity, this is part of the reason in assigns an internal edgeID to make every edge unique within the graph. Aside from malformed graphs it is a thin record type currently. A sum type added to flag a two-way edge can provide a simple check to convert the type of the Graph.

@zouroboros Can you re-frame you motivations in this light? I agree however on paramterising the graph similarly to how this thread began.

[zouroboros]

Can you re-frame you motivations in this light?

I wanted to try to find a representation that expresses as much about the graph as possible on the type level. For example: This thread began with the idea of parametrizing the Pangraph Type by its vertex and edge labels.

I thought maybe we can express more about a graph at the type level, hence the idea to not only parametrize the Pangraph type with the label types but also with types of the vertex and edge containers (Set vs. List) and the structure of edges (hyperedge vs normal edge).