Questions about the .gt format

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Questions about the .gt format

ddka
Hello,

I'm in need of an efficient network format for frontend code, and I figured
that since you already have one I shouldn't reinvent the wheel. I'm
currently trying to implement it with Node + Typescript. I'm reading the
docs page for the format carefully, but I'm stuck at a point. I'm not used
to working at the level of bytes so if this is a waste of time, I'm sorry.

I'm using the "7th graders" graph from ns as an example. Everything is
working fine up to the number of nodes:

```
    {
      magicString: '⛾ gt',
      version: 1,
      bigEndian: false,
      stringLength: 216,
      commentString: 'graph-tool binary file (http:://graph-tool.skewed.de)
generated by version 2.34dev (commit 1f792136, Thu Jul 2 23:05:34 2020
+0200) stats: 29 vertices, 740 edges, directed, 6 graph props, 2 vertex
props, 2 edge props',
      directed: true,
      numNodes: 29,
      usedBytesForNodeIndex: 1
    }
```

But, for grabbing the neighbors for every node I'm stuck. I can read the
number of neighbors for the first node properly: 22. But, this is giving
nonsense when I read it as LE, but it's working as BE, even though
Big-Endian byte in the beginning was 0? That's my first source of confusion.

Next, after reading that 64bit int I move the offset forward by 8 and start
reading the neighbors (each consuming 1 byte because numNodes = 29 < 64?). I
get: "[0,  0,  0,  0,  0,  0,  0,  5,  7, 10, 11, 13, 15, 16, 18, 20, 21,
25, 26,  7, 10, 11]". Clearly I'm messing something up here. It's misaligned
by 7 bytes. If I move the offset forward by 7 I get the proper "[5, 7, 10,
11, 13, 15, 16, 18, 20, 21, 25, 26,  7, 10, 11,  1,  4,  5, 10, 11, 13,
15]". And, the number of nodes I read for the second vertex is garbage.

I'm doing something wrong at this point. Sorry if this is obvious and I'm
wasting time. Any idea what I'm missing here?

Thanks for any help!



--
Sent from: https://nabble.skewed.de/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Questions about the .gt format

Tiago Peixoto
Administrator
Am 15.10.20 um 23:04 schrieb ddka:

> Hello,
>
> I'm in need of an efficient network format for frontend code, and I figured
> that since you already have one I shouldn't reinvent the wheel. I'm
> currently trying to implement it with Node + Typescript. I'm reading the
> docs page for the format carefully, but I'm stuck at a point. I'm not used
> to working at the level of bytes so if this is a waste of time, I'm sorry.
>
> I'm using the "7th graders" graph from ns as an example. Everything is
> working fine up to the number of nodes:
>
> ```
>     {
>       magicString: '⛾ gt',
>       version: 1,
>       bigEndian: false,
>       stringLength: 216,
>       commentString: 'graph-tool binary file (http:://graph-tool.skewed.de)
> generated by version 2.34dev (commit 1f792136, Thu Jul 2 23:05:34 2020
> +0200) stats: 29 vertices, 740 edges, directed, 6 graph props, 2 vertex
> props, 2 edge props',
>       directed: true,
>       numNodes: 29,
>       usedBytesForNodeIndex: 1
>     }
> ```
>
> But, for grabbing the neighbors for every node I'm stuck. I can read the
> number of neighbors for the first node properly: 22. But, this is giving
> nonsense when I read it as LE, but it's working as BE, even though
> Big-Endian byte in the beginning was 0? That's my first source of confusion.
>
> Next, after reading that 64bit int I move the offset forward by 8 and start
> reading the neighbors (each consuming 1 byte because numNodes = 29 < 64?). I
> get: "[0,  0,  0,  0,  0,  0,  0,  5,  7, 10, 11, 13, 15, 16, 18, 20, 21,
> 25, 26,  7, 10, 11]". Clearly I'm messing something up here. It's misaligned
> by 7 bytes. If I move the offset forward by 7 I get the proper "[5, 7, 10,
> 11, 13, 15, 16, 18, 20, 21, 25, 26,  7, 10, 11,  1,  4,  5, 10, 11, 13,
> 15]". And, the number of nodes I read for the second vertex is garbage.
>
> I'm doing something wrong at this point. Sorry if this is obvious and I'm
> wasting time. Any idea what I'm missing here?
If you are trying to implement a gt reader, and you are running into
problems parsing an existing file, you need to provide an actual minimal
working example that yields the problem you are having. Just describing
in words what you are trying to do is a complete non-starter.

A side observation: If you are implementing a gt reader in Javascript,
it is not very likely that you will get much speed improvement over
graphml/gml. Significant improvements will only be seen if implementing
in C/C++.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: Questions about the .gt format

ddka
Live example here
https://codesandbox.io/s/gt-javascript-nn7k8?file=/src/gt.js Codesandbox
seems a bit flaky, but it appears to be working

For speed: I'm mostly thinking about the file compression, not the parse
speed. But, anyway, I could use WASM in the end and I'm sure it will be much
better than existing JS + GraphML solutions

Thanks for quick response



--
Sent from: https://nabble.skewed.de/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Questions about the .gt format

Tiago Peixoto
Administrator
Am 16.10.20 um 20:54 schrieb ddka:
> Live example here
> https://codesandbox.io/s/gt-javascript-nn7k8?file=/src/gt.js Codesandbox
> seems a bit flaky, but it appears to be working

Your offset change is wrong at line 35. You have to increment 8 bytes,
not 1, after reading a 64-bit integer.

See why it's important to share the actual code?

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: Questions about the .gt format

ddka
Indeed. I was afraid it would be something silly. The off-by-7 thing should
have tipped me off.

Thanks!



--
Sent from: https://nabble.skewed.de/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool