-- 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.9.5.1

module Data.Graph.Types

-- | Types that behave like graphs
--   
--   The main <a>Graph</a> instances are <tt>UGraph</tt> and
--   <tt>DGraph</tt>. The functions in this class should be used for
--   algorithms that are graph-directionality agnostic, otherwise use the
--   more specific ones in <tt>UGraph</tt> and <tt>DGraph</tt>
class Graph g where size = length . edgePairs density g = (2 * (e - n + 1)) / (n * (n - 3) + 2) where n = fromIntegral $ order g e = fromIntegral $ size g edgePairs g = tripleToPair <$> edgeTriples g adjacentVertices g v = tripleDestVertex <$> adjacentVertices' g v reachableAdjacentVertices g v = tripleDestVertex <$> reachableAdjacentVertices' g v degrees g = vertexDegree g <$> vertices g maxDegree = maximum . degrees minDegree = minimum . degrees avgDegree g = fromIntegral (2 * size g) / fromIntegral (order g) insertVertices vs g = foldl' (flip insertVertex) g vs incidentEdgePairs g v = tripleToPair <$> incidentEdgeTriples g v insertEdgeTriples es g = foldl' (flip insertEdgeTriple) g es insertEdgePair (v1, v2) = insertEdgeTriple (v1, v2, ()) insertEdgePairs es g = foldl' (flip insertEdgePair) g es removeVertices vs g = foldl' (flip removeVertex) g vs removeEdgePairs es g = foldl' (flip removeEdgePair) g es removeEdgePairAndVertices (v1, v2) g = removeVertex v2 $ removeVertex v1 $ removeEdgePair (v1, v2) g isolatedVertices g = filter (\ v -> vertexDegree g v == 0) $ vertices g fromList links = go links empty where go [] g = g go ((v, es) : rest) g = go rest $ foldr (\ (v', e) g' -> insertEdgeTriple (v, v', e) g') (insertVertex v g) es

-- | 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

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

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

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

-- | Retrieve the edges of a graph, ignoring its attributes
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

-- | Tell if two vertices are adjacent
areAdjacent :: (Graph g, Hashable v, Eq v) => g v e -> v -> v -> Bool

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

-- | Same as <a>adjacentVertices</a> but gives back the connecting edges
adjacentVertices' :: (Graph g, Hashable v, Eq v) => g v e -> v -> [(v, v, e)]

-- | Same as <a>adjacentVertices</a> but gives back only those vertices for
--   which the connecting edge allows the vertex to be reached.
--   
--   For an undirected graph this is equivalent to <a>adjacentVertices</a>,
--   but for the case of a directed graph, the directed arcs will constrain
--   the reachability of the adjacent vertices.
reachableAdjacentVertices :: (Graph g, Hashable v, Eq v) => g v e -> v -> [v]

-- | Same as <a>reachableAdjacentVertices</a> but gives back the connecting
--   edges
reachableAdjacentVertices' :: (Graph g, Hashable v, Eq v) => g v e -> v -> [(v, v, e)]

-- | 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

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

-- | Insert 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
incidentEdgeTriples :: (Graph g, Hashable v, Eq v) => g v e -> v -> [(v, v, e)]

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

-- | Get the edge between to vertices if it exists
edgeTriple :: (Graph g, Hashable v, Eq v) => g v e -> v -> v -> Maybe (v, v, e)

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

-- | Same as <a>insertEdgeTriple</a> but for multiple edges
insertEdgeTriples :: (Graph g, Hashable v, Eq v) => [(v, v, e)] -> g v e -> g v e

-- | Same as <a>insertEdgeTriple</a> but insert edge pairs in graphs with
--   attribute less edges
insertEdgePair :: (Graph g, Hashable v, Eq v) => (v, v) -> g v () -> g v ()

-- | Same as <a>insertEdgePair</a> for multiple edges
insertEdgePairs :: (Graph g, Hashable v, Eq v) => [(v, v)] -> g v () -> g v ()

-- | Remove a vertex from a graph if present. Every edge incident to this
--   vertex also gets removed
removeVertex :: (Graph g, Hashable v, Eq v) => v -> g v e -> g v e

-- | Same as <a>removeVertex</a> but for multiple vertices
removeVertices :: (Graph g, Hashable v, Eq v) => [v] -> g v e -> g v e

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

