Vertex-labelled adjacency maps

[srid]

I just learned that the library supports edge-labelled adjacency maps:

newtype AdjacencyMap e a = AM {
    adjacencyMap :: Map a (Map a e) } deriving (Eq, NFData)

What do you think of having a edge and vertex labelled adjacency map? Something like:

newtype AdjacencyMap v e a = AM {
    adjacencyMap :: Map a (v, Map a e) } deriving (Eq, NFData)

I could look into writing this if this is worth adding to the library.

[srid]

I suppose I could get away with it by storing the vertex-label in the a and use elemAt and lookupIndex to pull the label out of the map for a given vertex, though it seems slightly hacky.

data Vertex key label = Vertex key label  -- A vertex key with label

instance Ord key => Ord (Vertex key label)
  compare (Vertex k1 _) (Vertex k2 _) = compare k1 k2

-- Example
data MyEdgeLabel = ThisEdge | ThatEdge
data MyVertexlabel = ThisVertex | ThatVertex

type MyGraph = AdjacencyMap MyEdgeLabel (Vertex Int MyVertexLabel)

[srid]

I'm thinking perhaps we can call it a "property graph" and then redefine the edge-labelled graph using it:

A labeled-property graph model is represented by a set of nodes, relationships, properties, and labels. Both nodes of data and their relationships are named and can store properties represented by key/value pairs. Nodes [vertices] can be labelled to be grouped. The edges representing the relationships have two qualities: they always have a start node and an end node, and are directed;[6] making the graph a directed graph. Relationships [edges] can also have properties. This is useful in providing additional metadata and semantics to relationships of the nodes. https://en.wikipedia.org/wiki/Graph_database#Labeled-property_graph

So we would have a new module:

-- Algebra.Graph.Property.AdjacencyMap
newtype AdjacencyMap v e a = AM {
    adjacencyMap :: Map a (v, Map a e) } deriving (Eq, NFData)

with the edge-labelled module either becoming redundant or redefined using the new one:

-- Algebra.Graph.Property.AdjacencyMap
type AdjacencyMap e a = Algebra.Graph.Property.AdjacencyMap () e a

@snowleopard What do you think?

[snowleopard]

@srid My personal approach to labelling vertices has always been like you describe in your 2nd comment:

-- A data type of vertices
data Vertex = ...

-- A data type corresponding to vertex labels
data Label = ...

-- A way to extract the label of a vertex
vertexLabel :: Vertex -> Label

-- Custom equality and comparison instances that ignore vertex labels
instance Eq Vertex where ...
instance Ord Vertex where ...

-- Actual graph datatypes: with and without edge labels
type Graph1 = AdjacencyMap Vertex
type Graph2 = Labelled.AdjacencyMap EdgeLabel Vertex

I like this approach because it does not involve any additional complexity in the library itself. On the other hand, adding "property graphs" which you describe involves quite a lot of work for duplicating all existing graph modules: empty/non-empty, edge-labelled/edge-unlabelled, ADT-based/Map-based, etc.

My preference would be to avoid this, as long as the solution with extracting labels from vertices works for you. Does it? You say it "seems slightly hacky" -- could you elaborate on this?

[srid]

You say it "seems slightly hacky" -- could you elaborate on this?

Mainly having to wrap vertices with emptyLabel (see below) before passing them to library functions like edge, edgeLabel, replaceEdge, replaceVertex, etc. But it is not that janky, so can definitely live with it. Just succeeded in wrapping in the labelled adjacency map for my purposes, so I'll close this!

-- | A labelled type that ignores the label value in Eq and Ord instances
newtype Labelled a label = Labelled { unLabelled :: (a, label) }
  deriving Generic

emptyLabel :: Monoid label => a -> Labelled a label
emptyLabel x = Labelled (x, mempty)

labelled :: a -> label -> Labelled a label
labelled x l = Labelled (x, l)

unLabel :: Labelled a label -> a
unLabel = fst . unLabelled

getLabel :: Labelled a label -> label
getLabel = snd . unLabelled

instance Eq a => Eq (Labelled a label) where
  (==) = on (==) unLabel

instance Ord a => Ord (Labelled a label) where
  compare = on compare unLabel

[snowleopard]

Just succeeded in wrapping in the labelled adjacency map for my purposes, so I'll close this!

@srid Great, thanks! Feel free to reopen if you come up with some API improvements for supporting vertex-labelled graphs.

[srid]

I just found myself needing this again, but this time I'm not so sure about the Labelled type.

An adjacency map is defined as Map a (Map a e). The storage of vertices is of the O(n ^ 2) O(n + m). If I store the vertex label along with vertex, there would be needless repetitions, would it not? And there is no (type-level) guarantee that the label remains the same regardless of its position in the outer or inner map. The type used in the original issue description does give this guarantee (because vertex label is indexed by the outter map).

What do you think @snowleopard ? I would like this to simplify error handling in neuron.

[snowleopard]

An adjacency map is defined as Map a (Map a e). The storage of vertices is of the O(n ^ 2).

@srid I don't think that's right: the memory complexity of this representation is O(n + m) for a graph with n vertices and m edges.

However, there is indeed some repetition: a vertex is stored O(d) times where d is its degree, i.e. the number of neighbours.

To avoid this, you can just use the approach I described in this comment: store a graph and the labelling function separately as type VertexLabelledGraph a = (Graph a, a -> VertexLabel), where Graph can be any graph representation supported in the library, including the edge-labelled version, and a can be something cheap like Int.

[srid]

@snowleopard The problem with that approach is that, when you are using graph to represent items that can only be known at runtime, a -> VertexLabel cannot be anything but a partial function. A standard implementation is:

getLabel :: a -> VertexLabel
getLabel = fromMaybe (error "Missing vertex") . flip Map.lookup labels 

I would like the guarantee that for every vertex there exists a label, and vice-versa. Just as it is the case with edge-labels in the current edge-labelled adjacency maps.

[snowleopard]

I would like the guarantee that for every vertex there exists a label, and vice-versa.

Hmm, if all you have is a partial Map from vertices to labels (which you call labels), I'm not sure how you plan to avoid using fromMaybe somewhere.

In your earlier version (with potential duplication), where the vertices had the type (a, label), how did you ensure that all label components are non errors and that all pairs were "bijective"?

This doesn't seem to be a problem related only to graphs. Imagine that you'd like to store a list of labelled as, possibly with repetitions. How would you do that? We discussed two options:

• [(a, label)]
• [a]

Maybe there are others? I think if you find a good answer for lists, it should lead to a similar solution for graphs.

[srid]

Hmm, if all you have is a partial Map from vertices to labels (which you call labels), I'm not sure how you plan to avoid using fromMaybe somewhere.

Not a partial Map; I actually know all the vertices ahead (in my application, they refer to the note files in a directory; where filename is vertex, and note content is the 'label').

Consider an unique list of objects [x] and a hash function x -> v (known ahead to be bijective) which produces the short vertex ID for a given object. From this list and the hash function, I can build a labelled graph without involving error. In theory, x is the vertex label; the question is how to represent this totally (without involving error) in the graph datastructure such that any graph algorithm that results in a container of vertices will include the vertex label along with it?

In my application, v = filename, and x is, for all intents and purposes, the file contents.

I think if you find a good answer for lists, it should lead to a similar solution for graphs.

Lists are easy. I'd simply use [(v, x)] - i.e., a list of pairs of filename and its content. It has no repetitions (as long as filenames are unique, which they are). How would one do this in graph?

[snowleopard]

@srid Thanks for further details, I think I understand your problem better now.

Consider an unique list of objects [x] and a hash function x -> v (known ahead to be bijective)

I think here is where I'm confused. It's not enough that you know that the function is bijective. You need to prove this to the compiler by exhibiting the inverse mapping v -> x. Once you show it, the approach based on (Graph v, v -> x) seems to work.

Furthermore, assuming your belief that the function is bijective is justified, you shouldn't be worried about extracting v -> x from a Map v x and fromMaybe. After all, it will only fail if there is a v (filename) for which you don't have a corresponding x (contents), thus contradicting your assumption.

[snowleopard]

@srid Actually, I now see the value of the vertex-and-edge-labelled graph representation that you proposed in the very first comment: Map a (v, Map a e). Indeed, this seems to solve your problem, but I'm not sure how to interpret the resulting data type in the context of algebraic graphs :)

(I mean, it looks fine as a possible representation but we don't have a corresponding algebra yet.)

((Also, I'm a bit terrified about adding yet another representation to the library.))

[srid]

Yea, fair enough.

Meanwhile I have a come up with a solution using type famillies:

From https://github.com/srid/neuron/blob/f58e408/src/Data/Graph/Labelled/Type.hs#L11-L27

data LabelledGraph v e = LabelledGraph
  { graph :: LAM.AdjacencyMap e (VertexID v),
    -- Guaranteed to contain exact vertices in graph, using smart constructors
    vertices :: Map (VertexID v) v 
  }

with the associated class:

-- | Instances of this class can be used as a vertex in a graph.
class Vertex v where
  type VertexID v :: Type
  -- | Get the vertex ID associated with this vertex.
  --
  -- This relation is expected to be bijective.
  vertexID :: v -> VertexID v

This works, but I find myself writing adapters to graph functions to transform the input and output, eg:

topSort :: (Vertex v, Ord (VertexID v)) => LabelledGraph v e -> Either (NonEmpty v) [v]
topSort g =
  bimap (fmap (getVertex g)) (fmap (getVertex g))
    $ Algo.topSort
    $ LAM.skeleton
    $ graph g

[snowleopard]

@srid Many thanks for sharing your approach.

What is getVertex in the last snippet? Is it an unsafe lookup from the vertices map?

[srid]

getVertex uses Map.lookup - yes in theory it is unsafe, but the map was constructed using a smart constructor in mkGraphFrom so in practice it should not fail as long as only the graph vertices are passed as argument.

[snowleopard]

Yes, I see. This seems like a reasonable trade-off.