-- 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.3.0.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 order of a graph is its -- number of vertices order :: Graph g => g v e -> Int -- | Retrieve the size of a graph | The size 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 -- | 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] -- | Retrieve the vertices that are directly reachable from a particular | -- vertex. | A vertex is directly reachable to other if there is -- an edge that | connects from one vertex to the other -- | Every vertex is directly reachable from itself directlyReachableVertices :: (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) => g v e -> v -> 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) => g v e -> [v] -> 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) => g v () -> (v, v) -> g v () -- | Remove the edge from a graph present | The involved vertices are left -- untouched removeEdgePair :: (Graph g, Hashable v, Eq v) => g v e -> (v, v) -> g v e -- | Remove the edge from a graph if present | The involved vertices are -- also removed removeEdgePairAndVertices :: (Graph g, Hashable v, Eq v) => g v e -> (v, v) -> g v e -- | Tell if a graph is simple | A graph is simple 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 regular 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 e between to Vertices of -- type v data Edge v e Edge :: v -> v -> e -> Edge v e -- | Directed Arc with attribute of type e between to Vertices of -- type v data Arc v e Arc :: v -> v -> e -> Arc v e -- | Construct an undirected Edge between two vertices (<->) :: (Hashable v) => v -> v -> Edge v () -- | Construct a directed Arc 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 loop 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 Edges are equal if they point to the same vertices, -- regardless of the | direction -- | To Arcs 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 Links 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 Arcs from an association list of vertices and their links linksToArcs :: [(v, Links v a)] -> [Arc v a] -- | Get Edges 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 v and Edges with attributes in -- e newtype UGraph v e UGraph :: HashMap v (Links v e) -> UGraph v e [unUGraph] :: UGraph v e -> HashMap v (Links v e) -- | O(n) Remove a vertex from a UGraph if present | Every -- Edge incident to this vertex is also removed removeVertex :: (Hashable v, Eq v) => v -> UGraph v e -> UGraph v e -- | O(log n) Insert an undirected Edge into a -- UGraph | 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 -- | O(m*log n) Insert many directed Edges into a -- UGraph | Same rules as insertEdge are applied insertEdges :: (Hashable v, Eq v) => [Edge v e] -> UGraph v e -> UGraph v e -- | O(log n) Remove the undirected Edge from a -- UGraph if present | The involved vertices are left untouched removeEdge :: (Hashable v, Eq v) => UGraph v e -> Edge v e -> UGraph v e -- | Same as removeEdge but the edge is an unordered pair removeEdge' :: (Hashable v, Eq v) => UGraph v e -> (v, v) -> UGraph v e -- | O(log n) Remove the undirected Edge from a -- UGraph if present | The involved vertices are also removed removeEdgeAndVertices :: (Hashable v, Eq v) => UGraph v e -> Edge v e -> UGraph v e -- | Same as removeEdgeAndVertices but the edge is an unordered pair removeEdgeAndVertices' :: (Hashable v, Eq v) => UGraph v e -> (v, v) -> UGraph v e -- | O(n*m) Retrieve the Edges of a UGraph edges :: forall v e. (Hashable v, Eq v) => UGraph v e -> [Edge v e] -- | O(log n) Tell if an undirected Edge exists in the -- graph containsEdge :: (Hashable v, Eq v) => UGraph v e -> Edge v e -> Bool -- | Same as containsEdge but the edge is an unordered pair containsEdge' :: (Hashable v, Eq v) => UGraph v e -> (v, v) -> Bool -- | Retrieve the incident Edges of a Vertex incidentEdges :: (Hashable v, Eq v) => UGraph v e -> v -> [Edge v e] -- | Tell if two UGraph 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 UGraph is a list of degrees newtype DegreeSequence DegreeSequence :: [Int] -> DegreeSequence [unDegreeSequence] :: DegreeSequence -> [Int] -- | Construct a DegreeSequence from a list of degrees | Negative -- degree values are discarded degreeSequence :: [Int] -> DegreeSequence -- | Get the DegreeSequence of a simple UGraph | If the graph -- is not simple (see isSimple) the result is Nothing getDegreeSequence :: (Hashable v, Eq v) => UGraph v e -> Maybe DegreeSequence -- | Tell if a DegreeSequence is a Graphical Sequence | A Degree -- Sequence is a Graphical Sequence if a corresponding -- UGraph for | it exists isGraphicalSequence :: DegreeSequence -> Bool -- | Get the corresponding UGraph of a DegreeSequence | If -- the DegreeSequence is not graphical (see -- isGraphicalSequence) 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.Generation -- | Probability value between 0 and 1 newtype Probability P :: Float -> Probability -- | Construct a Probability 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 -- fromAdjacencyMatrix 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 v and Arcs with attributes in -- e 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 DGraph is a list of pairs (Indegree, -- Outdegree) type DegreeSequence = [(Int, Int)] -- | O(n) Remove a vertex from a DGraph if present | Every -- Arc incident to this vertex is also removed removeVertex :: (Hashable v, Eq v) => v -> DGraph v e -> DGraph v e -- | O(log n) Insert a directed Arc into a DGraph | -- 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 -- | O(m*log n) Insert many directed Arcs into a -- DGraph | Same rules as insertArc are applied insertArcs :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e -> DGraph v e -- | O(log n) Remove the directed Arc from a DGraph -- if present | The involved vertices are left untouched removeArc :: (Hashable v, Eq v) => DGraph v e -> Arc v e -> DGraph v e -- | Same as removeArc but the arc is an ordered pair removeArc' :: (Hashable v, Eq v) => DGraph v e -> (v, v) -> DGraph v e -- | O(log n) Remove the directed Arc from a DGraph -- if present | The involved vertices are also removed removeArcAndVertices :: (Hashable v, Eq v) => DGraph v e -> Arc v e -> DGraph v e -- | Same as removeArcAndVertices but the arc is an ordered pair removeArcAndVertices' :: (Hashable v, Eq v) => DGraph v e -> (v, v) -> DGraph v e -- | O(n*m) Retrieve the Arcs of a DGraph arcs :: forall v e. (Hashable v, Eq v) => DGraph v e -> [Arc v e] -- | Same as arcs but the arcs are ordered pairs, and their -- attributes are | discarded arcs' :: (Hashable v, Eq v) => DGraph v e -> [(v, v)] -- | O(log n) Tell if a directed Arc exists in the graph containsArc :: (Hashable v, Eq v) => DGraph v e -> Arc v e -> Bool -- | Same as containsArc but the arc is an ordered pair containsArc' :: (Hashable v, Eq v) => DGraph v e -> (v, v) -> Bool -- | Retrieve the inbounding Arcs of a Vertex inboundingArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e] -- | Retrieve the outbounding Arcs of a Vertex outboundingArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e] -- | Retrieve the incident Arcs of a Vertex | Both inbounding and -- outbounding arcs incidentArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e] -- | Tell if a DGraph is symmetric | All of its Arcs are -- bidirected isSymmetric :: DGraph v e -> Bool -- | Tell if a DGraph is oriented | There are none bidirected -- Arcs | Note: This is not the opposite of -- isSymmetric isOriented :: DGraph v e -> Bool -- | Indegree of a vertex | The number of inbounding Arcs to a -- vertex vertexIndegree :: DGraph v e -> v -> Int -- | Outdegree of a vertex | The number of outbounding Arcs from a -- vertex vertexOutdegree :: DGraph v e -> v -> Int -- | Indegrees of all the vertices in a DGraph indegrees :: DGraph v e -> [Int] -- | Outdegree of all the vertices in a DGraph outdegrees :: DGraph v e -> [Int] -- | Tell if a DGraph is balanced | A Directed Graph is -- balanced when its indegree = outdegree isBalanced :: DGraph v e -> Bool -- | Tell if a DGraph is regular | A Directed Graph is -- regular when all of its vertices have the same number | of -- adjacent vertices AND when the indegree and -- outdegree of each vertex | are equal to each toher. isRegular :: DGraph v e -> Bool -- | Tell if a vertex is a source | A vertex is a source when its -- indegree = 0 isSource :: DGraph v e -> v -> Bool -- | Tell if a vertex is a sink | A vertex is a sink when its -- outdegree = 0 isSink :: DGraph v e -> v -> Bool -- | Tell if a vertex is internal | A vertex is a internal when -- its neither a source nor a sink isInternal :: DGraph v e -> v -> Bool -- | Convert a directed DGraph to an undirected UGraph by -- converting all of | its Arcs into Edges toUndirected :: (Hashable v, Eq v) => DGraph v e -> UGraph v e -- | Tell if a DegreeSequence is a Directed Graphic | A Directed -- Graphic is a Degree Sequence for wich a DGraph 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) module Data.Graph.Visualize -- | Plot an undirected UGraph to a PNG image file plotUndirectedIO :: (Show e) => UGraph Int e -> FilePath -> IO FilePath -- | Same as plotUndirectedIO but open the resulting image with -- xdg-open plotUndirectedXdgIO :: (Show e) => UGraph Int e -> FilePath -> IO () -- | Plot a directed DGraph to a PNG image file plotDirectedIO :: (Show e) => DGraph Int e -> FilePath -> IO FilePath -- | Same as plotDirectedIO but open the resulting image with -- xdg-open plotDirectedXdgIO :: (Show e) => DGraph Int e -> FilePath -> IO () -- | For Connectivity analisis purposes a DGraph can be converted -- into a | UGraph using toUndirected module Data.Graph.Connectivity -- | Tell if two vertices of a graph are connected | Two vertices are -- connected 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 UGraph are disconnected | Two -- vertices are disconnected 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 isolated 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 -- connected when there is a path between every pair | of -- vertices isConnected :: (Hashable v, Eq v) => UGraph v e -> Bool -- | Tell if a DGraph is weakly connected | A Directed Graph is -- weakly connected if the underlying undirected graph | is -- connected isWeaklyConnected :: (Hashable v, Eq v) => DGraph v e -> Bool -- | Tell if a DGraph is strongly connected | A Directed Graph is -- strongly connected if it contains a directed path | on every -- pair of vertices isStronglyConnected :: (Hashable v, Eq v, Ord v) => DGraph v e -> Bool