Copyright | (c) Eben Kadile 2018 |
---|---|

License | BSD 3 Clause |

Maintainer | eben.cowley42@gmail.com |

Stability | experimental |

Safe Haskell | None |

Language | Haskell2010 |

This module allows one to do computations involving directed graphs. Namely, it allows you to convert a directed graph (presented in a generic way) into a simplicial complex and provides functions for constructing the "directed clique complex," see below.

This module uses algorithms for admissible Hasse diagrams. A Hasse diagram is admissible if it is stratified and oriented. A diagram is stratified if all the vertices can be arranged in rows such that all the sources of each vertex are in the next highest row and all the targets are in the next lowest row. A diagram is oriented if every vertex has a linear ordering on its targets.

A node in the diagram is represented as a tuple: the indices of the level 0 nodes in the diagram that are reachable from this node, the indices of targets in the next lowest level, and the indices of the sources in the next highest level. The entire diagram is simply an array of arrays representing each particular level; index 0 represents level 0, etc.

Any directed graph can be encoded as an admissible Hasse diagram with 2 levels. The edges are level 1 and the vertices are level 0. The ordering on the targets of a node representing an edge is simply the terminal vertex first and the initial vertex second. This may be counterintuitive, but its helpful to interpret an arrow between two vertices as the "<" operator. This induces a linear ordering on the vertices of any acyclic complete subgraph - which is what the nodes in the Hasse diagram of the directed clique complex represent.

Any oriented simplicial complex can also be encoded as an admissible Hasse diagram. A node is a simplex, the targets are the faces of the simplex, and the sources are simplices of which the given simplex is a face.

The main feature of this module is an algorithm which takes the Hasse diagram of a directed graph and generates the Hasse diagram of the directed flag complex - the simplicial complex whose simplices are acyclic complete subgraphs of the given graph. Here acyclic refers to a directed graph without any sequence of arrows whose heads and tails match up and which has the same start and end vertex.

The idea is that, if your directed graph represents any kind of information flow, "sub-modules" in the network are groups of nodes that simply take input, process it, and then output it without spinning the information around at all. These "sub-modules" are the directed cliques/flags which I've been referring to as acyclic complete subgraphs up to this point. Constructing a simplicial complex out of them will allow you to both simplify the 1-dimensional topology of the network and possibly detect higher-dimensional topological features.

The algorithm for constructing the directed clique complex comes from this paper by Markram et al: https://www.frontiersin.org/articles/10.3389/fncom.2017.00048/full.

## Synopsis

- type Node = (Vector Int, Vector Int, Vector Int)
- type HasseDiagram = Vector (Vector Node)
- hsd2String :: HasseDiagram -> String
- dGraph2sc :: Int -> [(Int, Int)] -> SimplicialComplex
- encodeDirectedGraph :: Int -> [(Int, Int)] -> HasseDiagram
- directedFlagComplex :: HasseDiagram -> HasseDiagram
- hDiagram2sc :: HasseDiagram -> SimplicialComplex

# Documentation

type Node = (Vector Int, Vector Int, Vector Int) Source #

Type representing a node in a Hasse diagram. Hasse diagrams are being used to represent simplicial complexes so each node represents a simplex. Contents of the tuple in order: Vector of references to vertices of the underlying directed graph, vector of references to the simplices faes in the next lowest level of the Hasse diagram, vector of references to "parent" simplices (simplices who have this simplex as a face) in the next highest level of the Hasse diagram.

type HasseDiagram = Vector (Vector Node) Source #

Type representing an admissible Hasse diagram. Each entry in the vector represents a level in the Hasse diagram.

hsd2String :: HasseDiagram -> String Source #

Simple printing function for Hasse diagrams.

dGraph2sc :: Int -> [(Int, Int)] -> SimplicialComplex Source #

Given the number of vertices in a directed graph, and pairs representing the direction of each edge, construct a 1-dimensional simplicial complex in the canonical way. Betti numbers of this simplicial complex can be used to count cycles and connected components.

encodeDirectedGraph :: Int -> [(Int, Int)] -> HasseDiagram Source #

Given the number of vertices in a directed graph, and pairs representing the direction of each edge (initial, terminal), construct a Hasse diagram representing the graph.

directedFlagComplex :: HasseDiagram -> HasseDiagram Source #

Given a Hasse diagram representing a directed graph, construct the diagram representing the directed clique/flag complex of the graph. Algorithm adapted from the one shown in the supplementary materials of this paper: https://www.frontiersin.org/articles/10.3389/fncom.2017.00048/full

hDiagram2sc :: HasseDiagram -> SimplicialComplex Source #

Convert a Hasse diagram to a simplicial complex.