graph: graph serialisation

[kortschak]

It would be good to have some standard graph serialisation capacity.

Which would we like to support?

Probably DOT at the very least, but I think at least one of the richer markup languages, probably GraphML since it seems to have the widest compatibility range, though GEXF would probably be nice as well.

In the first instance marshaling support would be the goal, later to add unmarshaling.

[UserAB1236872]

I'll defer to you on this, I haven't done much in the way of graph
serialization (though I know how to read a spec so I can assist in
implementing it).

On Thu, Apr 3, 2014 at 5:49 PM, kortschak notifications@github.com wrote:

It would be good to have some standard graph serialisation capacity.

Which would we like to support?

Probably DOT http://www.graphviz.org/content/dot-language at the very
least, but I think at least one of the richer markup languages, probably
GraphML http://graphml.graphdrawing.org/ since it seems to have the
widest compatibility range, though GEXF http://gexf.net/format/ would
probably be nice as well.

In the first instance marshaling support would be the goal, later to add
unmarshaling.

Reply to this email directly or view it on GitHubhttps://github.com/gonum/graph/issues/9
.

[kortschak]

I'm happy to vote on a priority list, but I think we need others' input too:

1. DOT (can be readily used for debugging)
2. GraphML (seems to be the most generally used format)
3. GEXF (Has handling for graph dynamics - node/edge life times - which can be important in biology and probably other areas)

[soniakeys]

DOT seems like a good first step.

[kortschak]

Which parts of DOT? Do we want to handle subgraphs? There is not conception of them explicitly in graph although you can implement them. Also, non-numeric node IDs are tricky for parsing - we could make use of the encoding.TextEncoder and TextDecoder interfaces here. The first step is to come up with a reasonable set of interfaces that would be required to cover DOT (and would hopefully cover other formats).

[mewmew]

... though GEXF would probably be nice as well.

The GEXF link in the first comments is broken. Should be updated to https://gephi.org/gexf/format/

[mewmew]

I would like to initiate a discussion on how we may introduce decode functionality for DOT graphs; i.e.

Read and parse DOT files into gonum/graph.Graph representations.

While playing with this in the graphism/dot project I've come across a couple of issues that I would like to hear if we can figure out a clean solution to together.

The primary issue is related to #87, the sometimes subtle representation of nodes within graphs, and specifically the creation of user specified node structures from a decoding library.

As the Builder interface only exposes a NewNodeID method, the decoding library cannot create user defined nodes for the client, but has to resort to pre-defined node representation.

Imagine a users has defined a graph, a node, and an edge type Graph, Node and Edge, respectively, in package p, and wants to decode a DOT file into this graph representation. Since the decoding library is unaware of the existance of package p, and rightly should be, we may wish to introduce some sort of a interface for decoding graphs which introduces methods such as NewNode (to be used instead of NewNodeID) and NewEdge. This would allow a decoding library to generate graphs with user defined structures for nodes and edges. Furthermore, we may look into introducing methods for decoding DOT attributes, which may be propagated to the user-defined node and edge types. For instance:

with inspiration from encoding/xml.

package p

type Node struct {}
func (n *Node) UnmarshalDOTAttr(attr Attr) error {}
type Edge struct {}
func (e *Edge) UnmarshalDOTAttr(attr Attr) error {}

What are your thoughts on this? I hope we may end up with a design that makes it possible to hook into existing graph and node definitions, without having to extensively rewrite them.

Would also like to think about the potential downsides to the UnmarshalDOTAttr example give above. Perhaps we may find a way to propagate additional DOT attributes after decoding, and allow the decoder to only focus on the most essential aspects of the graphs, such as nodes and edges between them.

[mewmew]

Initial support for decoding DOT files into graphs with user-defined types for nodes and edges has been implemented in graphism/dot.

The following interface is currently being used:

// DirectedBuilder is a directed graph builder capable of handling user-defined
// node and edge types.
type DirectedBuilder interface {
	graph.DirectedBuilder
	// NewNode returns a new node with a unique node ID in the graph.
	NewNode() graph.Node
	// NewEdge returns a new edge from the source to the destination node in the
	// graph, or the existing edge if already present.
	NewEdge(from, to graph.Node) graph.Edge
}

// UnmarshalerAttr is the interface implemented by objects that can unmarshal a
// DOT attribute description of themselves.
type UnmarshalerAttr interface {
	// UnmarshalDOTAttr decodes a single DOT attribute.
	UnmarshalDOTAttr(attr *ast.Attr) error
}

Any thoughts or suggestions would be warmly appreciated. The parser is now capable of doing round-trips between gonum/graph.Graph representations and DOT files, including DOT attributes for nodes and edges.

(Note, the graphism/dot package is only supporting directed graphs during the proof of concept stage of development. Support for undirected graphs will be added once we settle on a good design.)

An example implementation of a user-defined graph which may be used for DOT decoding using the new interface may be found at:

• Graph type definition: https://github.com/decomp/decomp/blob/dev/graph/cfg/cfg.go
• Decoding support: https://github.com/decomp/decomp/blob/dev/graph/cfg/decode.go
• Encoding support: https://github.com/decomp/decomp/blob/dev/graph/cfg/encode.go

[kortschak]

That design sounds good to me.

[mewmew]

That design sounds good to me.

Glad to hear!

I'll start preparing a pull request for adding decoding support of DOT files to gonum/graph/encoding/dot. I'll try my hardest to minimize the public API, and follow the interface outlined above.

Should hope to have it ready within the next few days.

Cheers /u