-- | Same as <a>removeEdgePair</a> but for multiple edges
removeEdgePairs :: (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 also
--   get removed
removeEdgePairAndVertices :: (Graph g, Hashable v, Eq v) => (v, v) -> g v e -> g v e

-- | Retrieve the isolated vertices of a graph, if any
isolatedVertices :: (Graph g, Hashable v, Eq v) => g v e -> [v]

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

-- | Union of two graphs
union :: (Graph g, Hashable v, Eq v) => g v e -> g v e -> g v e

-- | Intersection of two graphs
intersection :: (Graph g, Hashable v, Eq v, Eq e) => g v e -> g v e -> g v e

-- | Convert a graph to an adjacency list with vertices in type <i>v</i>
--   and edge attributes in <i>e</i>
toList :: (Graph g, Hashable v, Eq v) => g v e -> [(v, [(v, e)])]

-- | Construct a graph from an adjacency list with vertices in type /v and
--   edge attributes in <i>e</i>
fromList :: (Graph g, Hashable v, Eq v) => [(v, [(v, e)])] -> g v e

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

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

-- | Types that represent edges
--   
--   The main <a>IsEdge</a> instances are <a>Edge</a> for undirected edges
--   and <a>Arc</a> for directed edges.
class IsEdge e

-- | Retrieve the origin vertex of the edge
originVertex :: IsEdge e => e v a -> v

-- | Retrieve the destination vertex of the edge
destinationVertex :: IsEdge e => e v a -> v

-- | Retrieve the attribute of the edge
attribute :: IsEdge e => e v a -> a

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

-- | Convert a pair to an edge, where it's attribute is unit
fromPair :: IsEdge e => (v, v) -> e v ()

-- | Convert an edge to a triple, where the 3rd element it's the edge
--   attribute
toTriple :: IsEdge e => e v a -> (v, v, a)

-- | Convert a triple to an edge
fromTriple :: IsEdge e => (v, v, a) -> e v a

-- | 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

-- | 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 attribute less undirected <a>Edge</a> between two
--   vertices
(<->) :: (Hashable v) => v -> v -> Edge v ()

-- | Construct an attribute less directed <a>Arc</a> between two vertices
(-->) :: (Hashable v) => v -> v -> Arc v ()

-- | Weighted Edge attributes
class Weighted e
weight :: Weighted e => e -> Double

-- | Labeled Edge attributes
class Labeled e
label :: Labeled e => e -> String

-- | Convert a triple to a pair by ignoring the third element
tripleToPair :: (a, b, c) -> (a, b)

-- | Convert a pair to a triple where the 3rd element is unit
pairToTriple :: (a, b) -> (a, b, ())

-- | Get the origin vertex from an edge triple
tripleOriginVertex :: (v, v, e) -> v

-- | Get the destination vertex from an edge triple
tripleDestVertex :: (v, v, e) -> v

-- | Get the attribute from an edge triple
tripleAttribute :: (v, v, e) -> e
instance GHC.Generics.Generic (Data.Graph.Types.Arc v e)
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.Generics.Generic (Data.Graph.Types.Edge 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 (Control.DeepSeq.NFData v, Control.DeepSeq.NFData e) => Control.DeepSeq.NFData (Data.Graph.Types.Edge v e)
instance (Control.DeepSeq.NFData v, Control.DeepSeq.NFData e) => Control.DeepSeq.NFData (Data.Graph.Types.Arc 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.Base.Functor (Data.Graph.Types.Edge v)
instance GHC.Base.Functor (Data.Graph.Types.Arc v)
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.Traversal

-- | breadh-first-search vertices starting at a particular vertex
bfsVertices :: (Graph g, Hashable v, Eq v, Ord v) => g v e -> v -> [v]

-- | depth-first-search vertices starting at a particular vertex
dfsVertices :: (Graph g, Hashable v, Eq v, Ord v) => g v e -> v -> [v]

module Data.Graph.Read

-- | Read a graph from a CSV file of adjacency lists
--   
--   The CSV lines:
--   
--   <pre>
--   "1,2,3,4"
--   "2,1,4,5"
--   </pre>
--   
--   produce the graph with this list of edge pairs:
--   
--   <pre>
--   [(1, 2), (1, 3), (1, 4), (2, 1), (2, 4), (2, 5)]
--   </pre>
fromCsv :: Graph g => (Hashable v, Eq v, FromField v) => FilePath -> IO (Either String (g v ()))

-- | Same as <a>fromCsv</a> but rise an exception when parsing fails
fromCsv' :: Graph g => (Hashable v, Eq v, FromField v) => FilePath -> IO (g v ())

module Data.Graph.UGraph

-- | Undirected Graph of Vertices in <i>v</i> and Edges with attributes in
--   <i>e</i>
data UGraph v e

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

-- | Same as <a>insertEdge</a> but for a list of <a>Edge</a>s
insertEdges :: (Hashable v, Eq v) => [Edge v e] -> UGraph v e -> UGraph v e

-- | 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 for a list of <a>Edge</a>s
removeEdges :: (Hashable v, Eq v) => [Edge v e] -> UGraph v e -> UGraph v e

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

-- | 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]

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

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

-- | Convert a <a>UGraph</a> to a list of <a>Edge</a>s discarding isolated
--   vertices
--   
--   Note that because <a>toEdgesList</a> discards isolated vertices: &gt;
--   fromEdgesList . toEdgesList /= id
toEdgesList :: (Hashable v, Eq v) => UGraph v e -> [Edge v e]

-- | Construct a <a>UGraph</a> from a list of <a>Edge</a>s
fromEdgesList :: (Hashable v, Eq v) => [Edge v e] -> UGraph v e

-- | Pretty print a <a>UGraph</a>
prettyPrint :: (Hashable v, Eq v, Show v, Show e) => UGraph v e -> String
instance GHC.Generics.Generic (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 (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v, GHC.Show.Show v, GHC.Show.Show e) => GHC.Show.Show (Data.Graph.UGraph.UGraph v e)
instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v, GHC.Read.Read v, GHC.Read.Read e) => GHC.Read.Read (Data.Graph.UGraph.UGraph v e)
instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v) => GHC.Base.Monoid (Data.Graph.UGraph.UGraph v e)
instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v) => Data.Semigroup.Semigroup (Data.Graph.UGraph.UGraph v e)
instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v) => GHC.Base.Functor (Data.Graph.UGraph.UGraph v)
instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v) => Data.Foldable.Foldable (Data.Graph.UGraph.UGraph v)
instance (Control.DeepSeq.NFData v, Control.DeepSeq.NFData e) => Control.DeepSeq.NFData (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.UGraph.DegreeSequence

-- | The Degree Sequence of a simple <a>UGraph</a> is a list of degrees of
--   the vertices in the graph
--   
--   Use <a>degreeSequence</a> to construct a valid Degree Sequence
data DegreeSequence

-- | Construct a <a>DegreeSequence</a> from a list of degrees. Negative
--   degree values get 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. Uses the Havel-Hakimi algorithm
isGraphicalSequence :: DegreeSequence -> Bool

-- | Tell if a <a>DegreeSequence</a> is a Directed Graphic
--   
--   A <tt>Directed Graphic</tt> is a Degree Sequence for which a
--   <tt>DGraph</tt> exists TODO: Kleitman–Wang | Fulkerson–Chen–Anstee
--   theorem algorithms
isDirectedGraphic :: DegreeSequence -> Bool

-- | Tell if a <a>DegreeSequence</a> holds the Handshaking lemma, that is,
--   if the number of vertices with odd degree is even
holdsHandshakingLemma :: 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.DegreeSequence
instance GHC.Classes.Ord Data.Graph.UGraph.DegreeSequence.DegreeSequence
instance GHC.Classes.Eq Data.Graph.UGraph.DegreeSequence.DegreeSequence

module Data.Graph.DGraph.DegreeSequence

-- | The Degree Sequence of a <tt>DGraph</tt> is a list of pairs (Indegree,
--   Outdegree)
newtype DegreeSequence
DegreeSequence :: [(Int, Int)] -> DegreeSequence
[unDegreeSequence] :: DegreeSequence -> [(Int, Int)]
instance GHC.Show.Show Data.Graph.DGraph.DegreeSequence.DegreeSequence
instance GHC.Classes.Ord Data.Graph.DGraph.DegreeSequence.DegreeSequence
instance GHC.Classes.Eq Data.Graph.DGraph.DegreeSequence.DegreeSequence

module Data.Graph.DGraph

-- | Directed Graph of Vertices in <i>v</i> and Arcs with attributes in
--   <i>e</i>
data DGraph v e

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

-- | Same as <a>insertArc</a> but for a list of <a>Arc</a>s
insertArcs :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e -> DGraph v e

-- | 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 for a list of <a>Arc</a>s
removeArcs :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e -> DGraph v e

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

-- | 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]

