Skip to content
This repository has been archived by the owner on Mar 20, 2020. It is now read-only.

DAGify of graphs to convert paths into slices #13

Open
6br opened this issue Jul 10, 2019 · 1 comment
Open

DAGify of graphs to convert paths into slices #13

6br opened this issue Jul 10, 2019 · 1 comment
Assignees

Comments

@6br
Copy link
Contributor

6br commented Jul 10, 2019

DAGify is the first step to convert paths into slices for graphs that we cannot assume that the graphs are already directed acyclic graph.

@6br 6br self-assigned this Jul 11, 2019
6br pushed a commit that referenced this issue Jul 17, 2019
6br pushed a commit that referenced this issue Jul 18, 2019
6br pushed a commit that referenced this issue Jul 18, 2019
6br pushed a commit that referenced this issue Jul 18, 2019
6br pushed a commit that referenced this issue Jul 18, 2019
6br pushed a commit that referenced this issue Jul 18, 2019
6br pushed a commit that referenced this issue Jul 18, 2019
6br pushed a commit that referenced this issue Jul 18, 2019
6br pushed a commit that referenced this issue Jul 18, 2019
6br pushed a commit that referenced this issue Jul 19, 2019
6br pushed a commit that referenced this issue Jul 19, 2019
@6br
Copy link
Contributor Author

6br commented Jul 19, 2019

There are procedures in visualizing graphs:

  1. Retrieve a subgraph from the whole graph by tracing the nodes from the initial node. (I have not implemented yet because I think it is enough to use vg chunk command in MVP, but we need to implement the algorithm in future, whose algorithm is as written by Josiah.)
  2. DAGify nodes to determine the order of nodes from the input. First, select the first path as a reference path, and then other paths are compared to the reference path iteratively to capture the node that shared in multiple paths using a longest common substrings DP. Each node between those common nodes should belong to the same slice. -> This is implemented in #4: Add DAGify method for linearizing the order of nodes #9.
  3. Align the order of paths (For example, path(x,y,z) might be displayed as [y,x,z] by comparing the relevancy of paths), but it has not implemented yet. To compare the relevancy of paths, create a big bloom filter to store the hash(node_id). The hamming distance of bloom filter may be an estimated distance between paths. Considering the similarity distance, we can build "guide-tree" from the similarity ratio to determine how to cluster these paths.

6br pushed a commit that referenced this issue Jul 21, 2019
6br pushed a commit that referenced this issue Jul 21, 2019
6br pushed a commit that referenced this issue Aug 15, 2019
6br pushed a commit that referenced this issue Aug 15, 2019
josiahseaman added a commit that referenced this issue Aug 20, 2019
… backward_paths. Add Slice stub for the transition. Currently skipping DAGify tests.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant