-- 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.0.2.0 module Data.Graph.Types -- | 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 -- | Each vertex maps to a Links value so it can poit to other -- vertices type Links v e = HashMap v e -- | 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 -- | 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 -- | Edges generator arbitraryEdge :: (Arbitrary v, Arbitrary e, Ord v, Num v) => (v -> v -> e -> edge) -> Gen edge -- | 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 () -- | Convert an Arc to an ordered pair discarding its attribute toOrderedPair :: Arc v a -> (v, v) -- | Convert an Edge to an unordered pair discarding its attribute toUnorderedPair :: Edge v a -> (v, v) -- | 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 (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) 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) module Data.Graph.Graph -- | Undirected Graph of Vertices in v and Edges with attributes in -- e newtype Graph v e Graph :: HashMap v (Links v e) -> Graph v e [unGraph] :: Graph v e -> HashMap v (Links v e) -- | Probability value between 0 and 1 newtype Probability P :: Float -> Probability -- | Construct a Probability value probability :: Float -> Probability -- | Generate a random Graph of the Erdős–Rényi G(n, p) model erdosRenyiIO :: Int -> Probability -> IO (Graph Int ()) randomMatIO :: Int -> IO [[Int]] -- | The Empty (order-zero) Graph with no vertices and no edges empty :: (Hashable v) => Graph v e -- | O(log n) Insert a vertex into a Graph | If the graph -- already contains the vertex leave the graph untouched insertVertex :: (Hashable v, Eq v) => v -> Graph v e -> Graph v e -- | O(n) Remove a vertex from a Graph if present | Every -- Edge incident to this vertex is also removed removeVertex :: (Hashable v, Eq v) => v -> Graph v e -> Graph v e -- | O(m*log n) Insert a many vertices into a Graph | New -- vertices are inserted and already contained vertices are left -- untouched insertVertices :: (Hashable v, Eq v) => [v] -> Graph v e -> Graph v e -- | O(log n) Insert an undirected Edge into a Graph -- | 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 -> Graph v e -> Graph v e -- | O(m*log n) Insert many directed Edges into a -- Graph | Same rules as insertEdge are applied insertEdges :: (Hashable v, Eq v) => [Edge v e] -> Graph v e -> Graph v e -- | O(log n) Remove the undirected Edge from a -- Graph if present | The involved vertices are left untouched removeEdge :: (Hashable v, Eq v) => Edge v e -> Graph v e -> Graph v e -- | Same as removeEdge but the edge is an unordered pair removeEdge' :: (Hashable v, Eq v) => (v, v) -> Graph v e -> Graph v e -- | O(log n) Remove the undirected Edge from a -- Graph if present | The involved vertices are also removed removeEdgeAndVertices :: (Hashable v, Eq v) => Edge v e -> Graph v e -> Graph v e -- | Same as removeEdgeAndVertices but the edge is an unordered pair removeEdgeAndVertices' :: (Hashable v, Eq v) => (v, v) -> Graph v e -> Graph v e -- | O(n) Retrieve the vertices of a Graph vertices :: Graph v e -> [v] -- | O(n) Retrieve the order of a Graph | The -- order of a graph is its number of vertices order :: Graph v e -> Int -- | O(n*m) Retrieve the size of a Graph | The -- size of an undirected graph is its number of Edges size :: (Hashable v, Eq v) => Graph v e -> Int -- | O(n*m) Retrieve the Edges of a Graph edges :: forall v e. (Hashable v, Eq v) => Graph v e -> [Edge v e] -- | Same as edges but the edges are unordered pairs, and their -- attributes | are discarded edges' :: (Hashable v, Eq v) => Graph v e -> [(v, v)] -- | O(log n) Tell if a vertex exists in the graph containsVertex :: (Hashable v, Eq v) => Graph v e -> v -> Bool -- | O(log n) Tell if an undirected Edge exists in the -- graph containsEdge :: (Hashable v, Eq v) => Graph v e -> Edge v e -> Bool -- | Same as containsEdge but the edge is an unordered pair containsEdge' :: (Hashable v, Eq v) => Graph v e -> (v, v) -> Bool -- | Retrieve the adjacent vertices of a vertex adjacentVertices :: (Hashable v, Eq v) => Graph v e -> v -> [v] -- | Retrieve the incident Edges of a Vertex incidentEdges :: (Hashable v, Eq v) => Graph v e -> v -> [Edge v e] -- | Degree of a vertex | The total number incident Edges of a -- vertex vertexDegree :: (Hashable v, Eq v) => Graph v e -> v -> Int -- | Degrees of a all the vertices in a Graph degrees :: (Hashable v, Eq v) => Graph v e -> [Int] -- | Maximum degree of a Graph maxDegree :: (Hashable v, Eq v) => Graph v e -> Int -- | Minimum degree of a Graph minDegree :: (Hashable v, Eq v) => Graph v e -> Int -- | Tell if an Edge forms a loop | An Edge forms a loop with -- both of its ends point to the same vertex isLoop :: (Eq v) => Edge v e -> Bool -- | Tell if a Graph is simple | A Graph is simple -- if it has no multiple edges nor loops isSimple :: (Hashable v, Eq v) => Graph v e -> Bool -- | Tell if a Graph is regular | An Undirected Graph is -- regular when all of its vertices have the same | number of -- adjacent vertices isRegular :: Graph v e -> Bool -- | Tell if two Graphs are isomorphic areIsomorphic :: Graph v e -> Graph v' e' -> Bool isomorphism :: Graph v e -> Graph v' e' -> (v -> v') -- | Generate a directed Graph of Int vertices from an adjacency | -- square matrix fromAdjacencyMatrix :: [[Int]] -> Maybe (Graph Int ()) -- | Get the adjacency matrix representation of a directed Graph toAdjacencyMatrix :: Graph v e -> [[Int]] -- | The Degree Sequence of a simple Graph 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 Graph | If the graph -- is not simple (see isSimple) the result is Nothing getDegreeSequence :: (Hashable v, Eq v) => Graph v e -> Maybe DegreeSequence -- | Tell if a DegreeSequence is a Graphical Sequence | A Degree -- Sequence is a Graphical Sequence if a corresponding -- Graph for | it exists isGraphicalSequence :: DegreeSequence -> Bool -- | Get the corresponding Graph of a DegreeSequence | If the -- DegreeSequence is not graphical (see -- isGraphicalSequence) the | result is Nothing fromGraphicalSequence :: DegreeSequence -> Maybe (Graph Int ()) instance GHC.Show.Show Data.Graph.Graph.DegreeSequence instance GHC.Classes.Ord Data.Graph.Graph.DegreeSequence instance GHC.Classes.Eq Data.Graph.Graph.DegreeSequence instance GHC.Show.Show Data.Graph.Graph.Probability instance GHC.Classes.Ord Data.Graph.Graph.Probability instance GHC.Classes.Eq Data.Graph.Graph.Probability instance (GHC.Show.Show e, GHC.Show.Show v) => GHC.Show.Show (Data.Graph.Graph.Graph v e) instance (GHC.Classes.Eq e, GHC.Classes.Eq v) => GHC.Classes.Eq (Data.Graph.Graph.Graph 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.Graph.Graph v e) module Data.Graph.Visualize -- | Plot an undirected Graph to a PNG image file plotIO :: (Show e) => Graph Int e -> FilePath -> IO FilePath -- | Same as plotIO but open the resulting image with -- xdg-open plotXdgIO :: (Show e) => Graph Int e -> FilePath -> IO () 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)] -- | The Empty (order-zero) DGraph with no vertices and no arcs empty :: (Hashable v) => DGraph v e -- | O(log n) Insert a vertex into a DGraph | If the graph -- already contains the vertex leave the graph untouched insertVertex :: (Hashable v, Eq v) => v -> DGraph v e -> DGraph v e -- | 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(m*log n) Insert a many vertices into a DGraph | New -- vertices are inserted and already contained vertices are left -- untouched insertVertices :: (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) => Arc v e -> DGraph v e -> DGraph v e -- | Same as removeArc but the arc is an ordered pair removeArc' :: (Hashable v, Eq v) => (v, v) -> DGraph v e -> 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) => Arc v e -> DGraph v e -> DGraph v e -- | Same as removeArcAndVertices but the arc is an ordered pair removeArcAndVertices' :: (Hashable v, Eq v) => (v, v) -> DGraph v e -> DGraph v e -- | O(n) Retrieve the vertices of a DGraph vertices :: DGraph v e -> [v] -- | O(n) Retrieve the order of a DGraph | The -- order of a graph is its number of vertices order :: DGraph v e -> Int -- | O(n*m) Retrieve the size of a DGraph | The -- size of a directed graph is its number of Arcs size :: (Hashable v, Eq v) => DGraph v e -> Int -- | 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 vertex exists in the graph containsVertex :: (Hashable v, Eq v) => DGraph v e -> v -> Bool -- | 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] -- | Retrieve the adjacent vertices of a vertex adjacentVertices :: DGraph v e -> v -> [v] -- | 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 -- | Tell if a DGraph is isolated | A graph is isolated if -- it has no edges, that is, it has a degree of 0 | TODO: What if it has -- a loop? isIsolated :: DGraph v e -> Bool -- | Degree of a vertex | The total number of inbounding and outbounding -- Arcs of a vertex vertexDegree :: DGraph v e -> v -> Int -- | 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 -- | 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 (Test.QuickCheck.Arbitrary.Arbitrary v, Test.QuickCheck.Arbitrary.Arbitrary e, Data.Hashable.Class.Hashable v, GHC.Num.Num v, GHC.Classes.Ord v) => Test.QuickCheck.Arbitrary.Arbitrary (Data.Graph.DGraph.DGraph v e) -- | For Connectivity analisis purposes a DGraph can be converted -- into a | Graph using toUndirected module Data.Graph.Connectivity -- | Tell if a Graph is connected | An Undirected Graph is -- connected when there is a path between every pair | of -- vertices isConnected :: Graph v e -> Bool -- | Tell if a Graph is disconnected | An Undirected Graph is -- disconnected when its not connected. See | -- isConnected TODO: An edgeles graph with two or more vertices is -- disconnected isDisconnected :: Graph v e -> Bool -- | Tell if two vertices of a Graph are connected | Two vertices -- are connected if it exists a path between them areConnected :: Graph v e -> v -> v -> Bool -- | Tell if two vertices of a Graph are disconnected | Two vertices -- are disconnected if it doesn't exist a path between them areDisconnected :: Graph v e -> v -> v -> Bool -- | Retrieve all the unreachable vertices of a Graph | The -- unreachable vertices are those with no adjacent -- Edges unreachableVertices :: Graph v e -> [v] -- | Tell if a DGraph is weakly connected | A Directed Graph is -- weakly connected if the equivalent undirected graph | is -- connected isWeaklyConnected :: DGraph v e -> Bool