-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Graphs and networks library
--   
--   Represent, analyze and visualize graphs
@package graphite
@version 0.2.1.0

module Data.Graph.Types
class Graph g where size = length . edgePairs degrees g = vertexDegree g <$> vertices g maxDegree = maximum . degrees minDegree = minimum . degrees avgDegree g = fromIntegral (2 * size g) / (fromIntegral $ order g) density g = (2 * (e - n + 1)) / (n * (n - 3) + 2) where n = fromIntegral $ order g e = fromIntegral $ size g

-- | The Empty (order-zero) graph with no vertices and no edges
empty :: (Graph g, Hashable v) => g v e

-- | Retrieve the order of a graph | The <tt>order</tt> of a graph is its
--   number of vertices
order :: Graph g => g v e -> Int

-- | Retrieve the size of a graph | The <tt>size</tt> of a graph is its
--   number of edges
size :: (Graph g, Hashable v, Eq v) => g v e -> Int

-- | Retrieve the vertices of a graph
vertices :: Graph g => g v e -> [v]

-- | Retrieve the edges of a graph
edgePairs :: (Graph g, Hashable v, Eq v) => g v e -> [(v, v)]

-- | Tell if a vertex exists in the graph
containsVertex :: (Graph g, Hashable v, Eq v) => g v e -> v -> Bool

-- | Retrieve the adjacent vertices of a vertex
adjacentVertices :: (Graph g, Hashable v, Eq v) => g v e -> v -> [v]

-- | Total number of incident edges of a vertex
vertexDegree :: (Graph g, Hashable v, Eq v) => g v e -> v -> Int

-- | Degrees of a all the vertices in a graph
degrees :: (Graph g, Hashable v, Eq v) => g v e -> [Int]

-- | Maximum degree of a graph
maxDegree :: (Graph g, Hashable v, Eq v) => g v e -> Int

-- | Minimum degree of a graph
minDegree :: (Graph g, Hashable v, Eq v) => g v e -> Int

-- | Average degree of a graph
avgDegree :: (Graph g, Hashable v, Eq v) => g v e -> Double

-- | Density of a graph | The ratio of the number of existing edges in the
--   graph to the number of | posible edges
density :: (Graph g, Hashable v, Eq v) => g v e -> Double

-- | Insert a vertex into a graph | If the graph already contains the
--   vertex leave the graph untouched
insertVertex :: (Graph g, Hashable v, Eq v) => v -> g v e -> g v e

-- | Insert a many vertices into a graph | New vertices are inserted and
--   already contained vertices are left | untouched
insertVertices :: (Graph g, Hashable v, Eq v) => [v] -> g v e -> g v e

-- | Tell if an edge exists in the graph
containsEdgePair :: (Graph g, Hashable v, Eq v) => g v e -> (v, v) -> Bool

-- | Retrieve the incident edges of a vertex
incidentEdgePairs :: (Graph g, Hashable v, Eq v) => g v e -> v -> [(v, v)]

-- | Insert an edge into a graph | The involved vertices are inserted if
--   don't exist. If the graph already | contains the edge, its attribute
--   is updated
insertEdgePair :: (Graph g, Hashable v, Eq v) => (v, v) -> g v () -> g v ()

-- | Remove the edge from a graph present | The involved vertices are left
--   untouched
removeEdgePair :: (Graph g, Hashable v, Eq v) => (v, v) -> g v e -> g v e

-- | Remove the edge from a graph if present | The involved vertices are
--   also removed
removeEdgePairAndVertices :: (Graph g, Hashable v, Eq v) => (v, v) -> g v e -> g v e

-- | Tell if a graph is simple | A graph is <tt>simple</tt> if it has no
--   multiple edges nor loops
isSimple :: (Graph g, Hashable v, Eq v) => g v e -> Bool

-- | Tell if a graph is regular | A graph is <tt>regular</tt> when all of
--   its vertices have the same | number of adjacent vertices
isRegular :: Graph g => g v e -> Bool

-- | Generate a graph of Int vertices from an adjacency | square matrix
fromAdjacencyMatrix :: Graph g => [[Int]] -> Maybe (g Int ())

-- | Get the adjacency matrix representation of a grah
toAdjacencyMatrix :: Graph g => g v e -> [[Int]]

-- | Undirected Edge with attribute of type <i>e</i> between to Vertices of
--   type <i>v</i>
data Edge v e
Edge :: v -> v -> e -> Edge v e

-- | Directed Arc with attribute of type <i>e</i> between to Vertices of
--   type <i>v</i>
data Arc v e
Arc :: v -> v -> e -> Arc v e

-- | Construct an undirected <a>Edge</a> between two vertices
(<->) :: (Hashable v) => v -> v -> Edge v ()

-- | Construct a directed <a>Arc</a> between two vertices
(-->) :: (Hashable v) => v -> v -> Arc v ()
class IsEdge e

-- | Convert an edge to a pair discargind its attribute
toPair :: IsEdge e => e v a -> (v, v)

-- | Tell if an edge is a loop | An edge forms a <tt>loop</tt> if both of
--   its ends point to the same vertex
isLoop :: (IsEdge e, Eq v) => e v a -> Bool

-- | Weighted Edge attributes | Useful for computing some algorithms on
--   graphs
class Weighted a
weight :: Weighted a => a -> Double

-- | Labeled Edge attributes | Useful for graph plotting
class Labeled a
label :: Labeled a => a -> String

-- | To <a>Edge</a>s are equal if they point to the same vertices,
--   regardless of the | direction

-- | To <a>Arc</a>s are equal if they point to the same vertices, and the
--   directions | is the same

-- | Edges generator
arbitraryEdge :: (Arbitrary v, Arbitrary e, Ord v, Num v) => (v -> v -> e -> edge) -> Gen edge

-- | Each vertex maps to a <a>Links</a> value so it can poit to other
--   vertices
type Links v e = HashMap v e

-- | Insert a link directed to *v* with attribute *a* | If the connnection
--   already exists, the attribute is replaced
insertLink :: (Hashable v, Eq v) => v -> a -> Links v a -> Links v a

-- | Get the links for a given vertex
getLinks :: (Hashable v, Eq v) => v -> HashMap v (Links v e) -> Links v e

-- | Get <a>Arc</a>s from an association list of vertices and their links
linksToArcs :: [(v, Links v a)] -> [Arc v a]

-- | Get <a>Edge</a>s from an association list of vertices and their links
linksToEdges :: (Eq v) => [(v, Links v a)] -> [Edge v a]

-- | O(log n) Associate the specified value with the specified key in this
--   map. | If this map previously contained a mapping for the key, leave
--   the map | intact.
hashMapInsert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v
instance (GHC.Classes.Ord e, GHC.Classes.Ord v) => GHC.Classes.Ord (Data.Graph.Types.Arc v e)
instance (GHC.Read.Read e, GHC.Read.Read v) => GHC.Read.Read (Data.Graph.Types.Arc v e)
instance (GHC.Show.Show e, GHC.Show.Show v) => GHC.Show.Show (Data.Graph.Types.Arc v e)
instance (GHC.Classes.Ord e, GHC.Classes.Ord v) => GHC.Classes.Ord (Data.Graph.Types.Edge v e)
instance (GHC.Read.Read e, GHC.Read.Read v) => GHC.Read.Read (Data.Graph.Types.Edge v e)
instance (GHC.Show.Show e, GHC.Show.Show v) => GHC.Show.Show (Data.Graph.Types.Edge v e)
instance Data.Graph.Types.IsEdge Data.Graph.Types.Edge
instance Data.Graph.Types.IsEdge Data.Graph.Types.Arc
instance Data.Graph.Types.Weighted GHC.Types.Int
instance Data.Graph.Types.Weighted GHC.Types.Float
instance Data.Graph.Types.Weighted GHC.Types.Double
instance Data.Graph.Types.Labeled GHC.Base.String
instance Data.Graph.Types.Weighted (GHC.Types.Double, GHC.Base.String)
instance Data.Graph.Types.Labeled (GHC.Types.Double, GHC.Base.String)
instance (Test.QuickCheck.Arbitrary.Arbitrary v, Test.QuickCheck.Arbitrary.Arbitrary e, GHC.Num.Num v, GHC.Classes.Ord v) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Graph.Types.Edge v e)
instance (Test.QuickCheck.Arbitrary.Arbitrary v, Test.QuickCheck.Arbitrary.Arbitrary e, GHC.Num.Num v, GHC.Classes.Ord v) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Graph.Types.Arc v e)
instance (GHC.Classes.Eq v, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Graph.Types.Edge v a)
instance (GHC.Classes.Eq v, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Graph.Types.Arc v a)

module Data.Graph.UGraph

-- | Undirected Graph of Vertices in <i>v</i> and Edges with attributes in
--   <i>e</i>
newtype UGraph v e
UGraph :: HashMap v (Links v e) -> UGraph v e
[unUGraph] :: UGraph v e -> HashMap v (Links v e)

-- | <tt>O(n)</tt> Remove a vertex from a <a>UGraph</a> if present | Every
--   <a>Edge</a> incident to this vertex is also removed
removeVertex :: (Hashable v, Eq v) => v -> UGraph v e -> UGraph v e