-- | Tell if a directed <a>Arc</a> exists in the graph
containsArc :: (Hashable v, Eq v) => DGraph v e -> Arc v e -> 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
--   
--   The <tt>incident</tt> arcs of a vertex are all the inbounding and
--   outbounding arcs of the vertex
incidentArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e]

-- | Indegree of a vertex
--   
--   The <tt>indegree</tt> of a vertex is the number of inbounding
--   <a>Arc</a>s to a vertex
vertexIndegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int

-- | Outdegree of a vertex
--   
--   The <tt>outdegree</tt> of a vertex is the number of outbounding
--   <a>Arc</a>s from a vertex
vertexOutdegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int

-- | Indegrees of all the vertices in a <a>DGraph</a>
indegrees :: (Hashable v, Eq v) => DGraph v e -> [Int]

-- | Outdegree of all the vertices in a <a>DGraph</a>
outdegrees :: (Hashable v, Eq v) => DGraph v e -> [Int]

-- | Tell if a <a>DGraph</a> is symmetric
--   
--   A directed graph is <tt>symmetric</tt> if all of its <a>Arc</a>s are
--   bi-directed
isSymmetric :: DGraph v e -> Bool

-- | Tell if a <a>DGraph</a> is oriented
--   
--   A directed graph is <tt>oriented</tt> if there are none bi-directed
--   <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 balanced
--   
--   A directed graph is <tt>balanced</tt> when its <tt>indegree =
--   outdegree</tt>
isBalanced :: (Hashable v, Eq v) => 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 <i>AND</i> when the <tt>indegree</tt>
--   and <tt>outdegree</tt> of each vertex are equal to each other.
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 :: (Hashable v, Eq v) => 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 :: (Hashable v, Eq v) => DGraph v e -> v -> Bool

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

