Graph.IntMap

Documentation

class EdgeAttribute el where

Convert a complex edge label to an attribute with 8 bits How to do this depends on which edges have to be filtered fast

Methods

fastEdgeAttr :: el -> Word8

edgeFromAttr :: Map Word8 el

show_e :: Maybe el -> String

bases :: el -> [Edge8]

data Graph nl el

The edges are enumerated, because sometimes the edge attrs are not continuous and it is impossible to try all possible 32 bit attrs

Constructors

Graph

Fields

• outgoingNodes :: IntMap (Set Node)

  A Graph of outgoing 32 bit nodeEdges with 24 bit nodes and 8 bit edges

• incomingNodes :: IntMap (Set Node)

  A Graph of incoming 32 bit nodeEdges with 24 bit nodes and 8 bit edges

• nodeLabels :: IntMap nl
• edgeLabels :: Map (Node, Node) el
• is32BitInt :: Bool
• showEdge :: Map Word8 el

Instances

(EdgeAttribute el, Eq el, Eq nl) => Eq (Graph nl el)

Defined in Graph.IntMap

Methods

(==) :: Graph nl el -> Graph nl el -> Bool

(/=) :: Graph nl el -> Graph nl el -> Bool

(EdgeAttribute el, Show nl, ExtractNodeType nl, Show el, Enum nl) => Show (Graph nl el)

Defined in Graph.IntMap

Methods

showsPrec :: Int -> Graph nl el -> ShowS

show :: Graph nl el -> String

showList :: [Graph nl el] -> ShowS

Generic (Graph nl el)

Defined in Graph.IntMap

Associated Types

type Rep (Graph nl el) :: Type -> Type

Methods

from :: Graph nl el -> Rep (Graph nl el) x

to :: Rep (Graph nl el) x -> Graph nl el

type Rep (Graph nl el)

Defined in Graph.IntMap

type Rep (Graph nl el)

class ExtractNodeType nl where

if a node label is complicated, specify a short string to understand its type

Methods

extractNodeType :: nl -> String

type Edge = (Node, Node)

A tuple of nodes

newtype Edge8

In Javascript there are only 32 bit integers. If we want to squeeze a node and an edge into this we use 24 bits for the node and 8 bits for the edge

Constructors

Edge8 Word8

Instances

Show Edge8

Defined in Graph.IntMap

Methods

showsPrec :: Int -> Edge8 -> ShowS

show :: Edge8 -> String

showList :: [Edge8] -> ShowS

Construction

empty :: EdgeAttribute el => Graph nl el

Generate an empty graph with 32 bit node-edges (24 bit for the node) that can be used with code that ghcjs compiled to javascript

fromLists :: (EdgeAttribute el, Enum nl, Show nl, Show el) => Bool -> [(Node, nl)] -> [((Node, Node), el)] -> [((Node, Node), el)] -> Graph nl el

Construct a graph from a list of nodes, undirected edges and directed edges, the bool has to be true it uses 32 bit integers, if false it uses 64 bit integers

fromMaps :: (EdgeAttribute el, Show nl, Show el, Enum nl) => Bool -> IntMap nl -> Map (Node, Node) el -> Map (Node, Node) el -> Bool -> Graph nl el

Construct a graph from a node map, undirected edges map and directed edges map, b = True means 32 bit integers

insertNode :: EdgeAttribute el => Node -> nl -> Graph nl el -> Graph nl el

Insert node with node label

insertNodes :: EdgeAttribute el => [(Node, nl)] -> Graph nl el -> Graph nl el

Insert nodes with their label

insertEdge :: EdgeAttribute el => Maybe Bool -> Edge -> el -> Graph nl el -> Graph nl el

Inserting an edge If maybeIsBack is Nothing only one directed is edge from n0 to n1 is inserted If maybeIsBack is Just then a second directed edge from n1 to n0 is inserted isBack = True means an opposite directed edge that can be explored in both directions isBack = False means a undirected edge that also can be explored in both directions