-- | <tt>O(log n)</tt> Insert an undirected <a>Edge</a> into a
--   <a>UGraph</a> | The involved vertices are inserted if don't exist. If
--   the graph already | contains the Edge, its attribute is updated
insertEdge :: (Hashable v, Eq v) => Edge v e -> UGraph v e -> UGraph v e

-- | <tt>O(m*log n)</tt> Insert many directed <a>Edge</a>s into a
--   <a>UGraph</a> | Same rules as <a>insertEdge</a> are applied
insertEdges :: (Hashable v, Eq v) => [Edge v e] -> UGraph v e -> UGraph v e

-- | <tt>O(log n)</tt> Remove the undirected <a>Edge</a> from a
--   <a>UGraph</a> if present | The involved vertices are left untouched
removeEdge :: (Hashable v, Eq v) => Edge v e -> UGraph v e -> UGraph v e

-- | Same as <a>removeEdge</a> but the edge is an unordered pair
removeEdge' :: (Hashable v, Eq v) => (v, v) -> UGraph v e -> UGraph v e

-- | <tt>O(log n)</tt> Remove the undirected <a>Edge</a> from a
--   <a>UGraph</a> if present | The involved vertices are also removed
removeEdgeAndVertices :: (Hashable v, Eq v) => Edge v e -> UGraph v e -> UGraph v e

-- | Same as <a>removeEdgeAndVertices</a> but the edge is an unordered pair
removeEdgeAndVertices' :: (Hashable v, Eq v) => (v, v) -> UGraph v e -> UGraph v e

-- | <tt>O(n*m)</tt> Retrieve the <a>Edge</a>s of a <a>UGraph</a>
edges :: forall v e. (Hashable v, Eq v) => UGraph v e -> [Edge v e]

-- | <tt>O(log n)</tt> Tell if an undirected <a>Edge</a> exists in the
--   graph
containsEdge :: (Hashable v, Eq v) => UGraph v e -> Edge v e -> Bool

-- | Same as <a>containsEdge</a> but the edge is an unordered pair
containsEdge' :: (Hashable v, Eq v) => UGraph v e -> (v, v) -> Bool

-- | Retrieve the incident <a>Edge</a>s of a Vertex
incidentEdges :: (Hashable v, Eq v) => UGraph v e -> v -> [Edge v e]

-- | Tell if two <a>UGraph</a> are isomorphic
areIsomorphic :: UGraph v e -> UGraph v' e' -> Bool
isomorphism :: UGraph v e -> UGraph v' e' -> (v -> v')

-- | The Degree Sequence of a simple <a>UGraph</a> is a list of degrees
newtype DegreeSequence
DegreeSequence :: [Int] -> DegreeSequence
[unDegreeSequence] :: DegreeSequence -> [Int]

-- | Construct a <a>DegreeSequence</a> from a list of degrees | Negative
--   degree values are discarded
degreeSequence :: [Int] -> DegreeSequence

-- | Get the <a>DegreeSequence</a> of a simple <a>UGraph</a> | If the graph
--   is not <tt>simple</tt> (see <a>isSimple</a>) the result is Nothing
getDegreeSequence :: (Hashable v, Eq v) => UGraph v e -> Maybe DegreeSequence

-- | Tell if a <a>DegreeSequence</a> is a Graphical Sequence | A Degree
--   Sequence is a <tt>Graphical Sequence</tt> if a corresponding
--   <a>UGraph</a> for | it exists
isGraphicalSequence :: DegreeSequence -> Bool

-- | Get the corresponding <a>UGraph</a> of a <a>DegreeSequence</a> | If
--   the <a>DegreeSequence</a> is not graphical (see
--   <a>isGraphicalSequence</a>) the | result is Nothing
fromGraphicalSequence :: DegreeSequence -> Maybe (UGraph Int ())
instance GHC.Show.Show Data.Graph.UGraph.DegreeSequence
instance GHC.Classes.Ord Data.Graph.UGraph.DegreeSequence
instance GHC.Classes.Eq Data.Graph.UGraph.DegreeSequence
instance (GHC.Show.Show e, GHC.Show.Show v) => GHC.Show.Show (Data.Graph.UGraph.UGraph v e)
instance (GHC.Classes.Eq e, GHC.Classes.Eq v) => GHC.Classes.Eq (Data.Graph.UGraph.UGraph v e)
instance (Test.QuickCheck.Arbitrary.Arbitrary v, Test.QuickCheck.Arbitrary.Arbitrary e, Data.Hashable.Class.Hashable v, GHC.Num.Num v, GHC.Classes.Ord v) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Graph.UGraph.UGraph v e)
instance Data.Graph.Types.Graph Data.Graph.UGraph.UGraph

