Location and access for metadata

[gdalle]

Should it be in the vertex / edge object itself?
What is the right syntax to access it? Can it be linked with the edge weight?

[gdalle]

Related:

• Common interface for graphs with metadata Graphs.jl#35
• Proposals for Graphs.jl 2.0 from the perspective of MultilayerGraphs.jl Graphs.jl#165

[mtfishman]

I would vote for separating the metadata from the edges, and think of the edges as indices for accessing the metadata (and indicating where there is nontrivial/nonzero metadata).

Say we have a metagraph wrapping a simple graph like:

struct MetaGraph{T<:Integer,D} <: AbstractGraph{T,SimpleEdge{T}}
  graph::SimpleGraph{T}
  edge_data::MyComplicatedEdgeDataStorage{SimpleEdge{T},D}
end

It could require some non-trivial calculation to access edge data from the edge_data structure. In the interface proposed in #13 the edges would be defined like this (if I understand correctly):

struct DataEdge{T<:Integer,D} <: AbstractEdge{T,D}
    src::T
    dst::T
    data::D
end

function GraphsBase.out_edges(g::MetaGraph{T}, u) where {T}
    return DataEdge{T}(u, v, get_data(g.edge_data, SimpleEdge(u, v)) for v in out_neighbors(g, u))
end

This seems like a lot of unnecessary work to do each time you ask for the edges.

Also, it seems like another disadvantage is that there would be many edge types which different graphs would have to understand. If I had both a MetaGraph g defined above and also its parent SimpleGraph g.graph, it seems like they should have the same out_edges (say so I could pass edges accessed from the MetaGraph and have those easily used by the SimpleGraph). I know some of that could be handled by generic code and conversions, but it seems better in practice to have fewer "simple" edge types.

As for the weights, I think they can be thought of as just a special kind of metadata, which again I don't think should be stored with the edges, but instead accessed from the graph using an edge in some generic way (weight(g::AbstractGraph, e)). I think that allows a lot more flexibility in how the weight function can be customized, i.e. it could be customized through overloading on a graph type or even an instance of a graph by storing a weight function with the graph, as opposed to just overloading it based on the type of the edge (which seems to lead to an awkward situation that you need to define a new edge type to define a new weight function).

[CameronBieganek]

Here's my preferred interface for metadata.

First the user defines their own vertex and edge metadata types. These could be any objects with getproperty and setproperty! methods, but typically they would be struct, mutable struct, or named tuple.

mutable struct VertexData
    a::Int
    b::String
end

mutable struct EdgeData
    c::Float64
    d::String
end

Then the user can create a graph that uses those metadata types. Suppose we use Char for the vertex type. Then creating an empty graph would look like this:

g = Graph{Char, VertexData, EdgeData}()

After adding vertices, edges, and metadata, the metadata can be accessed as follows:

# Access vertex metadata:
g[u].a

# Access edge metadata:
g[e].c
g[u, v].d

And, if the underlying metadata types are mutable, then the metadata can also be set with the following syntax:

# Set vertex metadata:
g[u].a = 42

# Set edge metadata:
g[e].c = 3.14
g[u, v].d = "hello"

[mtfishman]

@CameronBieganek agreed, that is very similar to the design of DataGraphs.jl, based on a getindex and setindex! interface for accessing and modifying metadata.

One unfortunate thing with committing to g[u, v] as the syntax for accessing edge metadata is that it precludes nice syntax for cartesian indexing of vertices (if the vertices are some kind of cartesian index), similar to the Dict syntax:

julia> Dict((1, 2) => "x", (2, 1) => "y")[1, 2]
"x"

But that leaves open the question of how to access edge metadata, in DataGraphs I went with g[Edge(u, v)] or g[u => v] but I could see arguments against those, since it leaves ambiguity if vertices themselves happen to be Edge or Pair types (we just disallow that, but that might not be a great design for a general graph type). One design could be to have a universal edge indexing type g[EdgeIndex(u, v)] which would be disallowed as a vertex type or just having a function get_edge_data(g, u, v) but I could see arguments against both of those choices. Another option is that in the case of ambiguity, say if a vertex is a Pair or Edge, one has to access vertex data with Vertex indexing type g[Vertex(u => v)] or g[Vertex(Edge(u, v))]. Again I think that may not be ideal since then that could force people to need to use Vertex all over the place to make graph code generic to any graph types.

