Before talking about the acyclic graph, first let me give some fundamental information for graphs. Graphs are the basis subject of study by “Graph Theory”. A “graph” is also a data structure which is studied in discrete mathematics and actively used in informatics. By its essence, it represents related pairwise objects. The objects are called vertices (a.k.a. points or nodes) and the connection between two vertices is called an edge (a.k.a arc or line). On Figure 1, the circles are vertices and the connecting lines are edges. A graph is represented by G = (V,E), where V is a set of vertices and E is a set of edges.
Figure 1. – A tree
Acyclic Graph
An acyclic graph is a graph without cycles in it. This means that if you start from any node and go through its edges you will never visit the same node again. Acyclic graphs are bipartite graphs. They can be “connected”, also known as “trees” (Figure 1). In this case, there is a path between any two nodes in the graph. If there are one or more “disconnected branches” of the acyclic graph, it is called a “forest” (Figure 2). This means that there will be nodes that have no available path between them. By removing a number of edges that participate in graph loops or cycles you can turn an cyclic to acyclic graph. Avoiding loops is important in data-flow programming languages to avoid infinite cycles.
Figure 2. – A forest
There are two groups of acyclic graphs, based on the type of their edges. The first group is when the edges have no orientation. This means that edge E(a,b) is identical to edge E(b,a) and the graph is classified as undirected graph. Directed graph on the other hand is represented by G = (V,A), where V is a set of vertices and A is a set of ordered pairs a.k.a. directed edges or arrows.
Acyclic graphs application
Acyclic graphs have big number of applications. With such graphs, you can represent files and folder structures, decision trees for classification problems, parallel tasks of processes in CPUs, genealogy and version history, etc. They are also the primary data structures in different expert systems. Additionally many systems which are based on machine learning algorithms use different types of graphs.
Graphs programming libraries
Finally here are some developers libraries with acyclic graphs implementation:
- http://js.cytoscape.org/ – Graph theory / network library for analysis and visualization, compatible with JS, Node.js, jQuery
- https://github.com/mgraffg/EvoDAG – A Python library
- https://github.com/Sciss/Topology – Scala programming language library that provides data structures and algorithms for graphs