module Data.Graph.Visualize

-- | Plot an undirected <tt>UGraph</tt> to a PNG image file
plotIO :: (Show e) => UGraph Int e -> FilePath -> IO FilePath

-- | Same as <a>plotIO</a> but open the resulting image with
--   <i>xdg-open</i>
plotXdgIO :: (Show e) => UGraph Int e -> FilePath -> IO ()

module Data.Graph.Generation

-- | Probability value between 0 and 1
newtype Probability
P :: Float -> Probability

-- | Construct a <a>Probability</a> value
probability :: Float -> Probability

-- | Generate a random Erdős–Rényi G(n, p) model graph
erdosRenyiIO :: Graph g => Int -> Probability -> IO (g Int ())

-- | Generate a random square binary matrix | Useful for use with
--   <a>fromAdjacencyMatrix</a>
randomMatIO :: Int -> IO [[Int]]
instance GHC.Show.Show Data.Graph.Generation.Probability
instance GHC.Classes.Ord Data.Graph.Generation.Probability
instance GHC.Classes.Eq Data.Graph.Generation.Probability

module Data.Graph.DGraph

-- | Directed Graph of Vertices in <i>v</i> and Arcs with attributes in
--   <i>e</i>
newtype DGraph v e
DGraph :: HashMap v (Links v e) -> DGraph v e
[unDGraph] :: DGraph v e -> HashMap v (Links v e)

-- | The Degree Sequence of a <a>DGraph</a> is a list of pairs (Indegree,
--   Outdegree)
type DegreeSequence = [(Int, Int)]

-- | <tt>O(n)</tt> Remove a vertex from a <a>DGraph</a> if present | Every
--   <a>Arc</a> incident to this vertex is also removed
removeVertex :: (Hashable v, Eq v) => v -> DGraph v e -> DGraph v e

-- | <tt>O(log n)</tt> Insert a directed <a>Arc</a> into a <a>DGraph</a> |
--   The involved vertices are inserted if don't exist. If the graph
--   already | contains the Arc, its attribute is updated
insertArc :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e

-- | <tt>O(m*log n)</tt> Insert many directed <a>Arc</a>s into a
--   <a>DGraph</a> | Same rules as <a>insertArc</a> are applied
insertArcs :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e -> DGraph v e

-- | <tt>O(log n)</tt> Remove the directed <a>Arc</a> from a <a>DGraph</a>
--   if present | The involved vertices are left untouched
removeArc :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e

-- | Same as <a>removeArc</a> but the arc is an ordered pair
removeArc' :: (Hashable v, Eq v) => (v, v) -> DGraph v e -> DGraph v e

-- | <tt>O(log n)</tt> Remove the directed <a>Arc</a> from a <a>DGraph</a>
--   if present | The involved vertices are also removed
removeArcAndVertices :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e

-- | Same as <a>removeArcAndVertices</a> but the arc is an ordered pair
removeArcAndVertices' :: (Hashable v, Eq v) => (v, v) -> DGraph v e -> DGraph v e

-- | <tt>O(n*m)</tt> Retrieve the <a>Arc</a>s of a <a>DGraph</a>
arcs :: forall v e. (Hashable v, Eq v) => DGraph v e -> [Arc v e]

-- | Same as <a>arcs</a> but the arcs are ordered pairs, and their
--   attributes are | discarded
arcs' :: (Hashable v, Eq v) => DGraph v e -> [(v, v)]

-- | <tt>O(log n)</tt> Tell if a directed <a>Arc</a> exists in the graph
containsArc :: (Hashable v, Eq v) => DGraph v e -> Arc v e -> Bool

-- | Same as <a>containsArc</a> but the arc is an ordered pair
containsArc' :: (Hashable v, Eq v) => DGraph v e -> (v, v) -> Bool

-- | Retrieve the inbounding <a>Arc</a>s of a Vertex
inboundingArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e]

-- | Retrieve the outbounding <a>Arc</a>s of a Vertex
outboundingArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e]

-- | Retrieve the incident <a>Arc</a>s of a Vertex | Both inbounding and
--   outbounding arcs
incidentArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e]

-- | Tell if a <a>DGraph</a> is symmetric | All of its <a>Arc</a>s are
--   bidirected
isSymmetric :: DGraph v e -> Bool

-- | Tell if a <a>DGraph</a> is oriented | There are none bidirected
--   <a>Arc</a>s | Note: This is <i>not</i> the opposite of
--   <a>isSymmetric</a>
isOriented :: DGraph v e -> Bool