-- | Get the transpose of a <a>DGraph</a>
--   
--   The <tt>transpose</tt> of a directed graph is another directed graph
--   where all of its arcs are reversed
transpose :: (Hashable v, Eq v) => DGraph v e -> DGraph v e

-- | Convert a directed <a>DGraph</a> to an undirected <tt>UGraph</tt> by
--   converting all of its <a>Arc</a>s into <a>Edge</a>s
toUndirected :: (Hashable v, Eq v) => DGraph v e -> UGraph v e

-- | Convert a <a>DGraph</a> to a list of <a>Arc</a>s discarding isolated
--   vertices
--   
--   Note that because <a>toArcsList</a> discards isolated vertices:
--   
--   <pre>
--   fromArcsList . toArcsList /= id
--   </pre>
toArcsList :: (Hashable v, Eq v) => DGraph v e -> [Arc v e]

-- | Construct a <a>DGraph</a> from a list of <a>Arc</a>s
fromArcsList :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e

-- | Pretty print a <a>DGraph</a>
prettyPrint :: (Hashable v, Eq v, Show v, Show e) => DGraph v e -> String
instance GHC.Generics.Generic (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.Hashable.Class.Hashable v, GHC.Classes.Eq v, GHC.Show.Show v, GHC.Show.Show e) => GHC.Show.Show (Data.Graph.DGraph.DGraph v e)
instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v, GHC.Read.Read v, GHC.Read.Read e) => GHC.Read.Read (Data.Graph.DGraph.DGraph v e)
instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v) => GHC.Base.Monoid (Data.Graph.DGraph.DGraph v e)
instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v) => Data.Semigroup.Semigroup (Data.Graph.DGraph.DGraph v e)
instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v) => GHC.Base.Functor (Data.Graph.DGraph.DGraph v)
instance (Data.Hashable.Class.Hashable v, GHC.Classes.Eq v) => Data.Foldable.Foldable (Data.Graph.DGraph.DGraph v)
instance (Control.DeepSeq.NFData v, Control.DeepSeq.NFData e) => Control.DeepSeq.NFData (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)

module Data.Graph.Generation

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

-- | <a>erdosRenyi</a> convinience <a>UGraph</a> generation function
erdosRenyiU :: Int -> Float -> IO (UGraph Int ())

-- | <a>erdosRenyi</a> convinience <a>DGraph</a> generation function
erdosRenyiD :: Int -> Float -> IO (DGraph Int ())

-- | Generate a random graph with vertices in <i>v</i> across range of
--   given bounds, random edge attributes in <i>e</i> within given bounds,
--   and some existing probability for each possible edge as per the
--   Erdős–Rényi model
rndGraph :: forall g v e. (Graph g, Hashable v, Eq v, Enum v, Random e) => (v, v) -> (e, e) -> Float -> IO (g v e)

