HashSet, Graph, Cognac

The post on applying GPU to finding Eulerian path mentioned a stumbling block: partitioning a very specific kind of graph. In general, partitioning is a hard problem, NP-hard actually. The graphs we are dealing with are very specific, though, and may be partitioned in $latex O(|E|)$ time (E - the set of graph edges). Our … Continue reading HashSet, Graph, Cognac →

Walking the Euler Path: PIN Cracking and DNA Sequencing

Continuing on to some cool applications of Eulerian paths. Intro Visualization GPU/CUDA Injection The goal of this little graph experiment remains exploration of accelerating Eulerian path finding on the GPU. This is the final introductory post. Eulerian Path Hierholzer algorithm works great. It's linear in the number of edges, so as fast as we can … Continue reading Walking the Euler Path: PIN Cracking and DNA Sequencing →

Visualizing Graphs

Previously Walking the Eule Path: Intro Generating and Visualizing Graphs I can hardly overemphasize the importance of visusalizations. Many a bug had been immediately spotted just by looking at a visual of a complex data structure. I therefore decided to add visuals to the project as soon as the DirectedGraph class was born. Code & … Continue reading Visualizing Graphs →

Walking the Euler Path: Intro

Source Code I'm thinking about a few posts in these series going very fast through the project. The source is on my GitHub, check out the tags since the master branch is still work in progress. Experimenting with Graph Algorithms with F# and GPU Graphs play their role in bioinformatics which is my favorite area … Continue reading Walking the Euler Path: Intro →