I think metadata can mostly be orthogonalized from the basic design and interface (though of course should be anticipated), since most graph algorithms don't require (or just ignore) metadata. The primary examples where metadata is needed that I came across is in operations where graphs are being merged so then you need to know how to merge metadata, but that would need some specialized functionality for different metagraph types anyway since you can't really anticipate how metadata will be stored (similar to how you can't really assume much about the storage structure of AbstractMatrix, though there could be a fallback standard metadata type comparable to Dict or Matrix in Base Julia). I think that could be solved by following the example of Julia Base AbstractArrays by just minimally requiring access to metadata through getindex, and then making use of generic concepts like similar and empty for making new metagraph structures.

[mtfishman]

I don't really see a particular need for requiring getproperty and setproperty! for metadata, I don't see why from the design of a generic graph interface you need to assume anything about what the metadata will be, just that you can access it and set it in the case of mutable metagraphs.

Regarding the issue around getindex/setindex! syntax, it may be better from an abstract type interface perspective (though not from an external interface perspective) to define lower level interface functions (EDIT: Simplified to just getdata, similar to the proposal in https://discourse.julialang.org/t/rfc-graphinterface-jl-an-interface-proposal-for-graphs-jl-version-2-0/104518/14 by @gdalle):

getdata(g, v) # Get vertex data
getdata(g, u, v) # Get edge data
setdata!(g, v, value) # Set vertex data if mutable
setdata!(g, u, v, value) # Set edge data if mutable

and let particular graph subtypes decide how getindex and setindex! act. There could be default fallbacks from getindex to getdata, which could then be overloaded if a graph instance wants getindex to mean something else or have slightly different syntax (analogous to getproperty and getfield in Base Julia).

[CameronBieganek]

I went with g[Edge(u, v)] or g[u => v] but I could see arguments against those, since it leaves ambiguity if vertices themselves happen to be Edge or Pair types

That's a very good point. I thought about that a while ago, and then I forgot about it. 😅

I don't really see a particular need for requiring getproperty and setproperty! for metadata, I don't see why from the design of a generic graph interface you need to assume anything about what the metadata will be, just that you can access it and set it in the case of mutable metagraphs.

You're right, the user should be able to use whatever object they want to store their metadata, including Dict, etc.

Here's a modified proposal:

• vertex_data(g) and edge_data(g) (or some other spelling) return indexable objects that allow access to metadata.

Here's a demonstration of what it would look like in practice:

# User defined metadata types. User can use any type of object.
mutable struct VertexData
    a::Int
    b::String
end

mutable struct EdgeData
    c::Float64
    d::String
end

# ... (Create graph here.)

vd = vertex_data(g)
ed = edge_data(g)

vd['x'] = VertexData(1, "hello")
vd['y'] = VertexData(2, "world")
vd['x'].a = 100
vd['y'].b = "foo"

vd['x'].a  # 100
vd['x'].b  # "hello"

ed['x', 'y'] = EdgeData(1.2, "asdf")
ed[Edge('x', 'y')].d = "qwer"

ed['x', 'y'].c  # 1.2
ed['x', 'y'].d  # "qwer"

I just wish there was a more compact way to write it than vertex_data. If we shorten the function names to vdata and edata, then this doesn't look too bad:

vdata(g)['x'].a = 123

If one uses a dictionary to store their metadata instead of a struct or named tuple, that statement would look something like this:

vdata(g)['x'][:a] = 123

There are some oddball ways that we could do it, but they might be a little too odd:

g[]  # Returns an object that can be indexed to obtain vertex metadata.
g()  # Returns an object that can be indexed to obtain edge metadata.

# Examples:
g[]['x'].a = 123
g()['x', 'y'].a = 3.14

or this:

g(:vertex)  # Returns an object that can be indexed to obtain vertex metadata.
g(:edge)    # Returns an object that can be indexed to obtain edge metadata.

# Examples:
g(:vertex)['x'].a = 123
g(:edge)['x', 'y'].a = 3.14

I considered g['x'] and g('x', 'y') for vertex and edge metadata, respectively, but then you can't assign a whole new object as the metadata for a given edge.

[mtfishman]

That's close to the design I have in DataGraphs.jl, where the minimal requirement of the interface for accessing metadata is that a type implements vertex_data(g) and edge_data(g) which output dictionaries (or some other data structure, at least in principle) that can be indexed into with vertices and edges, so then getdata and setdata! can be defined through vertex_data(g) and edge_data(g):

getdata(g, v) = vertex_data(g)[v] # Get vertex data
getdata(g, u, v) = edge_data(g)[Edge(u, v)] # Get edge data
setdata!(g, v, value) = (vertex_data(g)[v] = value) # Set vertex data if mutable
setdata!(g, u, v, value) = (edge_data(g)[Edge(u, v)] = value) # Set edge data if mutable

I just use getindex and setindex! in DataGraphs.jl but I think it is too opinionated for a general graph interface for those to be part of the interface requirement and we should allow AbstractGraph subtypes to decide the meaning of getindex and setindex!.

In general, it may not be practical or efficient to implement vertex_data(g) and edge_data(g) for a given graph, since the vertex data and edge data may be tangled up in some complicated data structure, in which case getdata and setdata! could be overloaded (which means that code in Graphs.jl should only make use of getdata and setdata!).

One reason to lean towards just making getdata and setdata! the required interface is that it is easier to encode sparsity into the data structures. For example, in general undirected graphs will have symmetry between the data on the same edge in opposite directions. Often getdata(g, u, v) == getdata(g, v, u), however I have examples where getdata(g, u, v) == f(getdata(g, v, u)). Maybe one could argue that you should use a directed graph at that point, but the underlying graph is undirected for all purposes related to how it should be treated in graph algorithms, it's only the data that has some sense of directionality. Additionally, there may be other symmetry such that getdata(f, u, v) == getdata(f, w, x) which isn't easy to encode in a single data structure.

Of course you could have vertex_data(g) and edge_data(g) output a data structure which then encode these symmetries or relationships between elements through getindex and setindex!, but it seems unfortunate to require users to define data structures (which could get kind of complicated) as opposed to just defining function overloads of getdata and setdata!.

[CameronBieganek]

Of course you could have vertex_data(g) and edge_data(g) output a data structure which then encode these symmetries or relationships between elements through getindex and setindex!, but it seems unfortunate to require users to define data structures (which could get kind of complicated) as opposed to just defining function overloads of getdata and setdata!.

To clarify, by "users" do you mean implementers of new graph types, or users of existing graph types? Users of existing graph types shouldn't be overloading anything. And implementers of new graph types can, as you said, do anything they want with getindex(edge_data(g), ...) and set_index!(edge_data(g), ...). I think it's ok to have higher expectations of graph implementers than we do of graph users.

[mtfishman]

Yes, I meant implementers of new graph types. I was just arguing that getdata(g, ...) and setdata!(g, ...) may be simpler overloading interfaces than getindex(edge_data(g), ...) and setindex!(edge_data(g), ...) in practice, especially for more complicated graph types where it's not so straightforward to extract edge_data and vertex_data objects, since then new graph types have the burden of two nontrivial overloads: both edge_data/vertex_data and getindex defined for whatever type those output, instead of just one, getdata.

[CameronBieganek]

Of course it's partly a matter of taste. I prefer the square bracket syntax sugar for getting and setting values, rather than a function like setdata!(g, u, v, value).

especially for more complicated graph types where it's not so straightforward to extract edge_data and vertex_data objects, since then new graph types have the burden of two nontrivial overloads: both edge_data/vertex_data and getindex

I would imagine most graph implementers would use the following pattern:

struct VertexData{V}
    g::Graph{V}
end

struct EdgeData{V}
    g::Graph{V}
end

vertex_data(g::Graph) = VertexData(g)
edge_data(g::Graph) = EdgeData(g)

# Define getindex and setindex! overloads for VertexData and EdgeData.

So, vertex_data and edge_data just return wrappers around the graph to facilitate indexing.

Now, if we want to support multigraphs, then getdata would need the following methods:

getdata(g::AbstractGraph, v)
getdata(g::AbstractGraph, u, v)
getdata(g::AbstractGraph, e::AbstractEdge)

But as you pointed out above, this is flawed, because the generic graph interface allows for graphs where the vertex type is a subtype of AbstractEdge. So, you would need separately named functions, like this:

get_vertex_data(g, v)
set_vertex_data!(g, v, value)
get_edge_data(g, u, v)
get_edge_data(g, e)
set_edge_data!(g, u, v, value)
set_edge_data!(g, e, value)

But that starts to get a bit unwieldy.

[mtfishman]

I would just disallow getdata(g::AbstractGraph, e::AbstractEdge) (EDIT: By disallow, I mean define it as accessing vertex data, treating e as a vertex) to avoid ambiguity in the interface function, graph implementers can overload getindex however they want to including indexing with AbstractEdge to access edge data.