{"action":"created","issue":{"url":"https://api.github.com/repos/jltsiren/gcsa2/issues/3","labels_url":"https://api.github.com/repos/jltsiren/gcsa2/issues/3/labels{/name}","comments_url":"https://api.github.com/repos/jltsiren/gcsa2/issues/3/comments","events_url":"https://api.github.com/repos/jltsiren/gcsa2/issues/3/events","html_url":"https://github.com/jltsiren/gcsa2/issues/3","id":90724753,"number":3,"title":"Rare issues in edge generation","user":{"login":"jltsiren","id":11444026,"avatar_url":"https://avatars.githubusercontent.com/u/11444026?v=3","gravatar_id":"","url":"https://api.github.com/users/jltsiren","html_url":"https://github.com/jltsiren","followers_url":"https://api.github.com/users/jltsiren/followers","following_url":"https://api.github.com/users/jltsiren/following{/other_user}","gists_url":"https://api.github.com/users/jltsiren/gists{/gist_id}","starred_url":"https://api.github.com/users/jltsiren/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jltsiren/subscriptions","organizations_url":"https://api.github.com/users/jltsiren/orgs","repos_url":"https://api.github.com/users/jltsiren/repos","events_url":"https://api.github.com/users/jltsiren/events{/privacy}","received_events_url":"https://api.github.com/users/jltsiren/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":3,"created_at":"2015-06-24T16:24:49Z","updated_at":"2015-06-25T10:10:46Z","closed_at":null,"body":"Assume that we have the following subgraphs:\r\n\r\n```\r\n1: B[CD]F[GH]J\r\n2: [AB]C[EF]GI\r\n```\r\n\r\nThere are the following paths of length 4:\r\n\r\n```\r\n(1,1): BCFG, BCFH, BDFG, BDFH\r\n(1,2): CFGJ, CFHJ, DFGJ, DFHJ\r\n(2,1): ACEG, ACFG, BCEG, BCFG\r\n(2,2): CEGI, CFGI\r\n```\r\n\r\nIf we start from paths of length 2 and do one step of prefix-doubling, we end up with the following list of paths:\r\n\r\n```\r\n(2,1): ACEG to BCEG\r\n(1,1): BCFG\r\n(2,1): BCFG\r\n(1,1): BCFH to BDFH\r\n(2,2): CEGI to CFGI\r\n(1,2): CFGJ to DFHJ\r\n```\r\n\r\nThe path graph has six nodes and four edges:\r\n\r\n```\r\n[(2,1): ACEG to BCEG] -> [(2,2): CEGI to CFGI] on A, B\r\n[(2,1): BCFG]         -> [(2,2): CEGI to CFGI] on B\r\n[(1,1): BCFG]         -> [(1,2): CFGJ to DFHJ] on B\r\n[(1,1): BCFH to BDFH] -> [(1,2): CFGJ to DFHJ] on B\r\n```\r\n\r\nIf we perform the final merge-by-label step, we end up with five nodes and four edges:\r\n\r\n```\r\n[(2,1): ACEG to BCEG] -> [(2,2): CEGI to CFGI] on A, B\r\n[(1,1), (2,1): BCFG]  -> [(2,2): CEGI to CFGI] on B\r\n[(1,1), (2,1): BCFG]  -> [(1,2): CFGJ to DFHJ] on B\r\n[(1,1): BCFH to BDFH] -> [(1,2): CFGJ to DFHJ] on B\r\n```\r\n\r\nBy doing backward searching in this graph, we could end up at (1,1) with pattern BCE and at (2,1) with pattern BD, which are both wrong.\r\n\r\nThe real issue is that the the merging step in prefix-doubling and the final merge-by-label step are incompatible. In some very rare cases (such as the example above), they will result in an incorrect path graph. The merge-by-label step is less useful, so we are probably going to drop it.\r\n\r\nThe remaining issue is how we can match the destination node of an edge with the correct source node, out of a set of path nodes with identical labels.\r\n"},"comment":{"url":"https://api.github.com/repos/jltsiren/gcsa2/issues/comments/115197919","html_url":"https://github.com/jltsiren/gcsa2/issues/3#issuecomment-115197919","issue_url":"https://api.github.com/repos/jltsiren/gcsa2/issues/3","id":115197919,"user":{"login":"jltsiren","id":11444026,"avatar_url":"https://avatars.githubusercontent.com/u/11444026?v=3","gravatar_id":"","url":"https://api.github.com/users/jltsiren","html_url":"https://github.com/jltsiren","followers_url":"https://api.github.com/users/jltsiren/followers","following_url":"https://api.github.com/users/jltsiren/following{/other_user}","gists_url":"https://api.github.com/users/jltsiren/gists{/gist_id}","starred_url":"https://api.github.com/users/jltsiren/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jltsiren/subscriptions","organizations_url":"https://api.github.com/users/jltsiren/orgs","repos_url":"https://api.github.com/users/jltsiren/repos","events_url":"https://api.github.com/users/jltsiren/events{/privacy}","received_events_url":"https://api.github.com/users/jltsiren/received_events","type":"User","site_admin":false},"created_at":"2015-06-25T10:10:46Z","updated_at":"2015-06-25T10:10:46Z","body":"I think there may be an easier solution than I thought yesterday. Right now the merging step works like in the original GCSA, merging lexicographic ranges of paths, if they all start from the same node. The issue should go away, if the merging is based on a common prefix instead of any lexicographic range. (In the terminology of the GCSA paper, this means switching from prefix-range-sorted automata to prefix-sorted automata.)"}}