Skip to content

Simple (directed) graph library. NOTE: This library is building for gatk...

License

Notifications You must be signed in to change notification settings

githublet/graph

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

graph

Simple (directed) graph library. NOTE: This library is building for gatk...

满足图论中点巡点,增加点,减少点,为GATK设计的,因为GATK是java代码,效率太低,所以用纯C重新编写了,可以用来做一些数据结构,代码无坑!

那就简单描述下吧:首先点的id是从0递增的,所以设定了一个mod取余操作,作为一个点的hash值;

有了hash表,查找点的时间复杂度O(1);删除点时会删除所有与这个点有关系的出边和入边,时间复杂度也从原来的O(点总数) 降低到 2倍点(边总数);

设计hasCycle函数时,第一次设计思想是每一个点递归到底,撞库则环,发现太耗时了,还出现了死循环; 第二次设计加了栈,规避了死循环,加了is_visit,时间还是很多; 第三次设计加了is_exclude,时间复杂度完美了,最多O(点总数);

开源是因为这个也是从GitHub上取到的代码,不过改的比较多,基本上重新设计了一遍。

About

Simple (directed) graph library. NOTE: This library is building for gatk...

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published