-- | Same as <a>rndGraph</a> but uses attributeless edges
rndGraph' :: forall g v. (Graph g, Hashable v, Eq v, Enum v) => (v, v) -> Float -> IO (g v ())

-- | Generate a random adjacency matrix
--   
--   Useful for use with <a>fromAdjacencyMatrix</a>
rndAdjacencyMatrix :: Int -> IO [[Int]]

module Data.Graph.Morphisms

-- | Tell if two graphs are isomorphic TODO: check first: same number of
--   vertices, same number of edges
areIsomorphic :: Graph g => g v e -> g v' e' -> Bool
isomorphism :: Graph g => g v e -> g v' e' -> (v -> v')

-- | Tell if a <a>UGraph</a> is regular
--   
--   An undirected graph is <tt>regular</tt> if each vertex has the same
--   degree
isURegular :: UGraph v e -> Bool

-- | Tell if a <a>DGraph</a> is regular
--   
--   A directed graph is <tt>regular</tt> if each vertex has the same
--   indegree and outdegree
isDRegular :: DGraph v e -> Bool

module Data.Graph.Visualize

-- | Plot an undirected <a>UGraph</a>
plotUGraph :: (Hashable v, Ord v, PrintDot v, Show v, Show e) => UGraph v e -> IO ThreadId

-- | Plot a directed <a>DGraph</a>
plotDGraph :: (Hashable v, Ord v, PrintDot v, Show v, Show e) => DGraph v e -> IO ThreadId

-- | Same as <a>plotUGraph</a> but render edge attributes
plotUGraphEdged :: (Hashable v, Ord v, PrintDot v, Show v, Show e) => UGraph v e -> IO ThreadId

-- | Same as <a>plotDGraph</a> but render edge attributes
plotDGraphEdged :: (Hashable v, Ord v, PrintDot v, Show v, Show e) => DGraph v e -> IO ThreadId

-- | Plot an undirected <a>UGraph</a> to a PNG image file
plotUGraphPng :: (Hashable v, Ord v, PrintDot v, Show v, Show e) => UGraph v e -> FilePath -> IO FilePath

-- | Plot a directed <a>DGraph</a> to a PNG image file
plotDGraphPng :: (Hashable v, Ord v, PrintDot v, Show v, Show e) => DGraph v e -> FilePath -> IO FilePath


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

-- | Tell if two vertices of a graph are connected
--   
--   Two vertices are <tt>connected</tt> if it exists a path between them.
--   The order of the vertices is relevant when the graph is directed
areConnected :: forall g v e. (Graph g, Hashable v, Eq v, Ord v) => g v e -> v -> v -> Bool

-- | Opposite of <a>areConnected</a>
areDisconnected :: (Graph g, Hashable v, Eq v, Ord v) => g v e -> v -> v -> Bool

-- | Tell if a vertex is isolated
--   
--   A vertex is <tt>isolated</tt> if it has no incident edges, that is, it
--   has a degree of zero
isIsolated :: (Graph g, Hashable v, Eq v) => g v e -> v -> Bool

-- | Tell if a graph is connected
--   
--   An undirected graph is <tt>connected</tt> when there is a path between
--   every pair of vertices FIXME: Use a O(n) algorithm
isConnected :: (Graph g, Hashable v, Eq v, Ord v) => g v e -> Bool

-- | Tell if a graph is bridgeless
--   
--   A graph is <tt>bridgeless</tt> if it has no edges that, when removed,
--   split the graph in two isolated components FIXME: Use a O(n) algorithm
isBridgeless :: (Hashable v, Eq v, Ord v) => UGraph v e -> Bool

-- | Tell if a <a>UGraph</a> is orientable
--   
--   An undirected graph is <tt>orientable</tt> if it can be converted into
--   a directed graph that is <tt>strongly connected</tt> (See
--   <a>isStronglyConnected</a>)
isOrientable :: (Hashable v, Eq v, Ord v) => UGraph v e -> Bool

-- | Tell if a <a>DGraph</a> is weakly connected
--   
--   A directed graph is <tt>weakly connected</tt> if the underlying
--   undirected graph is <tt>connected</tt>
isWeaklyConnected :: (Hashable v, Eq v, Ord v) => DGraph v e -> Bool

-- | Tell if a <a>DGraph</a> is strongly connected
--   
--   A directed graph is <tt>strongly connected</tt> if it contains a
--   directed path on every pair of vertices
isStronglyConnected :: (Hashable v, Eq v, Ord v) => DGraph v e -> Bool