{- | Module : Persistence.HasseDiagram Copyright : (c) Eben Kadile, 2018 License : BSD 3 Clause Maintainer : eben.cowley42@gmail.com Stability : experimental 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. -} module Persistence.HasseDiagram ( Node , HasseDiagram , hsd2String , dGraph2sc , encodeDirectedGraph , directedFlagComplex , hDiagram2sc ) where import Persistence.Util import Persistence.SimplicialComplex import Data.List as L import Data.Vector as V {- | 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 Node = (Vector Int, Vector Int, Vector Int) -- | Type representing an admissible Hasse diagram. Each entry in the vector represents a level in the Hasse diagram. type HasseDiagram = Vector (Vector Node) -- | Simple printing function for Hasse diagrams. hsd2String :: HasseDiagram -> String hsd2String = (L.intercalate "\n\n") . V.toList . (V.map (L.intercalate "\n" . V.toList . V.map show)) {- | 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. -} dGraph2sc :: Int -> [(Int, Int)] -> SimplicialComplex dGraph2sc v edges = (v, V.fromList [V.fromList $ L.map (\(i, j) -> (i `cons` (j `cons` V.empty), V.empty)) edges]) {- | 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. -} encodeDirectedGraph :: Int -> [(Int, Int)] -> HasseDiagram encodeDirectedGraph numVerts cxns = let verts = V.map (\n -> (n `cons` V.empty, V.empty, V.empty)) $ 0 `range` (numVerts - 1) encodeEdges _ vertices edges [] = V.empty `snoc` vertices `snoc` edges encodeEdges n vertices edges ((i, j):xs) = let v1 = vertices ! i; v2 = vertices ! j; edge = V.empty `snoc` j `snoc` i in encodeEdges (n + 1) (replaceElem i (one v1, two v1, (thr v1) `snoc` n) $ replaceElem j (one v2, two v2, (thr v2) `snoc` n) vertices) (edges `snoc` (edge, edge, V.empty)) xs in encodeEdges 0 verts V.empty cxns {- | 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 -} directedFlagComplex :: HasseDiagram -> HasseDiagram directedFlagComplex directedGraph = let edges = V.last directedGraph fstSinks = V.map (\e -> V.map (\(e0, _) -> (two e0) ! 0) $ findBothElems (\e1 e2 -> (two e1) ! 0 == (two e2) ! 0) (V.filter (\e0 -> (two e0) ! 1 == (two e) ! 1) edges) (V.filter (\e0 -> (two e0) ! 1 == (two e) ! 0) edges)) edges --take last level of nodes and their sinks --return modified last level, new level, and new sinks makeLevel :: Bool -> HasseDiagram -> Vector Node -> Vector (Vector Int) -> (Vector Node, Vector Node, Vector (Vector Int)) makeLevel fstIter result oldNodes oldSinks = let maxindex = V.length oldNodes --given a node and a specific sink --construct a new node with new sinks that has the given index --Fst output is the modified input nodes --snd output is the new node, thrd output is the sinks of the new node makeNode :: Int -> Int -> Int -> Vector Node -> Vector Int -> (Vector Node, Node, Vector Int) makeNode newIndex oldIndex sinkIndex nodes sinks = let sink = sinks ! sinkIndex oldNode = nodes ! oldIndex --the vertices of the new simplex are --the vertices of the old simplex plus the sink verts = sink `cons` (one oldNode) numFaces = V.length $ two oldNode --find all the faces of the new node by looking at the faces of the old node testTargets :: Int -> Node -> Vector Node -> Node -> Vector Int -> (Vector Node, Node, Vector Int) testTargets i onode onodes newNode newSinks = let faceVerts = if fstIter then one $ (V.last $ V.init $ result) ! ((two onode) ! i) else one $ (V.last $ result) ! ((two onode) ! i) in if i == numFaces then (onodes, newNode, newSinks) else case V.find (\(_, (v, _, _)) -> V.head v == sink && V.tail v == faceVerts) $ mapWithIndex (\j n -> (j, n)) onodes of Just (j, n) -> testTargets (i + 1) onode (replaceElem j (one n, two n, (thr n) `smartSnoc` newIndex) onodes) (one newNode, (two newNode) `snoc` j, thr newNode) (newSinks |^| (oldSinks ! j)) Nothing -> error "HasseDiagram.directedFlagComplex.makeDiagram.makeNode.testTargets. This is a bug. Please email the Persistence maintainers." in testTargets 0 oldNode nodes (verts, oldIndex `cons` V.empty, V.empty) sinks loopSinks :: Int -> Int -> Vector Node -> (Vector Node, Vector Node, Vector (Vector Int), Int) loopSinks nodeIndex lastIndex nodes = let node = oldNodes ! nodeIndex sinks = oldSinks ! nodeIndex numSinks = V.length sinks loop i (modifiedNodes, newNodes, newSinks) = if i == numSinks then (modifiedNodes, newNodes, newSinks, i + lastIndex) else let (modNodes, newNode, ns) = makeNode (i + lastIndex) nodeIndex i modifiedNodes sinks in loop (i + 1) (modNodes, newNodes `snoc` newNode, newSinks `snoc` ns) in loop 0 (nodes, V.empty, V.empty) loopNodes :: Int -> Int -> Vector Node -> Vector Node -> Vector (Vector Int) -> (Vector Node, Vector Node, Vector (Vector Int)) loopNodes i lastIndex nodes newNodes newSinks = if i == maxindex then (nodes, newNodes, newSinks) else let (modifiedNodes, nnodes, nsinks, index) = loopSinks i lastIndex nodes in loopNodes (i + 1) lastIndex modifiedNodes (newNodes V.++ nnodes) (newSinks V.++ nsinks) in loopNodes 0 0 oldNodes V.empty V.empty loopLevels :: Int -> HasseDiagram -> Vector Node -> Vector (Vector Int) -> HasseDiagram loopLevels iter diagram nextNodes sinks = let (modifiedNodes, newNodes, newSinks) = makeLevel (iter < 2) diagram nextNodes sinks newDiagram = diagram `snoc` modifiedNodes in if V.null newNodes then newDiagram else loopLevels (iter + 1) newDiagram newNodes newSinks in loopLevels 0 directedGraph edges fstSinks -- | Convert a Hasse diagram to a simplicial complex. hDiagram2sc :: HasseDiagram -> SimplicialComplex hDiagram2sc diagram = let sc = V.map (V.map not3) $ V.tail diagram in (V.length $ V.head diagram, (V.map (\(v, _) -> (v, V.empty)) $ sc ! 0) `cons` V.tail sc)