Graph.GraphDrawing

Documentation

layeredGraphAndCols :: (NodeClass n, Show n, EdgeClass e, Show e) => Bool -> CGraph n e -> (CGraphL n e, (Map GraphMoveX [UINode], Map Int [Column]))

Layout a directed acyclic graph in several steps (Sugiyama) 1. Assign the nodes to several layers (longest path) 2. Dummy vertices for lines that are longer than a layer 3. Reduce crossings, place the longest path on top 4. Assign y-coordinates to the nodes so that long lines that pass several layers are as straight as possible

layeredGraph :: (Unbox UINode, NodeClass n, Show n, EdgeClass e, Show e) => Bool -> CGraph n e -> CGraphL n e

fr :: (Int, n) -> (UINode, n)

graphvizNodes :: (CGraph n e, Map Int [Column]) -> String

primitiveYCoordinateAssignement :: (CGraph n e, [[UINode]]) -> CGraphL n e

See "Fast and Simple Horizontal Coordinate Assignment" (Brandes, Köpf)

yCoordinateAssignement :: (NodeClass n, EdgeClass e) => (CGraph n e, [[UINode]]) -> CGraphL n e

horizontalBalancing :: Map UINode (X, Y) -> Map UINode (X, Y) -> Map UINode (X, Y) -> Map UINode (X, Y) -> Map UINode (X, Y)

type X = Int

type Y = Int

type YN = (Y, (UINode, Bool))

data MYN

Constructors

Single (Y, (UINode, Bool))

Middle (Y, (UINode, Bool))

UpLowMedian (Y, (UINode, Bool)) (Y, (UINode, Bool))

Instances

Show MYN

Defined in Graph.GraphDrawing

Methods

showsPrec :: Int -> MYN -> ShowS

show :: MYN -> String

showList :: [MYN] -> ShowS

Eq MYN

Defined in Graph.GraphDrawing

Methods

(==) :: MYN -> MYN -> Bool

(/=) :: MYN -> MYN -> Bool

Ord MYN

Defined in Graph.GraphDrawing

Methods

compare :: MYN -> MYN -> Ordering

(<) :: MYN -> MYN -> Bool

(<=) :: MYN -> MYN -> Bool

(>) :: MYN -> MYN -> Bool

(>=) :: MYN -> MYN -> Bool

max :: MYN -> MYN -> MYN

min :: MYN -> MYN -> MYN

type Median = Map UINode MYN

biasedAlignment :: (NodeClass n, EdgeClass e) => CGraph n e -> Map UINode Y -> (Median, Median) -> [[(UINode, Bool)]] -> (Bool, Bool) -> Map UINode (X, Y)

toNode :: ((a1, (a2, b1)), (a3, (b2, b3))) -> (a2, b2)

tuples :: [a] -> [(a, a)]

type Insp = (Map Int (MYN, MYN), Map Int (MYN, MYN))

sweepForIndependentEdgeLists :: (NodeClass n, EdgeClass e) => CGraph n e -> (Median, Median) -> Set (UINode, UINode) -> (Bool, Bool) -> Insp -> (Y, Y) -> ([(UINode, Bool)], [(UINode, Bool)]) -> Set (MYN, MYN) -> [[(MYN, MYN)]]

Takes two layers and returns a list of lists of independent edges. A list A of edges is independent of a list B of edges if every edge of A does not intersect or connect any edge of B. This sweeping should save some time because graphs often have edges crossing near to each other. The number of intersections has been reduced in crossingreduction. Because of this we can assume that most edges are quite short and rectangular to layer0 and layer1. A sweep in the parallel direction of the two layers should reduce the number of edges that have to be examined. The overall algorithm (sweep + resolve) should have a runtime more like n*log(n) instead of n², because we only have to search for conflicts inside of these independent lists. The Brandes-Köpf paper is not explaining very well how they find intersections between two layers. I doubt that the whole algorithm is O(n). It seems more like a quadratic runtime in the worst case. Even finding the number of intersections (without giving back the exact edges that intersect) is O(n log n), See: Simple and Efficient Bilayer Cross Counting by Barth, Mutzel, Jünger or chapter 33 of Cormen: Introduction to algorithms If several edges emanate from a node the algorithm takes (one of the) the median. (e.g. three edges have one median, 4 edges have two) The sweep works by looking at the next node in the two layers, and comparing which node deletes more edges and introduces less new edges from the set of edges to look at. Every edge has a start node (first appearing at its y-position) and an end node. A start node means adding an edge when its source or target node appears in one of the two layers, and the edge disappears when both its nodes have been swept over.

data EdgeTy a

Either e0 prevails against all e1s or all e1s prevail against e0

Constructors

E0Prevails a

E1Prevails a

NoIntersect (a, a)

Instances

Show a => Show (EdgeTy a)

Defined in Graph.GraphDrawing

Methods

showsPrec :: Int -> EdgeTy a -> ShowS

show :: EdgeTy a -> String

showList :: [EdgeTy a] -> ShowS

Eq a => Eq (EdgeTy a)

Defined in Graph.GraphDrawing

Methods

(==) :: EdgeTy a -> EdgeTy a -> Bool

(/=) :: EdgeTy a -> EdgeTy a -> Bool

resolveConflicts :: (Bool, Bool) -> [(MYN, MYN)] -> [(YN, YN)]