insertEdges :: EdgeAttribute el => Maybe Bool -> [(Edge, el)] -> Graph nl el -> Graph nl el

Inserting an edge If maybeIsBack is Nothing only one directed is edge from n0 to n1 is inserted If maybeIsBack is Just then a second directed edge from n1 to n0 is inserted isBack = True means an opposite directed edge that can be explored in both directions isBack = False means a undirected edge that also can be explored in both directions

union :: Graph nl el -> Graph nl el -> Graph nl el

Makes a union over all components of the graph

Traversal

mapNode :: EdgeAttribute el => (nl0 -> nl1) -> Graph nl0 el -> Graph nl1 el

Mapping a function over the node labels

mapNodeWithKey :: EdgeAttribute el => (Key -> nl0 -> nl1) -> Graph nl0 el -> Graph nl1 el

Mapping a function over the node labels with node key

Deletion

deleteNode :: (EdgeAttribute el, Show nl, Show el, Enum nl) => el -> Node -> Graph nl el -> Graph nl el

Delete node with its nodelabel and also all outgoing and incoming edges with their edgeLabels

deleteNodes :: (Foldable t, EdgeAttribute el, Show nl, Show el, Enum nl) => el -> t Node -> Graph nl el -> Graph nl el

Delete nodes with their label

deleteEdge :: EdgeAttribute el => Maybe Bool -> Edge -> Graph nl el -> Graph nl el

"deleteEdge (n0, n1) graph" deletes the edgelabel of (n0,n1) and the nodeEdge that points from n0 to n1 If maybeIsBack is Just then a second directed edge from n1 to n0 is deleted isBack = True means an opposite directed edge that can be explored in both directions isBack = False means a undirected edge that also can be explored in both directions

deleteEdges :: (Foldable t, EdgeAttribute el) => Maybe Bool -> t Edge -> Graph nl el -> Graph nl el

Delete a list of (Node,Node) edges from the graph

Query

isNull :: Graph a1 a2 -> Bool

Are the node-/edge-maps of the graph all empty?

nodes :: Graph a el -> [Key]

The word32 keys of the node labels

edges :: Graph nl a -> [(Node, Node)]

List of (Node, Node)

lookupNode :: (Show nl, EdgeAttribute el) => Node -> Graph nl el -> Maybe nl

The nodelabel of the given node

lookupEdge :: (EdgeAttribute el, Show el) => Edge -> Graph nl el -> Maybe el

The edgelabel of the given edge of type (Node, Node)

adjacentNodesByAttr :: EdgeAttribute el => Graph nl el -> Bool -> Node -> Edge8 -> Vector Node

The list of adjacent edges can be divided with 8 bit attributes and all edges with a certain attribute selected

adjacentNodes :: EdgeAttribute el => Graph nl el -> Node -> el -> [Node]

Looking at all incoming and outgoing edges we get all adjacent nodes

parents :: EdgeAttribute el => Graph nl el -> Node -> el -> Vector Node

Following the incoming edges

children :: EdgeAttribute el => Graph nl el -> Node -> el -> Vector Node

Following the outgoing edges

Bit Operations

buildWord64 :: Word32 -> Word32 -> Word

Concatenate two Word32 to a Word (64 bit)

extractFirstWord32 :: Word -> Word32

Extract the first 32 bit of a 64 bit word

extractSecondWord32 :: Word -> Word32

Extract the second 32 bit of a 64 bit word

buildWord32 :: Word32 -> Word8 -> Word32

Nodes can use 24 bits, edges 8 bits

extractFirstWord24 :: Word32 -> Word32

Extract the first 24 bit of a 32 bit word

extractSecondWord8 :: Word32 -> Word8

Extract the last 8 bit of a 32 bit word

Displaying in hex for debugging

showHex :: Word -> String

Display a 64 bit word so that we can see the bits better

showHex32 :: Word32 -> String

Display a 32 bit word so that we can see the bits better