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

module Data.Graph.Types
class Graph g where size = length . edgePairs edgePairs g = tripleToPair <$> edgeTriples g adjacentVertices g v = fst <$> adjacentVertices' g v reachableAdjacentVertices g v = fst <$> reachableAdjacentVertices' g v 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 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

-- | 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
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 pairs the vertex with the
--   connecting | edge's attribute
adjacentVertices' :: (Graph g, Hashable v, Eq v) => g v e -> 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 pairs the vertex with the
--   | connecting edge's attribute
reachableAdjacentVertices' :: (Graph g, Hashable v, Eq v) => g v e -> 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

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

-- | 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
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 |
--   attributeless 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 is also 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 multple 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 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
--   loops
isSimple :: (Graph g, Hashable v, Eq v) => 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)

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

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

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

-- | 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 :: [(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.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.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>
data UGraph v e
UGraph :: Int -> HashMap v (Links v e) -> UGraph v e
[_size] :: UGraph v e -> Int
[unUGraph] :: UGraph v e -> HashMap v (Links 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 is 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 are also 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 | Same as
--   <a>edges</a>
toList :: (Hashable v, Eq v) => UGraph v e -> [Edge v e]

-- | Construct a <a>UGraph</a> from a list of <a>Edge</a>s
fromList :: (Hashable v, Eq v) => [Edge v e] -> UGraph v e
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 (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
--   vertices | in a graph | Use <a>degreeSequence</a> to construct a valid
--   Degree Sequence
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. | Use 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 wich 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.Read

-- | Read a <tt>UGraph</tt> from a CSV file | The line "1,2,3,4" translates
--   to the list of edges | "(1 <a>-</a> 2), (1 <a>-</a> 3), (1 <a>-</a>
--   4)"
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.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
DGraph :: Int -> HashMap v (Links v e) -> DGraph v e
[_size] :: DGraph v e -> Int
[unDGraph] :: DGraph v e -> HashMap v (Links 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 is 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 are also 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 | 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

-- | Indegree of a vertex | 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 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 <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 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 a <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 | Same as <a>arcs</a>
toList :: (Hashable v, Eq v) => DGraph v e -> [Arc v e]

-- | Construct a <a>DGraph</a> from a list of <a>Arc</a>s
fromList :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e
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 (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 of <i>n</i> vertices
--   with a | <i>p</i> connection probability
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 square binary matrix | Useful for use with
--   <a>fromAdjacencyMatrix</a>
randomMat :: 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 indigree and | |
--   outdegree
isDRegular :: DGraph v e -> Bool

module Data.Graph.Visualize

-- | Plot an undirected <a>UGraph</a>
plotUGraph :: (Show e) => UGraph Int e -> IO ()

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

-- | Plot a directed <a>DGraph</a>
plotDGraph :: (Show e) => DGraph Int e -> IO ()

-- | Plot a directed <a>DGraph</a> to a PNG image file
plotDGraphPng :: (Show e) => DGraph Int e -> FilePath -> IO FilePath


-- | For Connectivity analisis 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

-- | 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 :: (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 incidet 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
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
isBridgeless :: (Hashable v, Eq v, Ord v) => UGraph v e -> Bool

-- | Tell if a <a>UGraph</a> is orietable | An undirected graph is
--   <tt>orietable</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