toYN :: Bool -> (MYN, MYN) -> ((Y, (UINode, Bool)), (Y, (UINode, Bool)))

resolveConfs :: (Bool, Bool) -> [(MYN, MYN)] -> Int -> [(MYN, MYN)]

Compare all edges of a layer with each other. Worst case: O(n²). But n can shrink fast in every round and n is small, because of sweepForIndependentEdgeLists

isConsistent :: [EdgeTy (MYN, MYN)] -> EdgeTy Bool

The resolveConflicts-algorithm has to be constructed in a consistent way It should be impossible that edge e has priority to edge x (keeping e), and another edge y has priority to edge e (deleting e). It would not be clear if e has to be deleted or not

conflict :: Bool -> (MYN, MYN) -> (MYN, MYN) -> EdgeTy (MYN, MYN)

cases :: Bool -> (MYN, MYN) -> (MYN, MYN) -> EdgeTy (MYN, MYN)

Given two edges that intersect or connect, which one will prevail?

getYN :: Bool -> MYN -> (Y, (UINode, Bool))

getY :: Bool -> MYN -> Y

getN :: MYN -> [UINode]

ranksame :: [[UINode]] -> String

col :: Int -> UINode -> String

align :: EdgeClass e => CGraph n e -> [[UINode]] -> [(UINode, UINode)] -> (Bool, Bool) -> Map UINode (Int, Int)

type YNode = (YPos, Channel, UINode, IsDummy)

type YPos = Word32

type IsDummy = Bool

data Dir

Constructors

LeftToRight

RightToLeft

Instances

Show Dir

Defined in Graph.GraphDrawing

Methods

showsPrec :: Int -> Dir -> ShowS

show :: Dir -> String

showList :: [Dir] -> ShowS

leftToRight :: Dir -> Bool

longestinfrequentPaths :: EdgeClass e => NodeClass n => CGraph n e -> [[UINode]] -> Vector Int

startNodes :: EdgeClass e => CGraph n e -> [Word32] -> [Word32] -> [Word32]

liPaths :: EdgeClass e => NodeClass n => CGraph n e -> [[UINode]] -> [UINode] -> UINode -> Vector Int

myNub :: Ord a => [a] -> [a]

myNub2 :: [(Int, UINode)] -> [(Int, UINode)]

type UnconnectedChildren = [UINode]

longestPathAlgo :: (NodeClass n, EdgeClass e) => CGraph n e -> (CGraph n e, [[UINode]])

Every graph has a longest path, which is the center of attention for us Return layers of node ids This algorithm is a little bit more complicated because we can connect nodes "vertically", so that they are guaranteed to be all in one vertical layer All nodes before this vertical layer have to be placed in layers before we can proceed

addMissingInputNodes :: (NodeClass n, Show n, EdgeClass e) => CGraph n e -> CGraph n e

partitionNodes :: EdgeClass e => CGraph n e -> Vector UINode -> (Vector UINode, Vector UINode)

partition nodes into non-vertically connected nodes and vertically connected nodes

addConnectionVertices :: (NodeClass n, Show n, EdgeClass e, Show e) => (CGraph n e, [[UINode]]) -> (CGraph n e, [[UINode]])

addConnectionVs :: (NodeClass n, Show n, EdgeClass e, Show e) => (CGraph n e, [[UINode]]) -> (CGraph n e, [[UINode]])

insertConnNode :: (NodeClass n, Show n, EdgeClass e) => CGraph n e -> UINode -> UINode -> Maybe Channel -> Channel -> CGraph n e

crossingReduction :: (NodeClass n, Show n, EdgeClass e, Show e) => Int -> Bool -> (CGraph n e, [[UINode]]) -> (CGraph n e, [[UINode]])

crossR :: (NodeClass n, Show n, EdgeClass e, Show e) => CGraph n e -> Dir -> [[Int]] -> [Int] -> Bool -> [[Int]]

lv :: EdgeClass e => CGraph n e -> [Int] -> [(Int, Bool)]

edgesEnum :: (NodeClass n, EdgeClass e, Show e) => IntMap UINode -> IntMap UINode -> CGraph n e -> Dir -> [UINode] -> [(YNode, YNode)]

isNotMainFunctionArg :: NodeClass n => CGraph n e -> UINode -> Bool

barycenter :: (NodeClass n, Show n, EdgeClass e, Show e) => CGraph n e -> Dir -> [Int] -> [Int] -> Int -> [Int]

median :: EdgeClass e => CGraph n e -> [Int] -> [Int] -> [Int]

lexicographicSort :: Vector (YNode, YNode) -> Vector (YNode, YNode)

primitiveInversionCount :: Vector Int -> Int

See: Simple and Efficient Bilayer Cross Counting by Barth, Mutzel, Jünger

merge :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)

split :: [a] -> ([a], [a])

mergeSort :: ([Int], Int) -> ([Int], Int)

fromAdj :: EdgeClass e => Map Word32 nl -> [(Word32, [Word32], [e])] -> Graph nl [e]

getColumns :: EdgeClass e => CGraphL n e -> (Map X [UINode], Map Int [Column])

To be able to jump vertically between nodes in an interactive ui

getRows :: CGraphL n e -> Map Y [UINode]

To be able to jump horizontally between nodes in an interactive ui