I/O

[soniakeys]

marshaling, serialization, to/from popular formats.

This might sit until some application comes along, possibly testing against other libraries and needing to read their test data.

Current thinking though is that these should follow the model of the dot package. They should be separate packages that work by directly iterating over graph representations to generate output. Input (not yet addressed by the dot package) can be done by directly constructing graph objects. Representations of the graph package are transparent enough that this is possible. The graph package should not have to be otherwise cluttered with details of I/O.

[soniakeys]

The literature calls it "ingest." Speed is the issue for larger data sets.

Here's fairly a naive program to read the Dimacs NY city streets data (264k nodes, 734k arcs) into a LabeledAdjacencyList. Runtime on the laptop (Dell Precision M 4700, SSD):

real    8m8.299s
user    12m10.984s
sys 0m2.440s

Terrible.

package main

import (
    "fmt"
    "io/ioutil"
    "log"
    "strconv"
    "strings"

    "github.com/soniakeys/graph"
)

func main() {
    d, err := ioutil.ReadFile("USA-road-d.NY.gr")
    if err != nil {
        log.Fatal(err)
    }
    var g graph.LabeledAdjacencyList
    for ln, line := range strings.Split(string(d), "\n") {
        if ln%1000 == 0 {
            fmt.Println(ln)
        }
        f := strings.Fields(line)
        if len(f) != 4 || f[0] != "a" {
            continue
        }
        n1, err := strconv.Atoi(f[1])
        if err != nil {
            log.Fatal(err)
        }
        n2, err := strconv.Atoi(f[2])
        if err != nil {
            log.Fatal(err)
        }
        d, err := strconv.Atoi(f[3])
        if err != nil {
            log.Fatal(err)
        }
        if n1 > n2 {
            n1, n2 = n2, n1
        }
        if n2 >= len(g) {
            if need := n2 + 1 - cap(g); need > 0 {
                g2 := make(graph.LabeledAdjacencyList, cap(g)+2*need)
                copy(g2, g)
                g = g2
            }
            g = g[:n2+1]
        }
        g[n1] = append(g[n1], graph.Half{graph.NI(n2), graph.LI(d)})
        g[n2] = append(g[n2], graph.Half{graph.NI(n1), graph.LI(d)})
    }
    fmt.Println(len(g), "nodes")
}

[soniakeys]

Probably lots to learn by reading code of polished serialization packages.

[soniakeys]

So what are these "popular" formats anyway?

• Text, with some options: edge list, adjacency list, possibly weighted or with other attribues? possibly with header lines, comment lines, variations of separators. (igraph, networkx, lightGraphs)
• GraphML (igraph, boost, SNAP, graph-tool, networkx, lightGraphs)
• Graphviz dot (igraph, boost, SNAP, gonum, graph-tool)* GML (igraph, SNAP, graph-tool, networkx, lightGraphs)
• Pajek (igraph, SNAP, networkx, lightGraphs)

Interesting:

• Graph6 (networkx, lightGraphs)

Other formats:

• CDF (lightGraphs)

• DIMACS (igraph)

• DynNet (SNAP)

• GEFX (networkx, lightGraphs, gephi)

• GIS Shapefile (networkx)

• GML (gephi, lightGraphs)

• GraphQL (gonum)

• JSON: various, like with the text formats. (networkx)

• Large Graph Layout: http://clairemcwhite.github.io/lgl-guide/ (igraph)

• LEDA (networkx)

• Matlab (SNAP)

• ORA (SNAP)

• TLP (Tulip, gephi)

• UCINET DL (igraph)

• I think SNAP handles many other formats to read specific graphs or to solve specific problems. It would take more study of the docs.

• In addition there are various formats for saving and loading that are specific to a package or language. A new thing should probably be done from scratch. Probably using a fast and or efficient general purpose, well supported serialization, cross-language, cross-platform format.