-- | Tell if a <a>DGraph</a> is isolated | A graph is <tt>isolated</tt> if
--   it has no edges, that is, it has a degree of 0 | TODO: What if it has
--   a loop?
isIsolated :: DGraph v e -> Bool

-- | Indegree of a vertex | The number of inbounding <a>Arc</a>s to a
--   vertex
vertexIndegree :: DGraph v e -> v -> Int

-- | Outdegree of a vertex | The number of outbounding <a>Arc</a>s from a
--   vertex
vertexOutdegree :: DGraph v e -> v -> Int

-- | Indegrees of all the vertices in a <a>DGraph</a>
indegrees :: DGraph v e -> [Int]

-- | Outdegree of all the vertices in a <a>DGraph</a>
outdegrees :: DGraph v e -> [Int]

-- | Tell if a <a>DGraph</a> is balanced | A Directed Graph is
--   <tt>balanced</tt> when its <tt>indegree = outdegree</tt>
isBalanced :: DGraph v e -> Bool

-- | Tell if a <a>DGraph</a> is regular | A Directed Graph is
--   <tt>regular</tt> when all of its vertices have the same number | of
--   adjacent vertices AND when the <tt>indegree</tt> and
--   <tt>outdegree</tt> of each vertex | are equal to each toher.
isRegular :: DGraph v e -> Bool

-- | Tell if a vertex is a source | A vertex is a <tt>source</tt> when its
--   <tt>indegree = 0</tt>
isSource :: DGraph v e -> v -> Bool

-- | Tell if a vertex is a sink | A vertex is a <tt>sink</tt> when its
--   <tt>outdegree = 0</tt>
isSink :: DGraph v e -> v -> Bool

-- | Tell if a vertex is internal | A vertex is a <tt>internal</tt> when
--   its neither a <tt>source</tt> nor a <tt>sink</tt>
isInternal :: DGraph v e -> v -> Bool

-- | Tell if a <a>DegreeSequence</a> is a Directed Graphic | A <tt>Directed
--   Graphic</tt> is a Degree Sequence for wich a <a>DGraph</a> exists
--   TODO: Kleitman–Wang | Fulkerson–Chen–Anstee theorem algorithms
isDirectedGraphic :: DegreeSequence -> Bool
instance (GHC.Show.Show e, GHC.Show.Show v) => GHC.Show.Show (Data.Graph.DGraph.DGraph v e)
instance (GHC.Classes.Eq e, GHC.Classes.Eq v) => GHC.Classes.Eq (Data.Graph.DGraph.DGraph v e)
instance Data.Graph.Types.Graph Data.Graph.DGraph.DGraph
instance (Test.QuickCheck.Arbitrary.Arbitrary v, Test.QuickCheck.Arbitrary.Arbitrary e, Data.Hashable.Class.Hashable v, GHC.Num.Num v, GHC.Classes.Ord v) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Graph.DGraph.DGraph v e)


-- | For Connectivity analisis purposes a <a>DGraph</a> can be converted
--   into a | <a>UGraph</a> using <tt>toUndirected</tt>
module Data.Graph.Connectivity

-- | Tell if a <a>UGraph</a> is connected | An Undirected Graph is
--   <tt>connected</tt> when there is a path between every pair | of
--   vertices
isConnected :: UGraph v e -> Bool

-- | Tell if a <a>UGraph</a> is disconnected | An Undirected Graph is
--   <tt>disconnected</tt> when its not <tt>connected</tt>. See |
--   <a>isConnected</a> TODO: An edgeles graph with two or more vertices is
--   disconnected
isDisconnected :: UGraph v e -> Bool

-- | Tell if two vertices of a <a>UGraph</a> are connected | Two vertices
--   are <tt>connected</tt> if it exists a path between them
areConnected :: UGraph v e -> v -> v -> Bool

-- | Tell if two vertices of a <a>UGraph</a> are disconnected | Two
--   vertices are <tt>disconnected</tt> if it doesn't exist a path between
--   them
areDisconnected :: UGraph v e -> v -> v -> Bool

-- | Retrieve all the unreachable vertices of a <a>UGraph</a> | The
--   <tt>unreachable vertices</tt> are those with no adjacent
--   <tt>Edge</tt>s
unreachableVertices :: UGraph v e -> [v]

-- | Tell if a <a>DGraph</a> is weakly connected | A Directed Graph is
--   <tt>weakly connected</tt> if the equivalent undirected graph | is
--   <tt>connected</tt>
isWeaklyConnected :: DGraph v e -> Bool