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

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

-- | 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 :: g v e -&gt; [[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 ()

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

-- | Edge attributes that represent labels
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 v, GHC.Classes.Ord e) => GHC.Classes.Ord (Data.Graph.Types.Arc v e)
instance (GHC.Read.Read v, GHC.Read.Read e) => GHC.Read.Read (Data.Graph.Types.Arc v e)
instance (GHC.Show.Show v, GHC.Show.Show e) => GHC.Show.Show (Data.Graph.Types.Arc v e)
instance GHC.Generics.Generic (Data.Graph.Types.Edge v e)
instance (GHC.Classes.Ord v, GHC.Classes.Ord e) => GHC.Classes.Ord (Data.Graph.Types.Edge v e)
instance (GHC.Read.Read v, GHC.Read.Read e) => GHC.Read.Read (Data.Graph.Types.Edge v e)
instance (GHC.Show.Show v, GHC.Show.Show e) => GHC.Show.Show (Data.Graph.Types.Edge v e)
instance Data.Graph.Types.Labeled GHC.Base.String
instance Data.Graph.Types.Labeled (GHC.Types.Double, GHC.Base.String)
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.Weighted (GHC.Types.Double, GHC.Base.String)
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.Arc
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.Arc v)
instance (GHC.Classes.Eq v, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Graph.Types.Arc v a)
instance (Control.DeepSeq.NFData v, Control.DeepSeq.NFData e) => Control.DeepSeq.NFData (Data.Graph.Types.Edge v e)
instance Data.Graph.Types.IsEdge Data.Graph.Types.Edge
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 GHC.Base.Functor (Data.Graph.Types.Edge v)
instance (GHC.Classes.Eq v, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Graph.Types.Edge 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 v, GHC.Classes.Eq e) => 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) => GHC.Base.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.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 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 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 v, GHC.Classes.Eq e) => 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) => GHC.Base.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.Morphisms

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 for all the vertices of type <i>v</i> in the
--   list, 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, Random e) => (e, e) -> Float -> [v] -> IO (g v e)

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

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


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

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> holds the Handshaking lemma, that is,
--   if the number of vertices with odd degree is even
holdsHandshakingLemma :: DegreeSequence -> Bool
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.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