{"action":"created","issue":{"url":"https://api.github.com/repos/ipfs/notes/issues/168","repository_url":"https://api.github.com/repos/ipfs/notes","labels_url":"https://api.github.com/repos/ipfs/notes/issues/168/labels{/name}","comments_url":"https://api.github.com/repos/ipfs/notes/issues/168/comments","events_url":"https://api.github.com/repos/ipfs/notes/issues/168/events","html_url":"https://github.com/ipfs/notes/issues/168","id":179010492,"number":168,"title":"Binary encoding of (directed) Bipartite Graphs","user":{"login":"wires","id":315734,"avatar_url":"https://avatars.githubusercontent.com/u/315734?v=3","gravatar_id":"","url":"https://api.github.com/users/wires","html_url":"https://github.com/wires","followers_url":"https://api.github.com/users/wires/followers","following_url":"https://api.github.com/users/wires/following{/other_user}","gists_url":"https://api.github.com/users/wires/gists{/gist_id}","starred_url":"https://api.github.com/users/wires/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wires/subscriptions","organizations_url":"https://api.github.com/users/wires/orgs","repos_url":"https://api.github.com/users/wires/repos","events_url":"https://api.github.com/users/wires/events{/privacy}","received_events_url":"https://api.github.com/users/wires/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2016-09-24T04:42:28Z","updated_at":"2016-09-25T08:23:01Z","closed_at":null,"body":"This note describes an encoding of (finite) [bipartite graphs](https://en.wikipedia.org/wiki/Bipartite_graph).\r\n\r\nhttp://mathworld.wolfram.com/BipartiteGraph.html\r\n\r\n# Motivation\r\n\r\nBi-partite graphs are ubiquitous in mathematics and computer science.\r\n\r\nMatching on a graph is a very natural application (customer ↔ taxi), recommendations, clustering.\r\nLots of cool things.\r\n\r\nAnd, of course, my personal motivation, http://statebox.github.io but more on that later ;^)\r\n\r\n/cc @repatica @epost @whyrusleeping @jbenet @diasdavid \r\n\r\n## Details\r\n\r\nA bi-partite graph is a graph where the nodes can be partitioned in two\r\ndisjoint sets, say `A` and `B`.\r\n\r\nThe edges only run *between* the two sets, so `A=>B` and `B=>A` only, no `B=>B` or `A=>A`. Hence, (directed) bi-partited graphs are often depicted as such:\r\n\r\n<img width=\"185\" alt=\"screen shot 2016-09-24 at 12 30 31\" src=\"https://cloud.githubusercontent.com/assets/315734/18806095/b7e50d5c-8252-11e6-9abf-e53cd37612f4.png\">\r\n\r\nFor clarity and nothing else, I used nrs for one partition and letters for the other.\r\n\r\n## Proposed encoding\r\n\r\nWe now describe the graph by listing the adjacent edges of each node of one partition. So lets focus on the diamons and list them out.\r\n\r\n<img width=\"217\" alt=\"screen shot 2016-09-24 at 12 30 43\" src=\"https://cloud.githubusercontent.com/assets/315734/18806098/c0eb120c-8252-11e6-8d02-b3efc43ee18d.png\">\r\n\r\nNow in the directed case, each node a *pair* of sets of edges, namely the in- and outgoing edges. When we list this out we get (JSON example):\r\n\r\n```js\r\n{ a: [ [1]  , [2] ]\r\n, b: [ [1,2], []  ]\r\n, c: [ []   , [2] ]\r\n}\r\n```\r\n\r\nNow I do not want to name the nodes `a, b, c`, just be able to refer to them...\r\nSo instead we pick some order and infer their identifiers from the position in the array:\r\n\r\n```json\r\n[ [ [1]  , [2] ]\r\n, [ [1,2], []  ]\r\n, [ []   , [2] ]\r\n]\r\n```\r\n\r\n## Result\r\n\r\nWhats now left is:\r\n\r\n> List of lists (pairs) of lists of numbers\r\n\r\nNote that there is an upperbound to these numbers, namely the size of\r\nthe other set. So, you can minize the upper bound by picking the\r\npartition with the most nodes.\r\n\r\nNot only that but we can further simplify.\r\n\r\n- Let the number 0 denote `[`\r\n- Let the number 1 denote `]`\r\n- Counting the nodes starting at 2 (so 0=>2, 1=>3, ...).\r\n\r\nOur example now becomes (indented for clarity):\r\n\r\n```\r\n0\r\n 0 0 2 1\r\n   0 3 1 1\r\n 0 0 2 3 1\r\n   0 1 1\r\n 0 0 1\r\n   0 3 1 1\r\n1\r\n```\r\n\r\nThus we are left with\r\n\r\n> List of numbers smaller than some upper bound.\r\n\r\nThis naturally leads to encoding as a list of `varints`, see [protcol buffers](https://developers.google.com/protocol-buffers/docs/encoding#varints) for more information. Compression algorithms should work really well on this.\r\n\r\nWe now have a compact binary encoding of bipartite graphs and a natural decoding into JSON.\r\n\r\n## Further notes:\r\n\r\n- Why not `n`-partite? Well 1) the edge set becomes more involved when n goes up and 2) they are used less often.\r\n\r\n- What about undirected? Well, in that case you can leave out the *pair* altogether and stick to `[[n]]`. The parser can detect this by looking at how deep the lists are nested.\r\n\r\n- How to add data to this? Well, you can just we use a labeling\r\n  function, along the lines of\r\n\r\n```js\r\n{ labels: { vertices: { A: { 0: { someProp: 'someValue' },\r\n                             1: { someProp: 'someOtherValue' } }\r\n                      , B: { 0: { someOtherProp: 3.1415927 } } }\r\n          , edges: { AB: {} , BA: {} }\r\n          }\r\n}\r\n```\r\n\r\nOpinions?!\r\n"},"comment":{"url":"https://api.github.com/repos/ipfs/notes/issues/comments/249409412","html_url":"https://github.com/ipfs/notes/issues/168#issuecomment-249409412","issue_url":"https://api.github.com/repos/ipfs/notes/issues/168","id":249409412,"user":{"login":"whyrusleeping","id":1243164,"avatar_url":"https://avatars.githubusercontent.com/u/1243164?v=3","gravatar_id":"","url":"https://api.github.com/users/whyrusleeping","html_url":"https://github.com/whyrusleeping","followers_url":"https://api.github.com/users/whyrusleeping/followers","following_url":"https://api.github.com/users/whyrusleeping/following{/other_user}","gists_url":"https://api.github.com/users/whyrusleeping/gists{/gist_id}","starred_url":"https://api.github.com/users/whyrusleeping/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/whyrusleeping/subscriptions","organizations_url":"https://api.github.com/users/whyrusleeping/orgs","repos_url":"https://api.github.com/users/whyrusleeping/repos","events_url":"https://api.github.com/users/whyrusleeping/events{/privacy}","received_events_url":"https://api.github.com/users/whyrusleeping/received_events","type":"User","site_admin":false},"created_at":"2016-09-25T08:23:00Z","updated_at":"2016-09-25T08:23:00Z","body":"I'll read through and respond properly to this later, but for now: cc @nicola @BrendanBenshoof"}}
{"actor":{"display_login":"whyrusleeping"}}