{-# LANGUAGE Safe #-}
module Data.Graph.Generators where
{-|
The information required to build a graph.
This datastructure is designed to occupy minimal space.
With n being the number of nodes, the edge list contains
tuples (from, to), denoting an edge from node *from* to node
*to* where *from* and *to* are integers less than the number
of nodes.
Note that for a graph with n nodes, the nodes are labelled
@[0..n-1]@.
This data structure is library-agnostic and can be converted
to arbitrary representations.
Copyright (C) 2014 Uli Köhler
Apache License v2.0
-}
data GraphInfo = GraphInfo {
numNodes :: Int, -- ^ Number of nodes
edges :: [(Int,Int)] -- ^ Edge list
} deriving (Eq, Show)
{-|
The context of a single graph node.
This data-structure is library-agnostic, however,
it is isomophic to FGL's UContext
-}
data GraphContext = GraphContext {
inEdges :: [Int], -- ^ Nodes having an edge to the current node
nodeLabel :: Int, -- ^ The node identifier of the current node
outEdges :: [Int] -- ^ Nodes having an ingoing edge from the current node
}
{-|
Check the integrity of a GraphInfo instance:
Ensures for every edge (i,j), the following condition is met:
@0 <= i < n && 0 <= j < n@
-}
checkGraphInfo :: GraphInfo -> Bool
checkGraphInfo (GraphInfo n edges) =
all (\(i, j) -> 0 <= i && i < n && 0 <= j && j < n) edges
-- | Get the edge count for a given GraphInfo instance
numEdges :: GraphInfo -> Int
numEdges = length . edges