-- | Haskell bindings to the igraph C library. -- -- Function descriptions have been copied from -- from the specified sections. -- module Data.IGraph ( -- * Basic types Graph (..), E (isDirected, isWeighted, edgeFrom, edgeTo, edgeWeight), Edge , D, U, IsUnweighted , Weighted, toEdgeWeighted, getWeight , IsUndirected, ToDirected , IsDirected, ToUndirected -- * Pure Haskell functions -- | These functions do not depend on the C library and perform no FFI calls. -- ** Construction / modification , emptyGraph , fromList, fromListWeighted , insertEdge , deleteEdge , deleteNode , reverseGraphDirection , toDirected, toUndirected -- ** Query , numberOfNodes , numberOfEdges , member , nodes , edges , neighbours -- * Chapter 11. Vertex and Edge Selectors and Sequences, Iterators -- ** 11\.2 Vertex selector constructors , VertexSelector(..) --, NeiMode(..) -- ** 11\.3 Generic vertex selector operations , vsSize, selectedVertices -- ** 11\.6 Edge selector constructors , EdgeSelector(..) -- ** 11\.8 Generic edge selector operations , esSize, selectedEdges -- * Chapter 13\. Structural Properties of Graphs -- ** 13\.1 Basic properties , areConnected -- ** 13\.2 Shortest Path Related Functions , shortestPaths, shortestPathsDijkstra, shortestPathsBellmanFord, shortestPathsJohnson , getShortestPaths, getShortestPathsDijkstra , getShortestPath, getShortestPathDijkstra , getAllShortestPaths, getAllShortestPathsDijkstra , averagePathLength , pathLengthHist , diameter, diameterDijkstra , girth , eccentricity , radius -- ** 13\.4 Graph Components -- | Note that there currently is an issue with GHCi and shared libraries on -- x86_64 linux systems which will cause an error in those functions that -- return graphs (e.g. 'inducedSubgraph'). See GHC Ticket #781 -- (). Statically compiling -- your program or installing this module (and all it's dependencies) with -- @-fPIC@ should fix this issue. , subcomponent , inducedSubgraph, SubgraphImplementation(..) , subgraphEdges --, subgraph , clusters , isConnected , decompose , Connectedness(..) , biconnectedComponents , articulationPoints -- ** 13\.5 Centrality Measures , closeness , betweenness, edgeBetweenness , pagerank , personalizedPagerank , personalizedPagerankVs , constraint , maxdegree , strength , eigenvectorCentrality , hubScore , authorityScore -- ** 13\.6 Estimating Centrality Measures , closenessEstimate , betweennessEstimate , edgeBetweennessEstimate -- ** 13\.7 Centralization , centralizationDegree , centralizationBetweenness , centralizationCloseness , centralizationEigenvectorCentrality , centralizationDegreeTMax , centralizationBetweennessTMax , centralizationClosenessTMax , centralizationEigenvectorCentralityTMax -- ** 13\.8 Similarity Measures , bibCoupling , cocitation , similarityJaccard , similarityJaccardPairs , similarityJaccardEs , similarityDice , similarityDicePairs , similarityDiceEs , similarityInverseLogWeighted -- ** 13\.9 Spanning Tress , minimumSpanningTree , minimumSpanningTreeUnweighted , minimumSpanningTreePrim -- ** 13\.10 Transitivity or Clustering Coefficient , transitivityUndirected , transitivityLocalUndirected , transitivityAvglocalUndirected , transitivityBarrat -- ** 13\.12 Spectral properties , laplacian -- ** 13\.14 Mixing patterns , assortativityNominal , assortativity , assortativityDegree -- ** 13\.15 K-Cores , coreness -- ** 13\.16 Topological sorting, directed acyclic graphs , isDAG , topologicalSorting , FASAlgorithm(..) , feedbackArcSet -- ** 13\.17 Maximum cardinality search, graph decomposition, chordal graphs , maximumCardinalitySearch , isChordal ) where import Data.IGraph.Internal import Data.IGraph.Internal.Constants import Data.IGraph.Types import Data.Hashable import Data.Map (Map) import qualified Data.Map as M import qualified Data.Foldable as F import Data.List (nub) import Foreign hiding (unsafePerformIO) import Foreign.C import System.IO.Unsafe (unsafePerformIO) -------------------------------------------------------------------------------- -- 11.2 Vertex selector constructors {- nothing here -} -------------------------------------------------------------------------------- -- 11.3. Generic vertex selector operations foreign import ccall "igraph_vs_size" c_igraph_vs_size :: GraphPtr -> VsPtr -> Ptr CInt -> IO CInt -- | 3\.4\. `igraph_vs_size` — Returns the size of the vertex selector. vsSize :: Graph d a -> VertexSelector a -> Int vsSize g vs = unsafePerformIO $ alloca $ \ip -> do _e <- withGraph g $ \gp -> withVs vs g $ \vsp -> c_igraph_vs_size gp vsp ip fromIntegral `fmap` peek ip foreign import ccall "selected_vertices" c_selected_vertices :: GraphPtr -> VsPtr -> VectorPtr -> IO Int selectedVertices :: Graph d a -> VertexSelector a -> [a] selectedVertices g vs = unsafePerformIO $ do let s = vsSize g vs v <- newVector s _ <- withGraph g $ \gp -> withVs vs g $ \vsp -> withVector v $ \vp -> c_selected_vertices gp vsp vp l <- vectorToList v return (map (idToNode'' g . round) l) -------------------------------------------------------------------------------- -- 11.8. Generic edge selector operations foreign import ccall "igraph_es_size" c_igraph_es_size :: GraphPtr -> EsPtr -> Ptr CInt -> IO CInt -- | 8\.4\. `igraph_es_size` — Returns the size of the edge selector. esSize :: Graph d a -> EdgeSelector d a -> Int esSize g es = unsafePerformIO $ alloca $ \ip -> do _e <- withGraph g $ \gp -> withEs es g $ \esp -> c_igraph_es_size gp esp ip fromIntegral `fmap` peek ip foreign import ccall "selected_edges" c_selected_edges :: GraphPtr -> EsPtr -> VectorPtr -> IO CInt selectedEdges :: Graph d a -> EdgeSelector d a -> [Edge d a] selectedEdges g es = unsafePerformIO $ do let s = esSize g es v <- newVector s _e <- withGraph g $ \gp -> withEs es g $ \esp -> withVector v $ \vp -> c_selected_edges gp esp vp l <- vectorToList v return $ map (edgeIdToEdge g . round) l -------------------------------------------------------------------------------- -- 13.1 Basic properties foreign import ccall "igraph_are_connected" c_igraph_are_connected :: GraphPtr -> CInt -> CInt -> Ptr CInt -> IO CInt -- | 1\.1\. `igraph_are_connected` — Decides whether two vertices are connected areConnected :: Graph d a -> a -> a -> Bool areConnected g n1 n2 = case (nodeToId g n1, nodeToId g n2) of (Just i1, Just i2) -> unsafePerformIO $ withGraph g $ \gp -> alloca $ \bp -> do _ <- c_igraph_are_connected gp (fromIntegral i1) (fromIntegral i2) bp fmap (== 1) (peek bp) _ -> False -------------------------------------------------------------------------------- -- 13.2 Shortest Path Related Functions foreign import ccall "shortest_paths" c_igraph_shortest_paths :: GraphPtr -> MatrixPtr -> VsPtr -> VsPtr -> CInt -> IO CInt -- | 2\.1\. `igraph_shortest_paths` — The length of the shortest paths between -- vertices. shortestPaths :: (Ord a, Hashable a) => Graph d a -> VertexSelector a -> VertexSelector a -> Map (a,a) (Maybe Int) shortestPaths g vf vt = let ls = unsafePerformIO $ do ma <- newMatrix 0 0 _e <- withGraph g $ \gp -> withMatrix ma $ \mp -> withVs vf g $ \vfp -> withVs vt g $ \vtp -> c_igraph_shortest_paths gp mp vfp vtp (getNeiMode g) matrixToList ma nf = selectedVertices g vf nt = selectedVertices g vt in M.fromList [ ((f,t), len) | (f,lf) <- zip nf ls , (t,len) <- zip nt (map roundMaybe lf) ] roundMaybe :: Double -> Maybe Int roundMaybe d = if d == 1/0 then Nothing else Just (round d) foreign import ccall "shortest_paths_dijkstra" c_igraph_shortest_paths_dijkstra :: GraphPtr -> MatrixPtr -> VsPtr -> VsPtr -> VectorPtr -> CInt -> IO CInt -- | 2\.2\. `igraph_shortest_paths_dijkstra` — Weighted shortest paths from some -- sources. -- -- This function is Dijkstra's algorithm to find the weighted shortest paths to -- all vertices from a single source. (It is run independently for the given -- sources.) It uses a binary heap for efficient implementation. shortestPathsDijkstra :: (Ord a, Hashable a) => Graph (Weighted d) a -> VertexSelector a -> VertexSelector a -> Map (a,a) (Maybe Int) shortestPathsDijkstra g vf vt = let ls = unsafePerformIO $ do ma <- newMatrix 0 0 _e <- withGraph g $ \gp -> withWeights g $ \wp -> withMatrix ma $ \mp -> withVs vf g $ \vfp -> withVs vt g $ \vtp -> c_igraph_shortest_paths_dijkstra gp mp vfp vtp wp (getNeiMode g) matrixToList ma nf = selectedVertices g vf nt = selectedVertices g vt in M.fromList [ ((f,t), len) | (f,lf) <- zip nf ls , (t,len) <- zip nt (map roundMaybe lf) ] foreign import ccall "shortest_paths_bellman_ford" c_igraph_shortest_paths_bellman_ford :: GraphPtr -> MatrixPtr -> VsPtr -> VsPtr -> VectorPtr -> CInt -> IO CInt -- | 2\.3\. `igraph_shortest_paths_bellman_ford` — Weighted shortest paths from some -- sources allowing negative weights. -- -- This function is the Bellman-Ford algorithm to find the weighted shortest -- paths to all vertices from a single source. (It is run independently for the -- given sources.). If there are no negative weights, you are better off with -- igraph_shortest_paths_dijkstra() . shortestPathsBellmanFord :: (Ord a, Hashable a) => Graph (Weighted d) a -> VertexSelector a -> VertexSelector a -> Map (a,a) (Maybe Int) shortestPathsBellmanFord g vf vt = let ls = unsafePerformIO $ do ma <- newMatrix 0 0 _e <- withGraph g $ \gp -> withWeights g $ \wp -> withMatrix ma $ \mp -> withVs vf g $ \vfp -> withVs vt g $ \vtp -> c_igraph_shortest_paths_bellman_ford gp mp vfp vtp wp (getNeiMode g) matrixToList ma nf = selectedVertices g vf nt = selectedVertices g vt in M.fromList [ ((f,t), len) | (f,lf) <- zip nf ls , (t,len) <- zip nt (map roundMaybe lf) ] foreign import ccall "shortest_paths_johnson" c_igraph_shortest_paths_johnson :: GraphPtr -> MatrixPtr -> VsPtr -> VsPtr -> VectorPtr -> IO CInt -- | 2\.4\. `igraph_shortest_paths_johnson` — Calculate shortest paths from some -- sources using Johnson's algorithm. -- -- See Wikipedia at http://en.wikipedia.org/wiki/Johnson's_algorithm for -- Johnson's algorithm. This algorithm works even if the graph contains negative -- edge weights, and it is worth using it if we calculate the shortest paths -- from many sources. -- -- If no edge weights are supplied, then the unweighted version, -- igraph_shortest_paths() is called. -- -- If all the supplied edge weights are non-negative, then Dijkstra's algorithm -- is used by calling igraph_shortest_paths_dijkstra(). shortestPathsJohnson :: (Ord a, Hashable a) => Graph (Weighted d) a -> VertexSelector a -> VertexSelector a -> Map (a,a) (Maybe Int) shortestPathsJohnson g vf vt = let ls = unsafePerformIO $ do ma <- newMatrix 0 0 _e <- withGraph g $ \gp -> withWeights g $ \wp -> withMatrix ma $ \mp -> withVs vf g $ \vfp -> withVs vt g $ \vtp -> c_igraph_shortest_paths_johnson gp mp vfp vtp wp matrixToList ma nf = selectedVertices g vf nt = selectedVertices g vt in M.fromList [ ((f,t), len) | (f,lf) <- zip nf ls , (t,len) <- zip nt (map roundMaybe lf) ] foreign import ccall "get_shortest_paths" c_igraph_get_shortest_paths :: GraphPtr -> VectorPtrPtr -> VectorPtrPtr -> CInt -> VsPtr -> CInt -> IO CInt -- | 2\.5\. `igraph_get_shortest_paths` — Calculates the shortest paths from/to one -- vertex. -- -- If there is more than one geodesic between two vertices, this function gives -- only one of them. getShortestPaths :: Graph d a -> a -- ^ from -> VertexSelector a -- ^ to -> [ ([a],[Edge d a]) ] -- ^ list of @(vertices, edges)@ getShortestPaths g f vt = let mfi = nodeToId g f in case mfi of Nothing -> error "getShortestPaths: Invalid node" Just fi -> unsafePerformIO $ do vpv <- newVectorPtr 0 vpe <- newVectorPtr 0 _e <- withGraph g $ \gp -> withVectorPtr vpv $ \vpvp -> withVectorPtr vpe $ \vpep -> withVs vt g $ \vtp -> c_igraph_get_shortest_paths gp vpvp vpep (fromIntegral fi) vtp (getNeiMode g) v <- vectorPtrToVertices g vpv e <- vectorPtrToEdges g vpe return $ zip v e foreign import ccall "igraph_get_shortest_path" c_igraph_get_shortest_path :: GraphPtr -> VectorPtr -> VectorPtr -> CInt -> CInt -> CInt -> IO CInt -- | 2\.6\. `igraph_get_shortest_path` — Shortest path from one vertex to another -- one. -- -- Calculates and returns a single unweighted shortest path from a given vertex -- to another one. If there are more than one shortest paths between the two -- vertices, then an arbitrary one is returned. -- -- This function is a wrapper to igraph_get_shortest_paths(), for the special -- case when only one target vertex is considered. getShortestPath :: Graph d a -> a -> a -> ([a],[Edge d a]) getShortestPath g n1 n2 = let mi1 = nodeToId g n1 mi2 = nodeToId g n2 in case (mi1, mi2) of (Just i1, Just i2) -> unsafePerformIO $ withGraph g $ \gp -> do v1 <- listToVector ([] :: [Int]) v2 <- listToVector ([] :: [Int]) e <- withVector v1 $ \vp1 -> withVector v2 $ \vp2 -> c_igraph_get_shortest_path gp vp1 vp2 (fromIntegral i1) (fromIntegral i2) (getNeiMode g) if e == 0 then do vert <- vectorToVertices g v1 edgs <- vectorToEdges g v2 return ( vert, edgs ) else error $ "getShortestPath: igraph error " ++ show e _ -> error "getShortestPath: Invalid nodes" foreign import ccall "get_shortest_paths_dijkstra" c_igraph_get_shortest_paths_dijkstra :: GraphPtr -> VectorPtrPtr -> VectorPtrPtr -> CInt -> VsPtr -> VectorPtr -> CInt -> IO CInt -- | 2\.7\. `igraph_get_shortest_paths_dijkstra` — Calculates the weighted -- shortest paths from/to one vertex. -- -- If there is more than one path with the smallest weight between two vertices, -- this function gives only one of them. getShortestPathsDijkstra :: Graph (Weighted d) a -> a -- ^ from -> VertexSelector a -- ^ to -> [ ([a],[Edge (Weighted d) a]) ] -- ^ list of @(vertices, edges)@ getShortestPathsDijkstra g f vt = let mfi = nodeToId g f in case mfi of Nothing -> error "getShortestPathsDijkstra: Invalid node" Just fi -> unsafePerformIO $ do vpv <- newVectorPtr 0 vpe <- newVectorPtr 0 _e <- withGraph g $ \gp -> withWeights g $ \wp -> withVectorPtr vpv $ \vpvp -> withVectorPtr vpe $ \vpep -> withVs vt g $ \vtp -> c_igraph_get_shortest_paths_dijkstra gp vpvp vpep (fromIntegral fi) vtp wp (getNeiMode g) v <- vectorPtrToVertices g vpv e <- vectorPtrToEdges g vpe return $ zip v e foreign import ccall "igraph_get_shortest_path_dijkstra" c_igraph_get_shortest_path_dijkstra :: GraphPtr -> VectorPtr -> VectorPtr -> CInt -> CInt -> VectorPtr -> CInt -> IO CInt -- | 2\.8\. `igraph_get_shortest_path_dijkstra` — Weighted shortest path from one -- vertex to another one. -- -- Calculates a single (positively) weighted shortest path from a single vertex -- to another one, using Dijkstra's algorithm. -- -- This function is a special case (and a wrapper) to -- igraph_get_shortest_paths_dijkstra(). getShortestPathDijkstra :: Graph (Weighted d) a -> a -> a -> ([a],[Edge (Weighted d) a]) getShortestPathDijkstra g n1 n2 = let mi1 = nodeToId g n1 mi2 = nodeToId g n2 in case (mi1, mi2) of (Just i1, Just i2) -> unsafePerformIO $ do v1 <- newVector 0 v2 <- newVector 0 e <- withGraph g $ \gp -> withWeights g $ \wp -> withVector v1 $ \vp1 -> withVector v2 $ \vp2 -> c_igraph_get_shortest_path_dijkstra gp vp1 vp2 (fromIntegral i1) (fromIntegral i2) wp (getNeiMode g) if e == 0 then do vert <- vectorToVertices g v1 edgs <- vectorToEdges g v2 return ( vert, edgs ) else error $ "getShortestPathDijkstra: igraph error " ++ show e _ -> error "getShortestPathDijkstra: Invalid nodes" foreign import ccall "get_all_shortest_paths" c_igraph_get_all_shortest_paths :: GraphPtr -> VectorPtrPtr -> VectorPtr -> CInt -> VsPtr -> CInt -> IO CInt -- | 2\.9\. `igraph_get_all_shortest_paths` — Finds all shortest paths (geodesics) -- from a vertex to all other vertices. getAllShortestPaths :: Graph d a -> a -- ^ from -> VertexSelector a -- ^ to -> [[a]] -- ^ list of vertices along the shortest path from -- @from@ to each other (reachable) vertex getAllShortestPaths g f vt = let mfi = nodeToId g f in case mfi of Nothing -> error "getAllShortestPaths: Invalid node" Just fi -> unsafePerformIO $ do vpr <- newVectorPtr 0 _e <- withGraph g $ \gp -> withVectorPtr vpr $ \vprp -> withVs vt g $ \vtp -> c_igraph_get_all_shortest_paths gp vprp nullPtr -- NULL (fromIntegral fi) vtp (getNeiMode g) vectorPtrToVertices g vpr foreign import ccall "get_all_shortest_paths_dijkstra" c_igraph_get_all_shortest_paths_dijkstra :: GraphPtr -> VectorPtrPtr -> VectorPtr -> CInt -> VsPtr -> VectorPtr -> CInt -> IO CInt -- | 2\.10\. `igraph_get_all_shortest_paths_dijkstra` — Finds all shortest paths -- (geodesics) from a vertex to all other vertices. getAllShortestPathsDijkstra :: Graph (Weighted d) a -> a -- ^ from -> VertexSelector a -- ^ to -> [[a]] -- ^ list of vertices along the shortest path from -- @from@ to each other (reachable) vertex getAllShortestPathsDijkstra g f vt = let mfi = nodeToId g f in case mfi of Nothing -> error "getAllShortestPaths: Invalid node" Just fi -> unsafePerformIO $ do vpr <- newVectorPtr 0 _e <- withGraph g $ \gp -> withWeights g $ \wp -> withVectorPtr vpr $ \vprp -> withVs vt g $ \vtp -> c_igraph_get_all_shortest_paths_dijkstra gp vprp nullPtr -- NULL (fromIntegral fi) vtp wp (getNeiMode g) vectorPtrToVertices g vpr foreign import ccall "igraph_average_path_length" c_igraph_average_path_length :: GraphPtr -> Ptr CDouble -> Bool -> Bool -> IO CInt -- | 2\.11\. `igraph_average_path_length` — Calculates the average geodesic length -- in a graph. averagePathLength :: Graph d a -> Bool -- ^ Boolean, whether to consider directed paths. Ignored for undirected graphs. -> Bool -- ^ What to do if the graph is not connected. If -- TRUE the average of the geodesics within the -- components will be returned, otherwise the -- number of vertices is used for the length of -- non-existing geodesics. (The rationale behind -- this is that this is always longer than the -- longest possible geodesic in a graph.) -> Double averagePathLength g b1 b2 = unsafePerformIO $ do alloca $ \dp -> do _e <- withGraph g $ \gp -> c_igraph_average_path_length gp dp b1 b2 realToFrac `fmap` peek dp foreign import ccall "igraph_path_length_hist" c_igraph_path_length_hist :: GraphPtr -> VectorPtr -> Ptr CDouble -> Bool -> IO CInt -- | 2\.12\. `igraph_path_length_hist` — Create a histogram of all shortest path lengths. -- -- This function calculates a histogram, by calculating the shortest path length -- between each pair of vertices. For directed graphs both directions might be -- considered and then every pair of vertices appears twice in the histogram. pathLengthHist :: Graph d a -> Bool -- ^ Whether to consider directed paths in a directed -- graph (if not zero). This argument is ignored for -- undirected graphs. -> ([Double],Double) pathLengthHist g b = unsafePerformIO $ do v <- newVector 0 d <- alloca $ \dp -> do _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_path_length_hist gp vp dp b realToFrac `fmap` peek dp l <- vectorToList v return (l,d) foreign import ccall "igraph_diameter" c_igraph_diameter :: GraphPtr -> Ptr CInt -> Ptr CInt -> Ptr CInt -> VectorPtr -> Bool -> Bool -> IO CInt -- | 2\.13\. `igraph_diameter` — Calculates the diameter of a graph (longest -- geodesic). diameter :: Graph d a -> Bool -> Bool -> (Int, (a,a), [a]) -- ^ the diameter of the graph, the starting/end -- vertices and the longest path diameter g b1 b2 = unsafePerformIO $ do alloca $ \ip -> do alloca $ \fip -> do alloca $ \tip -> do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_diameter gp ip fip tip vp b1 b2 d <- fromIntegral `fmap` peek ip fi <- fromIntegral `fmap` peek fip ti <- fromIntegral `fmap` peek tip p <- vectorToVertices g v return (d, (idToNode'' g fi, idToNode'' g ti), p) foreign import ccall "igraph_diameter_dijkstra" c_igraph_diameter_dijkstra :: GraphPtr -> VectorPtr -> Ptr CDouble -> Ptr CInt -> Ptr CInt -> VectorPtr -> Bool -> Bool -> IO CInt -- | 2\.14\. `igraph_diameter_dijkstra` — Weighted diameter using Dijkstra's -- algorithm, non-negative weights only. -- -- The diameter of a graph is its longest geodesic. I.e. the (weighted) shortest -- path is calculated for all pairs of vertices and the longest one is the -- diameter. diameterDijkstra :: Graph d a -> (Double, a, a, [a]) -- ^ (diameter, source vertex, target vertex, path) diameterDijkstra g@(G _) = unsafePerformIO $ alloca $ \dp -> alloca $ \sp -> alloca $ \tp -> do v <- newVector 0 _e <- withGraph g $ \gp -> withOptionalWeights g $ \wp -> withVector v $ \vp -> c_igraph_diameter_dijkstra gp wp dp sp tp vp (isDirected g) True d <- peek dp s <- peek sp t <- peek tp path <- vectorToVertices g v return ( realToFrac d , idToNode'' g (fromIntegral s) , idToNode'' g (fromIntegral t) , path ) foreign import ccall "igraph_girth" c_igraph_girth :: GraphPtr -> Ptr CInt -> VectorPtr -> IO CInt -- | 2\.15\. `igraph_girth` — The girth of a graph is the length of the shortest -- circle in it. -- -- The current implementation works for undirected graphs only, directed graphs -- are treated as undirected graphs. Loop edges and multiple edges are ignored. -- -- If the graph is a forest (ie. acyclic), then zero is returned. -- -- This implementation is based on Alon Itai and Michael Rodeh: Finding a -- minimum circuit in a graph Proceedings of the ninth annual ACM symposium on -- Theory of computing , 1-10, 1977. The first implementation of this function -- was done by Keith Briggs, thanks Keith. girth :: Graph d a -> (Int, [a]) -- ^ girth with the shortest circle girth g = unsafePerformIO $ do alloca $ \ip -> do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_girth gp ip vp gr <- fromIntegral `fmap` peek ip s <- vectorToVertices g v return (gr, s) foreign import ccall "eccentricity" c_igraph_eccentricity :: GraphPtr -> VectorPtr -> VsPtr -> CInt -> IO CInt -- | 2\.16\. `igraph_eccentricity` — Eccentricity of some vertices -- -- The eccentricity of a vertex is calculated by measuring the shortest distance -- from (or to) the vertex, to (or from) all vertices in the graph, and taking -- the maximum. -- -- This implementation ignores vertex pairs that are in different components. -- Isolated vertices have eccentricity zero. eccentricity :: Graph d a -> VertexSelector a -> [(a,Int)] eccentricity g vs = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVs vs g $ \vsp -> withVector v $ \vp -> c_igraph_eccentricity gp vp vsp (getNeiMode g) l <- map round `fmap` vectorToList v return $ zip (selectedVertices g vs) l foreign import ccall "igraph_radius" c_igraph_radius :: GraphPtr -> Ptr CDouble -> CInt -> IO CInt -- | 2\.17\. `igraph_radius` — Radius of a graph -- -- The radius of a graph is the defined as the minimum eccentricity of its -- vertices, see igraph_eccentricity(). radius :: Graph d a -> Int radius g = unsafePerformIO $ do alloca $ \dp -> do _e <- withGraph g $ \gp -> c_igraph_radius gp dp (getNeiMode g) round `fmap` peek dp -------------------------------------------------------------------------------- -- 13.3 Neighborhood of a vertex {- TODO: 3.1. igraph_neighborhood_size — Calculates the size of the neighborhood of a given vertex. int igraph_neighborhood_size(const igraph_t *graph, igraph_vector_t *res, igraph_vs_t vids, igraph_integer_t order, igraph_neimode_t mode); 3.2. igraph_neighborhood — Calculate the neighborhood of vertices. foreign import ccall "neighborhood" c_igraph_neighborhood :: GraphPtr d a -> VectorPtrPtr -> VsPtr -> CInt -> CInt -> IO CInt neighborhood :: VertexSelector a -> Int -> IGraph (Graph d a) [[a]] neighborhood vs o = runUnsafeIO $ \g -> do v <- newVectorPtr 10 (_e, g') <- withGraph g $ \gp -> withVs vs g $ \vsp -> withVectorPtr v $ \vp -> c_igraph_neighborhood gp vp vsp (fromIntegral o) (getNeiMode g) ids <- vectorPtrToList v return (map (map (idToNode'' g . round)) ids, g') 3.3. igraph_neighborhood_graphs — Create graphs from the neighborhood(s) of some vertex/vertices. int igraph_neighborhood_graphs(const igraph_t *graph, igraph_vector_ptr_t *res, igraph_vs_t vids, igraph_integer_t order, igraph_neimode_t mode); -} -------------------------------------------------------------------------------- -- 13.4 Graph Components foreign import ccall "igraph_subcomponent" c_igraph_subcomponent :: GraphPtr -> VectorPtr -> CDouble -> CInt -> IO CInt -- | 4\.1\. `igraph_subcomponent` — The vertices in the same component as a given vertex. subcomponent :: Graph d a -> a -> [a] subcomponent g a = case nodeToId g a of Just i -> unsafePerformIO $ do v <- newVector 0 _ <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_subcomponent gp vp (fromIntegral i) (getNeiMode g) vectorToVertices g v _ -> [] foreign import ccall "induced_subgraph" c_igraph_induced_subcomponent :: GraphPtr -> GraphPtr -> VsPtr -> CInt -> IO CInt -- | 4\.2\. `igraph_induced_subgraph` — Creates a subgraph induced by the specified vertices. -- -- This function collects the specified vertices and all edges between them to a -- new graph. As the vertex ids in a graph always start with zero, this function -- very likely needs to reassign ids to the vertices. inducedSubgraph :: Graph d a -> VertexSelector a -> SubgraphImplementation -> Graph d a inducedSubgraph g vs i = unsafePerformIO $ do withGraph g $ \gp -> withVs vs g $ \vsp -> withGraph (emptyWithCtxt g) $ \gp' -> do setVertexIds gp _e <- c_igraph_induced_subcomponent gp gp' vsp (fromIntegral $ fromEnum i) subgraphFromPtr g gp' foreign import ccall "subgraph_edges" c_igraph_subgraph_edges :: GraphPtr -> GraphPtr -> EsPtr -> Bool -> IO CInt -- | 4\.3\. `igraph_subgraph_edges` — Creates a subgraph with the specified edges and their endpoints. -- -- This function collects the specified edges and their endpoints to a new -- graph. As the vertex ids in a graph always start with zero, this function -- very likely needs to reassign ids to the vertices. subgraphEdges :: Graph d a -> EdgeSelector d a -> Graph d a subgraphEdges g es = unsafePerformIO $ do withGraph g $ \gp -> withEs es g $ \esp -> withGraph (emptyWithCtxt g) $ \gp' -> do setVertexIds gp _e <- c_igraph_subgraph_edges gp gp' esp True subgraphFromPtr g gp' {- DEPRECATED foreign import ccall "subgraph" c_igraph_subgraph :: GraphPtr -> GraphPtr -> VsPtr -> IO CInt -- | 4\.4\. `igraph_subgraph` — Creates a subgraph induced by the specified vertices. subgraph :: Graph d a -> VertexSelector a -> Graph d a subgraph g vs = unsafePerformIO $ do withGraph g $ \gp -> withVs vs g $ \vsp -> withGraph (emptyWithCtxt g) $ \gp' -> do setVertexIds gp _e <- c_igraph_subgraph gp gp' vsp subgraphFromPtr g gp' -} foreign import ccall "igraph_clusters" c_igraph_clusters :: GraphPtr -> VectorPtr -> VectorPtr -> Ptr CInt -> CInt -> IO CInt -- | 4\.5\. `igraph_clusters` — Calculates the (weakly or strongly) connected -- components in a graph. clusters :: Graph d a -> Connectedness -> (Int, [Int]) -- ^ (number of clusters, list of size of all clusters) clusters g c = unsafePerformIO $ alloca $ \ip -> do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_clusters gp nullPtr vp ip (fromIntegral $ fromEnum c) i <- peek ip l <- vectorToList v return (fromIntegral i, map round l) foreign import ccall "igraph_is_connected" c_igraph_is_connected :: GraphPtr -> Ptr CInt -> CInt -> IO CInt -- | 4\.6\. `igraph_is_connected` — Decides whether the graph is (weakly or strongly) connected. -- -- A graph with zero vertices (i.e. the null graph) is connected by definition. isConnected :: Graph d a -> Connectedness -> Bool isConnected g c = unsafePerformIO $ withGraph g $ \gp -> alloca $ \b -> do _ <- c_igraph_is_connected gp b (fromIntegral $ fromEnum c) r <- peek b return $ r == 1 foreign import ccall "igraph_decompose" c_igraph_decompose :: GraphPtr -> GraphVecPtr -> CInt -> CLong -> CInt -> IO CInt -- | 4\.7\. `igraph_decompose` — Decompose a graph into connected components. -- -- Create separate graph for each component of a graph. Note that the vertex ids -- in the new graphs will be different than in the original graph. (Except if -- there is only one component in the original graph.) decompose :: Graph d a -> Connectedness -> Int -> Int -> [Graph d a] decompose g m ma mi = unsafePerformIO $ do gvp <- newGraphVector 0 _e <- withGraph g $ \gp -> withGraphVector gvp $ \gvpp -> do setVertexIds gp c_igraph_decompose gp gvpp (fromIntegral $ fromEnum m) (fromIntegral ma) (fromIntegral mi) graphVectorToSubgraphs gvp g {- 4.8. igraph_decompose_destroy — Free the memory allocated by igraph_decompose(). void igraph_decompose_destroy(igraph_vector_ptr_t *complist); necessary? no. -> foreign pointers! -} {- int igraph_biconnected_components(const igraph_t *graph, igraph_integer_t *no, igraph_vector_ptr_t *tree_edges, igraph_vector_ptr_t *component_edges, igraph_vector_ptr_t *components, igraph_vector_t *articulation_points); -} foreign import ccall "igraph_biconnected_components" c_igraph_biconnected_components :: GraphPtr -> Ptr CInt -> VectorPtrPtr -> VectorPtrPtr -> VectorPtrPtr -> VectorPtr -> IO CInt -- | 4\.9\. `igraph_biconnected_components` — Calculate biconnected components -- -- A graph is biconnected if the removal of any single vertex (and its incident -- edges) does not disconnect it. -- -- A biconnected component of a graph is a maximal biconnected subgraph of it. -- The biconnected components of a graph can be given by the partition of its -- edges: every edge is a member of exactly one biconnected component. Note that -- this is not true for vertices: the same vertex can be part of many -- biconnected components. biconnectedComponents :: Graph d a -> (Int, [[Edge d a]], [[Edge d a]], [[a]], [a]) -- ^ (number of biconnected -- components, edges of spanning trees, edges of biconnected components, -- vertices of biconnected components, articulation points of the graph) biconnectedComponents g = unsafePerformIO $ alloca $ \ip -> do t <- newVectorPtr 0 ce <- newVectorPtr 0 c <- newVectorPtr 0 a <- newVector 0 _e <- withGraph g $ \gp -> withVectorPtr t $ \tp -> withVectorPtr ce $ \cep -> withVectorPtr c $ \cp -> withVector a $ \ap -> c_igraph_biconnected_components gp ip tp cep cp ap i <- peek ip ts <- mapM (vectorToEdges' g) =<< vectorPtrToListOfVectorPtr t ces <- mapM (vectorToEdges' g) =<< vectorPtrToListOfVectorPtr ce cs <- mapM (vectorToVertices' g) =<< vectorPtrToListOfVectorPtr c as <- vectorToVertices g a return (fromIntegral i, ts, ces, cs, as) foreign import ccall "igraph_articulation_points" c_igraph_articulation_points :: GraphPtr -> VectorPtr -> IO CInt -- | 4\.10\. `igraph_articulation_points` — Find the articulation points in a -- graph. -- -- A vertex is an articulation point if its removal increases the number of -- connected components in the graph. articulationPoints :: Graph d a -> [a] articulationPoints g = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_articulation_points gp vp vectorToVertices g v -------------------------------------------------------------------------------- -- 13.5 Centrality Measures foreign import ccall "closeness" c_igraph_closeness :: GraphPtr -> VectorPtr -> VsPtr -> CInt -> VectorPtr -> IO CInt -- | 5\.1\. `igraph_closeness` — Closeness centrality calculations for some -- vertices. -- -- The closeness centrality of a vertex measures how easily other vertices can -- be reached from it (or the other way: how easily it can be reached from the -- other vertices). It is defined as the number of the number of vertices minus -- one divided by the sum of the lengths of all geodesics from/to the given -- vertex. -- -- If the graph is not connected, and there is no path between two vertices, the -- number of vertices is used instead the length of the geodesic. This is always -- longer than the longest possible geodesic. closeness :: Ord a => Graph d a -> VertexSelector a -> Map a Double closeness g vs = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withOptionalWeights g $ \wp -> withVs vs g $ \vsp -> withVector v $ \vp -> c_igraph_closeness gp vp vsp (getNeiMode g) wp scores <- vectorToList v return $ M.fromList $ zip (selectedVertices g vs) scores foreign import ccall "betweenness" c_igraph_betweenness :: GraphPtr -> VectorPtr -> VsPtr -> Bool -> VectorPtr -> Bool -> IO CInt -- | 5\.2\. `igraph_betweenness` — Betweenness centrality of some vertices. -- -- The betweenness centrality of a vertex is the number of geodesics going -- through it. If there are more than one geodesic between two vertices, the -- value of these geodesics are weighted by one over the number of geodesics. betweenness :: Ord a => Graph d a -> VertexSelector a -> Map a Double betweenness g vs = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withOptionalWeights g $ \wp -> withVs vs g $ \vsp -> withVector v $ \vp -> c_igraph_betweenness gp vp vsp True -- should be OK for all graphs wp True -- should be OK for all graphs scores <- vectorToList v return $ M.fromList $ zip (selectedVertices g vs) scores foreign import ccall "igraph_edge_betweenness" c_igraph_edge_betweenness :: GraphPtr -> VectorPtr -> Bool -> VectorPtr -> IO CInt -- | 5\.3\. `igraph_edge_betweenness` — Betweenness centrality of the edges. -- -- The betweenness centrality of an edge is the number of geodesics going -- through it. If there are more than one geodesics between two vertices, the -- value of these geodesics are weighted by one over the number of geodesics. edgeBetweenness :: Ord (Edge d a) => Graph d a -> Map (Edge d a) Double edgeBetweenness g = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withOptionalWeights g $ \wp -> withVector v $ \vp -> c_igraph_edge_betweenness gp vp True wp scores <- vectorToList v return $ M.fromList $ zip (F.toList $ edges g) scores foreign import ccall "pagerank" c_igraph_pagerank :: GraphPtr -> VectorPtr -> Ptr CDouble -> VsPtr -> Bool -> CDouble -> VectorPtr -> ArpackPtr -> IO CInt -- | 5\.4\. `igraph_pagerank` — Calculates the Google PageRank for the specified vertices. pagerank :: Graph d a -> VertexSelector a -> Double -- ^ The damping factor ("d" in the original paper) -> (Double, [(a,Double)]) pagerank g vs d = unsafePerformIO $ alloca $ \dp -> do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withVs vs g $ \vsp -> withOptionalWeights g $ \wp -> withArpack g $ \ap -> c_igraph_pagerank gp vp dp vsp True (realToFrac d) wp ap res <- peek dp lis <- vectorToList v return (realToFrac res, zip (nodes g) lis) {- 5.5. igraph_pagerank_old — Calculates the Google PageRank for the specified vertices. int igraph_pagerank_old(const igraph_t *graph, igraph_vector_t *res, const igraph_vs_t vids, igraph_bool_t directed, igraph_integer_t niter, igraph_real_t eps, igraph_real_t damping, igraph_bool_t old); -} foreign import ccall "personalized_pagerank" c_igraph_personalized_pagerank :: GraphPtr -> VectorPtr -> Ptr CDouble -> VsPtr -> Bool -> CDouble -> VectorPtr -> VectorPtr -> ArpackPtr -> IO CInt -- | 5\.6\. `igraph_personalized_pagerank` — Calculates the personalized Google PageRank for the specified vertices. personalizedPagerank :: Graph d a -> VertexSelector a -> Double -- ^ The damping factor ("d" in the original paper) -> (Double, [(a, Double)]) personalizedPagerank g vs d = unsafePerformIO $ alloca $ \dp -> do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withVs vs g $ \vsp -> withOptionalWeights g $ \wp -> withArpack g $ \ ap -> c_igraph_personalized_pagerank gp vp dp vsp True (realToFrac d) nullPtr wp ap res <- peek dp lis <- vectorToList v return (realToFrac res, zip (nodes g) lis) foreign import ccall "personalized_pagerank_vs" c_igraph_personalized_pagerank_vs :: GraphPtr -> VectorPtr -> Ptr CDouble -> VsPtr -> Bool -> CDouble -> VsPtr -> VectorPtr -> ArpackPtr -> IO CInt -- | 5\.7\. `igraph_personalized_pagerank_vs` — Calculates the personalized -- Google PageRank for the specified vertices. personalizedPagerankVs :: Graph d a -> VertexSelector a -> Double -- ^ The damping factor ("d" in the original paper) -> VertexSelector a -- ^ IDs of the vertices used when resetting the random -- walk. -> (Double, [(a, Double)]) personalizedPagerankVs g vs d reset = unsafePerformIO $ alloca $ \dp -> do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withVs vs g $ \vsp -> withVs reset g $ \resetp -> withOptionalWeights g $ \wp -> withArpack g $ \ap -> c_igraph_personalized_pagerank_vs gp vp dp vsp True (realToFrac d) resetp wp ap res <- peek dp lis <- vectorToList v return (realToFrac res, zip (nodes g) lis) foreign import ccall "constraint" c_igraph_constraint :: GraphPtr -> VectorPtr -> VsPtr -> VectorPtr -> IO CInt -- | 5\.8\. `igraph_constraint` — Burt's constraint scores. -- -- This function calculates Burt's constraint scores for the given vertices, -- also known as structural holes. -- -- Burt's constraint is higher if ego has less, or mutually stronger related -- (i.e. more redundant) contacts. Burt's measure of constraint, C[i], of vertex -- i's ego network V[i], is defined for directed and valued graphs, -- -- C[i] = sum( sum( (p[i,q] p[q,j])^2, q in V[i], q != i,j ), j in V[], j != i) -- -- for a graph of order (ie. number of vertices) N, where proportional tie -- strengths are defined as -- -- p[i,j]=(a[i,j]+a[j,i]) / sum(a[i,k]+a[k,i], k in V[i], k != i), -- -- a[i,j] are elements of A and the latter being the graph adjacency matrix. For -- isolated vertices, constraint is undefined. -- -- Burt, R.S. (2004). Structural holes and good ideas. American Journal of -- Sociology 110, 349-399. -- -- The first R version of this function was contributed by Jeroen Bruggeman. constraint :: Ord a => Graph d a -> VertexSelector a -> Map a Double constraint g vs = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withOptionalWeights g $ \wp -> withVector v $ \vp -> withVs vs g $ \vsp -> c_igraph_constraint gp vp vsp wp scores <- vectorToList v return $ M.fromList $ zip (selectedVertices g vs) scores foreign import ccall "maxdegree" c_igraph_maxdegree :: GraphPtr -> Ptr CInt -> VsPtr -> CInt -> Bool -> IO CInt -- | 5\.9\. `igraph_maxdegree` — Calculate the maximum degree in a graph (or set -- of vertices). -- -- The largest in-, out- or total degree of the specified vertices is -- calculated. maxdegree :: Graph d a -> VertexSelector a -> Bool -- ^ count self-loops? -> Int maxdegree g vs b = unsafePerformIO $ withGraph g $ \gp -> withVs vs g $ \vsp -> alloca $ \ip -> do _e <- c_igraph_maxdegree gp ip vsp (getNeiMode g) b fromIntegral `fmap` peek ip foreign import ccall "strength" c_igraph_strength :: GraphPtr -> VectorPtr -> VsPtr -> CInt -> Bool -> VectorPtr -> IO CInt -- | 5\.10\. `igraph_strength` — Strength of the vertices, weighted vertex degree -- in other words. -- -- In a weighted network the strength of a vertex is the sum of the weights of -- all incident edges. In a non-weighted network this is exactly the vertex -- degree. strength :: Ord a => Graph d a -> VertexSelector a -> Bool -- ^ count self-loops? -> Map a Int strength g vs b = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withVs vs g $ \vsp -> withOptionalWeights g $ \wp -> c_igraph_strength gp vp vsp (getNeiMode g) b wp scores <- vectorToList v return $ M.fromList $ zip (selectedVertices g vs) (map round scores) foreign import ccall "igraph_eigenvector_centrality" c_igraph_eigenvector_centrality :: GraphPtr -> VectorPtr -> Ptr CDouble -> Bool -> Bool -> VectorPtr -> ArpackPtr -> IO CInt -- | 5\.11\. `igraph_eigenvector_centrality` — Eigenvector centrality of the vertices eigenvectorCentrality :: Graph d a -> Bool -- ^ If True the result will be scaled such that the absolute value -- of the maximum centrality is one. -> (Double, [(a, Double)]) eigenvectorCentrality g s = unsafePerformIO $ alloca $ \dp -> do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withOptionalWeights g $ \wp -> withArpack g $ \ap -> c_igraph_eigenvector_centrality gp vp dp True s wp ap res <- peek dp lis <- vectorToList v return (realToFrac res, zip (nodes g) lis) foreign import ccall "igraph_hub_score" c_igraph_hub_score :: GraphPtr -> VectorPtr -> Ptr CDouble -> Bool -> VectorPtr -> ArpackPtr -> IO CInt -- | 5\.12\. `igraph_hub_score` — Kleinberg's hub scores hubScore :: Graph d a -> Bool -- ^ If True then the result will be scaled such that the absolute -- value of the maximum centrality is one. -> (Double, [(a, Double)]) hubScore g s = unsafePerformIO $ alloca $ \dp -> do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withOptionalWeights g $ \wp -> withArpack g $ \ap -> c_igraph_hub_score gp vp dp s wp ap res <- peek dp lis <- vectorToList v return (realToFrac res, zip (nodes g) lis) foreign import ccall "igraph_authority_score" c_igraph_authority_score :: GraphPtr -> VectorPtr -> Ptr CDouble -> Bool -> VectorPtr -> ArpackPtr -> IO CInt -- | 5\.13\. `igraph_authority_score` — Kleinerg's authority scores authorityScore :: Graph d a -> Bool -- ^ If True then the result will be scaled such that the absolute -- value of the maximum centrality is one. -> (Double, [(a, Double)]) authorityScore g s = unsafePerformIO $ alloca $ \dp -> do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withOptionalWeights g $ \wp -> withArpack g $ \ap -> c_igraph_authority_score gp vp dp s wp ap res <- peek dp lis <- vectorToList v return (realToFrac res, zip (nodes g) lis) -------------------------------------------------------------------------------- -- 13.6 Estimating Centrality Measures foreign import ccall "closeness_estimate" c_igraph_closeness_estimate :: GraphPtr -> VectorPtr -> VsPtr -> CInt -> CDouble -> VectorPtr -> IO CInt -- | 6\.1\. `igraph_closeness_estimate` — Closeness centrality estimations for -- some vertices. -- -- The closeness centrality of a vertex measures how easily other vertices can -- be reached from it (or the other way: how easily it can be reached from the -- other vertices). It is defined as the number of the number of vertices minus -- one divided by the sum of the lengths of all geodesics from/to the given -- vertex. When estimating closeness centrality, igraph considers paths having a -- length less than or equal to a prescribed cutoff value. -- -- If the graph is not connected, and there is no such path between two -- vertices, the number of vertices is used instead the length of the geodesic. -- This is always longer than the longest possible geodesic. -- -- Since the estimation considers vertex pairs with a distance greater than the -- given value as disconnected, the resulting estimation will always be lower -- than the actual closeness centrality. closenessEstimate :: Ord a => Graph d a -> VertexSelector a -> Int -- ^ cutoff -> Map a Double closenessEstimate g vs cutoff = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withVs vs g $ \vsp -> withOptionalWeights g $ \wp -> c_igraph_closeness_estimate gp vp vsp (getNeiMode g) (fromIntegral cutoff) wp scores <- vectorToList v return $ M.fromList $ zip (selectedVertices g vs) scores foreign import ccall "betweenness_estimate" c_igraph_betweenness_estimate :: GraphPtr -> VectorPtr -> VsPtr -> Bool -> CDouble -> VectorPtr -> Bool -> IO CInt -- | 6\.2\. `igraph_betweenness_estimate` — Estimated betweenness centrality of -- some vertices. -- -- The betweenness centrality of a vertex is the number of geodesics going -- through it. If there are more than one geodesic between two vertices, the -- value of these geodesics are weighted by one over the number of geodesics. -- When estimating betweenness centrality, igraph takes into consideration only -- those paths that are shorter than or equal to a prescribed length. Note that -- the estimated centrality will always be less than the real one. betweennessEstimate :: Ord a => Graph d a -> VertexSelector a -> Int -- ^ cutoff -> Map a Double betweennessEstimate g@(G _) vs cutoff = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withVs vs g $ \vsp -> withOptionalWeights g $ \wp -> c_igraph_betweenness_estimate gp vp vsp (isDirected g) (fromIntegral cutoff) wp True -- should be OK for most graphs scores <- vectorToList v return $ M.fromList $ zip (selectedVertices g vs) scores foreign import ccall "igraph_edge_betweenness_estimate" c_igraph_edge_betweenness_estimate :: GraphPtr -> VectorPtr -> Bool -> CDouble -> VectorPtr -> IO CInt -- | 6\.3\. `igraph_edge_betweenness_estimate` — Estimated betweenness centrality -- of the edges. -- -- The betweenness centrality of an edge is the number of geodesics going -- through it. If there are more than one geodesics between two vertices, the -- value of these geodesics are weighted by one over the number of geodesics. -- When estimating betweenness centrality, igraph takes into consideration only -- those paths that are shorter than or equal to a prescribed length. Note that edgeBetweennessEstimate :: Ord (Edge d a) => Graph d a -> Int -- ^ cutoff -> Map (Edge d a) Double edgeBetweennessEstimate g@(G _) cutoff = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withOptionalWeights g $ \wp -> c_igraph_edge_betweenness_estimate gp vp (isDirected g) (fromIntegral cutoff) wp scores <- vectorToList v return $ M.fromList $ zip (F.toList $ edges g) scores -------------------------------------------------------------------------------- -- 13.7 Centralization {- 7.1. igraph_centralization — Calculate the centralization score from the node level scores igraph_real_t igraph_centralization(const igraph_vector_t *scores, igraph_real_t theoretical_max, igraph_bool_t normalized); -} foreign import ccall "igraph_centralization_degree" c_igraph_centralization_degree :: GraphPtr -> VectorPtr -> CInt -> Bool -> Ptr CDouble -> Ptr CDouble -> Bool -> IO CInt -- | 7\.2\. `igraph_centralization_degree` — Calculate vertex degree and graph -- centralization -- -- This function calculates the degree of the vertices by passing its arguments -- to igraph_degree(); and it calculates the graph level centralization index -- based on the results by calling igraph_centralization(). centralizationDegree :: Ord a => Graph d a -> Bool -- ^ consider loop edges? -> Bool -- ^ normalize centralization score? -> (Map a Double, Double, Double) -- ^ (node-level degree scores, centralization scores, theoretical max) centralizationDegree g l n = unsafePerformIO $ do v <- newVector 0 alloca $ \cp -> alloca $ \tp -> do _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_centralization_degree gp vp (getNeiMode g) l cp tp n scores <- vectorToList v c <- peek cp t <- peek tp return ( M.fromList (zip (F.toList (nodes g)) scores) , realToFrac c , realToFrac t ) foreign import ccall "igraph_centralization_betweenness" c_igraph_centralization_betweenness :: GraphPtr -> VectorPtr -> Bool -> Bool -> Ptr CDouble -> Ptr CDouble -> Bool -> IO CInt -- | 7\.3\. `igraph_centralization_betweenness` — Calculate vertex betweenness and -- graph centralization -- -- This function calculates the betweenness centrality of the vertices by -- passing its arguments to igraph_betweenness(); and it calculates the graph -- level centralization index based on the results by calling -- igraph_centralization(). centralizationBetweenness :: Ord a => Graph d a -> Bool -- ^ normalize centralization score? -> (Map a Double, Double, Double) -- ^ (node-level degree scores, centralization scores, theoretical max) centralizationBetweenness g@(G _) n = unsafePerformIO $ alloca $ \cp -> alloca $ \tp -> do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_centralization_betweenness gp vp (isDirected g) False cp tp n scores <- vectorToList v c <- peek cp t <- peek tp return ( M.fromList (zip (F.toList (nodes g)) scores) , realToFrac c , realToFrac t ) foreign import ccall "igraph_centralization_closeness" c_igraph_centralization_closeness :: GraphPtr -> VectorPtr -> CInt -> Ptr CDouble -> Ptr CDouble -> Bool -> IO CInt -- | 7\.4\. `igraph_centralization_closeness` — Calculate vertex closeness and -- graph centralization -- -- This function calculates the closeness centrality of the vertices by passing -- its arguments to igraph_closeness(); and it calculates the graph level -- centralization index based on the results by calling igraph_centralization(). centralizationCloseness :: Ord a => Graph d a -> Bool -- ^ normalize centralization score? -> (Map a Double, Double, Double) -- ^ (node-level degree scores, centralization scores, theoretical max) centralizationCloseness g n = unsafePerformIO $ alloca $ \cp -> alloca $ \tp -> do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_centralization_closeness gp vp (getNeiMode g) cp tp n scores <- vectorToList v c <- peek cp t <- peek tp return ( M.fromList (zip (F.toList (nodes g)) scores) , realToFrac c , realToFrac t ) foreign import ccall "igraph_centralization_eigenvector_centrality" c_igraph_centralization_eigenvector_centrality :: GraphPtr -> Ptr CDouble -> Bool -> Bool -> ArpackPtr -> Ptr CDouble -> Ptr CDouble -> Bool -> IO CInt -- | 7\.5\. `igraph_centralization_eigenvector_centrality` — Calculate -- eigenvector centrality scores and graph centralization -- -- This function calculates the eigenvector centrality of the vertices by -- passing its arguments to igraph_eigenvector_centrality); and it calculates -- the graph level centralization index based on the results by calling -- igraph_centralization(). centralizationEigenvectorCentrality :: Graph d a -> Bool -- ^ If True then the result will be scaled, such that the absolute -- value of the maximum centrality is one. -> Bool -- ^ Boolean, whether to calculate a normalized centralization score. -- See igraph_centralization() for how the normalization is done. -> (Double, Double, Double) -- ^ (leading eigen-value, centralization score, theoretical max) centralizationEigenvectorCentrality g s n = unsafePerformIO $ alloca $ \evp -> alloca $ \csp -> alloca $ \tmp -> do _e <- withGraph g $ \gp -> withArpack g $ \ap -> c_igraph_centralization_eigenvector_centrality gp evp True s ap csp tmp n ev <- peek evp cs <- peek csp tm <- peek tmp return (realToFrac ev,realToFrac cs,realToFrac tm) foreign import ccall "igraph_centralization_degree_tmax" c_igraph_centralization_degree_tmax :: GraphPtr -> CInt -> CInt -> Bool -> Ptr CDouble -> IO CInt -- | 7\.6\. `igraph_centralization_degree_tmax` — Theoretical maximum for graph -- centralization based on degree -- -- This function returns the theoretical maximum graph centrality based on -- vertex degree. -- -- There are two ways to call this function, the first is to supply a graph as -- the graph argument, and then the number of vertices is taken from this -- object, and its directedness is considered as well. The nodes argument is -- ignored in this case. The mode argument is also ignored if the supplied graph -- is undirected. -- -- The other way is to supply a null pointer as the graph argument. In this case -- the nodes and mode arguments are considered. -- -- The most centralized structure is the star. More specifically, for undirected -- graphs it is the star, for directed graphs it is the in-star or the out-star. centralizationDegreeTMax :: Either (Graph d a) Int -- ^ either graph or number of nodes -> Bool -- ^ consider loop edges? -> Double centralizationDegreeTMax egi b = unsafePerformIO $ alloca $ \rp -> do _e <- withGraph' egi $ \gp -> c_igraph_centralization_degree_tmax gp i neimode b rp r <- peek rp return ( realToFrac r ) where withGraph' (Left g) = withGraph g withGraph' (Right _) = (\f -> f nullPtr) i = either (const 0) fromIntegral egi neimode = either getNeiMode (const (fromIntegral (fromEnum Out))) egi foreign import ccall "igraph_centralization_betweenness_tmax" c_igraph_centralization_betweenness_tmax :: GraphPtr -> CInt -> Bool -> Ptr CDouble -> IO CInt -- | 7\.7\. `igraph_centralization_betweenness_tmax` — Theoretical maximum for -- graph centralization based on betweenness -- -- This function returns the theoretical maximum graph centrality based on -- vertex betweenness. -- -- There are two ways to call this function, the first is to supply a graph as -- the graph argument, and then the number of vertices is taken from this -- object, and its directedness is considered as well. The nodes argument is -- ignored in this case. The directed argument is also ignored if the supplied -- graph is undirected. -- -- The other way is to supply a null pointer as the graph argument. In this case -- the nodes and directed arguments are considered. -- -- The most centralized structure is the star. centralizationBetweennessTMax :: Either (Graph d a) Int -> Double centralizationBetweennessTMax egi = unsafePerformIO $ alloca $ \rp -> do _e <- withGraph' egi $ \gp -> c_igraph_centralization_betweenness_tmax gp i directed rp r <- peek rp return ( realToFrac r ) where withGraph' (Left g) = withGraph g withGraph' (Right _) = (\f -> f nullPtr) i = either (const 0) fromIntegral egi directed = either (\g@(G _) -> isDirected g) (const True) egi foreign import ccall "igraph_centralization_closeness_tmax" c_igraph_centralization_closeness_tmax :: GraphPtr -> CInt -> CInt -> Ptr CDouble -> IO CInt -- | 7\.8\. `igraph_centralization_closeness_tmax` — Theoretical maximum for graph -- centralization based on closeness -- -- This function returns the theoretical maximum graph centrality based on -- vertex closeness. -- -- There are two ways to call this function, the first is to supply a graph as -- the graph argument, and then the number of vertices is taken from this -- object, and its directedness is considered as well. The nodes argument is -- ignored in this case. The mode argument is also ignored if the supplied graph -- is undirected. -- -- The other way is to supply a null pointer as the graph argument. In this case -- the nodes and mode arguments are considered. -- -- The most centralized structure is the star. centralizationClosenessTMax :: Either (Graph d a) Int -> Double centralizationClosenessTMax egi = unsafePerformIO $ alloca $ \rp -> do _e <- withGraph' egi $ \gp -> c_igraph_centralization_closeness_tmax gp i neimode rp r <- peek rp return ( realToFrac r ) where withGraph' (Left g) = withGraph g withGraph' (Right _) = (\f -> f nullPtr) i = either (const 0) fromIntegral egi neimode = either getNeiMode (const (fromIntegral (fromEnum Out))) egi foreign import ccall "igraph_centralization_eigenvector_centrality_tmax" c_igraph_centralization_eigenvector_centrality_tmax :: GraphPtr -> CInt -> Bool -> Bool -> Ptr CDouble -> IO CInt -- | 7\.9\. `igraph_centralization_eigenvector_centrality_tmax` — Theoretical -- maximum centralization for eigenvector centrality -- -- This function returns the theoretical maximum graph centrality based on -- vertex eigenvector centrality. -- -- There are two ways to call this function, the first is to supply a graph as -- the graph argument, and then the number of vertices is taken from this -- object, and its directedness is considered as well. The nodes argument is -- ignored in this case. The directed argument is also ignored if the supplied -- graph is undirected. -- -- The other way is to supply a null pointer as the graph argument. In this case -- the nodes and directed arguments are considered. -- -- The most centralized directed structure is the in-star. The most centralized -- undirected structure is the graph with a single edge. centralizationEigenvectorCentralityTMax :: Either (Graph d a) Int -> Bool -- ^ Whether to consider edge directions. This argument is ignored if -- graph is not a null pointer and it is undirected -> Bool -- ^ Whether to rescale the node-level centrality scores to have a maximum of one -> Double centralizationEigenvectorCentralityTMax egi dir sc = unsafePerformIO $ alloca $ \dp -> do _e <- withGraph' egi $ \gp -> c_igraph_centralization_eigenvector_centrality_tmax gp i dir sc dp realToFrac `fmap` peek dp where withGraph' (Left g) = withGraph g withGraph' (Right _) = (\f -> f nullPtr) i = either (const 0) fromIntegral egi -------------------------------------------------------------------------------- -- 13.8 Similarity Measures foreign import ccall "bibcoupling" c_igraph_bibcoupling :: GraphPtr -> MatrixPtr -> VsPtr -> IO CInt -- | 8\.1\. `igraph_bibcoupling` — Bibliographic coupling. -- -- The bibliographic coupling of two vertices is the number of other vertices -- they both cite, `igraph_bibcoupling()` calculates this. The bibliographic -- coupling score for each given vertex and all other vertices in the graph will -- be calculated. bibCoupling :: Graph d a -> VertexSelector a -> [(a,[(a,Int)])] bibCoupling g vs = unsafePerformIO $ do let selected = selectedVertices g vs nrows = length selected ncols = numberOfNodes g m <- newMatrix nrows ncols _e <- withGraph g $ \gp -> withVs vs g $ \vsp -> withMatrix m $ \mp -> c_igraph_bibcoupling gp mp vsp ids <- map (map round) `fmap` matrixToList m return $ zip selected (map (zip (nodes g)) ids) foreign import ccall "cocitation" c_igraph_cocitation :: GraphPtr -> MatrixPtr -> VsPtr -> IO CInt -- | 8\.2\. `igraph_cocitation` — Cocitation coupling. -- -- Two vertices are cocited if there is another vertex citing both of them. -- `igraph_cocitation()` simply counts how many times two vertices are cocited. -- The cocitation score for each given vertex and all other vertices in the -- graph will be calculated. cocitation :: Graph d a -> VertexSelector a -> [(a,[(a,Int)])] cocitation g vs = unsafePerformIO $ do let selected = selectedVertices g vs nrows = length selected ncols = numberOfNodes g m <- newMatrix nrows ncols _e <- withGraph g $ \gp -> withVs vs g $ \vsp -> withMatrix m $ \mp -> c_igraph_cocitation gp mp vsp ids <- map (map round) `fmap` matrixToList m return $ zip selected (map (zip (nodes g)) ids) foreign import ccall "similarity_jaccard" c_igraph_similarity_jaccard :: GraphPtr -> MatrixPtr -> VsPtr -> CInt -> Bool -> IO CInt -- | 8\.3\. `igraph_similarity_jaccard` — Jaccard similarity coefficient for the -- given vertices. -- -- The Jaccard similarity coefficient of two vertices is the number of common -- neighbors divided by the number of vertices that are neighbors of at least -- one of the two vertices being considered. This function calculates the -- pairwise Jaccard similarities for some (or all) of the vertices. similarityJaccard :: Graph d a -> VertexSelector a -> Bool -- ^ Whether to include the vertices themselves in the neighbor sets -> [(a,[(a,Double)])] similarityJaccard g vs loops = unsafePerformIO $ do let selected = selectedVertices g vs nrows = length selected m <- newMatrix nrows nrows _e <- withGraph g $ \gp -> withVs vs g $ \vsp -> withMatrix m $ \mp -> c_igraph_similarity_jaccard gp mp vsp (getNeiMode g) loops ids <- matrixToList m return $ zip selected (map (zip selected) ids) foreign import ccall "igraph_similarity_jaccard_pairs" c_igraph_similarity_jaccard_pairs :: GraphPtr -> VectorPtr -> VectorPtr -> CInt -> Bool -> IO CInt -- | 8\.4\. `igraph_similarity_jaccard_pairs` — Jaccard similarity coefficient for -- given vertex pairs. -- -- The Jaccard similarity coefficient of two vertices is the number of common -- neighbors divided by the number of vertices that are neighbors of at least -- one of the two vertices being considered. This function calculates the -- pairwise Jaccard similarities for a list of vertex pairs. similarityJaccardPairs :: Graph d a -> [Edge d a] -> Bool -- ^ Whether to include the vertices themselves in the neighbor sets -> [(Edge d a,Double)] similarityJaccardPairs g@(G _) es loops = unsafePerformIO $ do p <- listToVector $ foldr (\e r -> nodeToId'' g (edgeFrom e):nodeToId'' g (edgeTo e):r) [] es r <- newVector (length es) _e <- withGraph g $ \gp -> withVector r $ \rp -> withVector p $ \pp -> c_igraph_similarity_jaccard_pairs gp rp pp (getNeiMode g) loops res <- vectorToList r return $ zip es res foreign import ccall "similarity_jaccard_es" c_igraph_similarity_jaccard_es :: GraphPtr -> VectorPtr -> EsPtr -> CInt -> Bool -> IO CInt -- | 8\.5\. `igraph_similarity_jaccard_es` — Jaccard similarity coefficient for a -- given edge selector. -- -- The Jaccard similarity coefficient of two vertices is the number of common -- neighbors divided by the number of vertices that are neighbors of at least -- one of the two vertices being considered. This function calculates the -- pairwise Jaccard similarities for the endpoints of edges in a given edge -- selector. similarityJaccardEs :: Graph d a -> EdgeSelector d a -> Bool -- ^ Whether to include the vertices themselves in the neighbor sets -> [(Edge d a, Double)] similarityJaccardEs g es b = unsafePerformIO $ do let sel = selectedEdges g es v <- newVector (length sel) _e <- withGraph g $ \gp -> withVector v $ \vp -> withEs es g $ \esp -> c_igraph_similarity_jaccard_es gp vp esp (getNeiMode g) b l <- vectorToList v return $ zip sel l foreign import ccall "similarity_dice" c_igraph_similarity_dice :: GraphPtr -> MatrixPtr -> VsPtr -> CInt -> Bool -> IO CInt -- | 8\.6\. `igraph_similarity_dice` — Dice similarity coefficient. -- -- The Dice similarity coefficient of two vertices is twice the number of -- common neighbors divided by the sum of the degrees of the vertices. This -- function calculates the pairwise Dice similarities for some (or all) of the -- vertices. similarityDice :: Graph d a -> VertexSelector a -> Bool -- ^ Whether to include the vertices themselves as their own neighbors -> [(a,[(a,Double)])] similarityDice g vs loops = unsafePerformIO $ do let sel = selectedVertices g vs n = length sel m <- newMatrix n n _e <- withGraph g $ \gp -> withVs vs g $ \vsp -> withMatrix m $ \mp -> c_igraph_similarity_dice gp mp vsp (getNeiMode g) loops res <- matrixToList m return $ zip sel (map (zip sel) res) foreign import ccall "igraph_similarity_dice_pairs" c_igraph_similarity_dice_pairs :: GraphPtr -> VectorPtr -> VectorPtr -> CInt -> Bool -> IO CInt -- | 8\.7\. `igraph_similarity_dice_pairs` — Dice similarity coefficient for given -- vertex pairs. -- -- The Dice similarity coefficient of two vertices is twice the number of -- common neighbors divided by the sum of the degrees of the vertices. This -- function calculates the pairwise Dice similarities for a list of vertex -- pairs. similarityDicePairs :: Graph d a -> [Edge d a] -> Bool -- ^ Whether to include the vertices themselves as their own neighbors -> [(Edge d a, Double)] similarityDicePairs g@(G _) es loops = unsafePerformIO $ do v <- listToVector $ foldr (\e r -> nodeToId'' g (edgeFrom e) : nodeToId'' g (edgeTo e) : r) [] es r <- newVector (length es) _e <- withGraph g $ \gp -> withVector r $ \rp -> withVector v $ \vp -> c_igraph_similarity_dice_pairs gp rp vp (getNeiMode g) loops res <- vectorToList r return $ zip es res foreign import ccall "similarity_dice_es" c_igraph_similarity_dice_es :: GraphPtr -> VectorPtr -> EsPtr -> CInt -> Bool -> IO CInt -- | 8\.8\. `igraph_similarity_dice_es` — Dice similarity coefficient for a given -- edge selector. -- -- The Dice similarity coefficient of two vertices is twice the number of common -- neighbors divided by the sum of the degrees of the vertices. This function -- calculates the pairwise Dice similarities for the endpoints of edges in a -- given edge selector. similarityDiceEs :: Graph d a -> EdgeSelector d a -> Bool -- ^ Whether to include the vertices themselves as their own neighbors -> [(Edge d a, Double)] similarityDiceEs g es b = unsafePerformIO $ do let sel = selectedEdges g es v <- newVector (length sel) _e <- withGraph g $ \gp -> withVector v $ \vp -> withEs es g $ \esp -> c_igraph_similarity_dice_es gp vp esp (getNeiMode g) b l <- vectorToList v return $ zip sel l foreign import ccall "similarity_inverse_log_weighted" c_igraph_similarity_inverse_log_weighted :: GraphPtr -> MatrixPtr -> VsPtr -> CInt -> IO CInt -- | 8\.9\. `igraph_similarity_inverse_log_weighted` — Vertex similarity based on -- the inverse logarithm of vertex degrees. -- -- The inverse log-weighted similarity of two vertices is the number of their -- common neighbors, weighted by the inverse logarithm of their degrees. It is -- based on the assumption that two vertices should be considered more similar -- if they share a low-degree common neighbor, since high-degree common -- neighbors are more likely to appear even by pure chance. -- -- Isolated vertices will have zero similarity to any other vertex. -- Self-similarities are not calculated. -- -- See the following paper for more details: Lada A. Adamic and Eytan Adar: -- Friends and neighbors on the Web. Social Networks, 25(3):211-230, 2003. similarityInverseLogWeighted :: Graph d a -> VertexSelector a -> [(a,[(a,Double)])] similarityInverseLogWeighted g vs = unsafePerformIO $ do let sel = selectedVertices g vs nrows = length sel ncols = numberOfNodes g m <- newMatrix nrows ncols _e <- withGraph g $ \gp -> withMatrix m $ \mp -> withVs vs g $ \vsp -> c_igraph_similarity_inverse_log_weighted gp mp vsp (getNeiMode g) r <- matrixToList m return $ zip sel (map (zip (nodes g)) r) -------------------------------------------------------------------------------- -- 13.9 Spanning Trees foreign import ccall "igraph_minimum_spanning_tree" c_igraph_minimum_spanning_tree :: GraphPtr -> VectorPtr -> VectorPtr -> IO CInt -- | 9\.1\. `igraph_minimum_spanning_tree` — Calculates one minimum spanning tree of a graph. -- -- If the graph has more minimum spanning trees (this is always the case, except -- if it is a forest) this implementation returns only the same one. -- -- Directed graphs are considered as undirected for this computation. -- -- If the graph is not connected then its minimum spanning forest is returned. -- This is the set of the minimum spanning trees of each component. minimumSpanningTree :: Graph d a -> [Edge d a] minimumSpanningTree g@(G _) = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withOptionalWeights g $ \wp -> c_igraph_minimum_spanning_tree gp vp wp vectorToEdges g v foreign import ccall "igraph_minimum_spanning_tree_unweighted" c_igraph_minimum_spanning_tree_unweighted :: GraphPtr -> GraphPtr -> IO CInt -- | 9\.2\. `igraph_minimum_spanning_tree_unweighted` — Calculates one minimum -- spanning tree of an unweighted graph. minimumSpanningTreeUnweighted :: IsUnweighted d => Graph d a -> Graph d a minimumSpanningTreeUnweighted g = unsafePerformIO $ withGraph g $ \gp -> withGraph (emptyWithCtxt g) $ \gp' -> do setVertexIds gp _e <- c_igraph_minimum_spanning_tree_unweighted gp gp' subgraphFromPtr g gp' foreign import ccall "igraph_minimum_spanning_tree_prim" c_igraph_minimum_spanning_tree_prim :: GraphPtr -> GraphPtr -> VectorPtr -> IO CInt -- | 9\.3\. `igraph_minimum_spanning_tree_prim` — Calculates one minimum -- spanning tree of a weighted graph. minimumSpanningTreePrim :: IsUnweighted d => Graph (Weighted d) a -> Graph (Weighted d) a minimumSpanningTreePrim g = unsafePerformIO $ withGraph g $ \gp -> withOptionalWeights g $ \wp -> withGraph (emptyWithCtxt g) $ \gp' -> do setVertexIds gp _e <- c_igraph_minimum_spanning_tree_prim gp gp' wp subgraphFromPtr g gp' -------------------------------------------------------------------------------- -- 13.10 Transitivity or Clustering Coefficient foreign import ccall "igraph_transitivity_undirected" c_igraph_transitivity_undirected :: GraphPtr -> Ptr CDouble -> CInt -> IO CInt -- | 10\.1\. `igraph_transitivity_undirected` — Calculates the transitivity -- (clustering coefficient) of a graph. -- -- The transitivity measures the probability that two neighbors of a vertex are -- connected. More precisely, this is the ratio of the triangles and connected -- triples in the graph, the result is a single real number. Directed graphs are -- considered as undirected ones. -- -- Note that this measure is different from the local transitivity measure (see -- `igraph_transitivity_local_undirected()` ) as it calculates a single value for -- the whole graph. See the following reference for more details: -- -- S. Wasserman and K. Faust: Social Network Analysis: Methods and Applications. -- Cambridge: Cambridge University Press, 1994. -- -- Clustering coefficient is an alternative name for transitivity. transitivityUndirected :: Graph d a -> Double transitivityUndirected g = unsafePerformIO $ alloca $ \dp -> do _e <- withGraph g $ \gp -> c_igraph_transitivity_undirected gp dp (fromIntegral $ fromEnum TransitivityZero) realToFrac `fmap` peek dp foreign import ccall "transitivity_local_undirected" c_igraph_transitivity_local_undirected :: GraphPtr -> VectorPtr -> VsPtr -> CInt -> IO CInt -- | 10\.2\. `igraph_transitivity_local_undirected` — Calculates the local -- transitivity (clustering coefficient) of a graph. -- -- The transitivity measures the probability that two neighbors of a vertex are -- connected. In case of the local transitivity, this probability is calculated -- separately for each vertex. -- -- Note that this measure is different from the global transitivity measure (see -- igraph_transitivity_undirected() ) as it calculates a transitivity value for -- each vertex individually. See the following reference for more details: -- -- D. J. Watts and S. Strogatz: Collective dynamics of small-world networks. -- Nature 393(6684):440-442 (1998). -- -- Clustering coefficient is an alternative name for transitivity. transitivityLocalUndirected :: Graph d a -> VertexSelector a -> [(a,Double)] transitivityLocalUndirected g vs = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withVs vs g $ \vsp -> c_igraph_transitivity_local_undirected gp vp vsp (fromIntegral $ fromEnum TransitivityZero) let sel = selectedVertices g vs r <- vectorToList v return $ zip sel r foreign import ccall "igraph_transitivity_avglocal_undirected" c_igraph_transitivity_avglocal_undirected :: GraphPtr -> Ptr CDouble -> CInt -> IO CInt -- | 10\.3\. `igraph_transitivity_avglocal_undirected` — Average local transitivity -- (clustering coefficient). -- -- The transitivity measures the probability that two neighbors of a vertex are -- connected. In case of the average local transitivity, this probability is -- calculated for each vertex and then the average is taken. Vertices with less -- than two neighbors require special treatment, they will either be left out -- from the calculation or they will be considered as having zero transitivity, -- depending on the mode argument. -- -- Note that this measure is different from the global transitivity measure (see -- `igraph_transitivity_undirected()` ) as it simply takes the average local -- transitivity across the whole network. See the following reference for more -- details: -- -- D. J. Watts and S. Strogatz: Collective dynamics of small-world networks. -- Nature 393(6684):440-442 (1998). -- -- Clustering coefficient is an alternative name for transitivity. transitivityAvglocalUndirected :: Graph d a -> Double transitivityAvglocalUndirected g = unsafePerformIO $ alloca $ \dp -> do _e <- withGraph g $ \gp -> c_igraph_transitivity_avglocal_undirected gp dp (fromIntegral $ fromEnum TransitivityZero) realToFrac `fmap` peek dp foreign import ccall "transitivity_barrat" c_igraph_transitivity_barrat :: GraphPtr -> VectorPtr -> VsPtr -> VectorPtr -> CInt -> IO CInt -- | 10\.4\. `igraph_transitivity_barrat` — Weighted transitivity, as defined by A. -- Barrat. -- -- This is a local transitivity, i.e. a vertex-level index. For a given vertex -- i, from all triangles in which it participates we consider the weight of the -- edges incident on i. The transitivity is the sum of these weights divided by -- twice the strength of the vertex (see `igraph_strength()`) and the degree of -- the vertex minus one. See Alain Barrat, Marc Barthelemy, Romualdo -- Pastor-Satorras, Alessandro Vespignani: The architecture of complex weighted -- networks, Proc. Natl. Acad. Sci. USA 101, 3747 (2004) at -- http://arxiv.org/abs/cond-mat/0311416 for the exact formula. transitivityBarrat :: Graph d a -> VertexSelector a -> [(a,Double)] transitivityBarrat g vs = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withVs vs g $ \vsp -> withOptionalWeights g $ \wp -> c_igraph_transitivity_barrat gp vp vsp wp (fromIntegral $ fromEnum TransitivityZero) r <- vectorToList v return $ zip (selectedVertices g vs) r -------------------------------------------------------------------------------- -- 13.11 Directedness conversion -- Done in Haskell -------------------------------------------------------------------------------- -- 13.12 Spectral properties foreign import ccall "igraph_laplacian" c_igraph_laplacian :: GraphPtr -> MatrixPtr -> SpMatrixPtr -> Bool -> VectorPtr -> IO CInt -- | 12\.1\. `igraph_laplacian` — Returns the Laplacian matrix of a graph -- -- The graph Laplacian matrix is similar to an adjacency matrix but contains -- -1's instead of 1's and the vertex degrees are included in the diagonal. So -- the result for edge i--j is -1 if i!=j and is equal to the degree of vertex i -- if i==j. igraph_laplacian will work on a directed graph; in this case, the -- diagonal will contain the out-degrees. Loop edges will be ignored. -- -- The normalized version of the Laplacian matrix has 1 in the diagonal and -- -1/sqrt(d[i]d[j]) if there is an edge from i to j. -- -- The first version of this function was written by Vincent Matossian. laplacian :: Graph d a -> Bool -- ^ Whether to create a normalized Laplacian matrix -> [[Double]] laplacian g norm = unsafePerformIO $ do m <- newMatrix 0 0 _e <- withGraph g $ \gp -> withMatrix m $ \mp -> withOptionalWeights g $ \wp -> c_igraph_laplacian gp mp nullPtr norm wp matrixToList m -------------------------------------------------------------------------------- -- 13.13 Non-simple graphs: multiple and loop edges {- This whole chapter might not be necessary since we can't have edges from a - vertex to itself or multiple edges in our graph due to the use of Map/Sets! foreign import ccall "igraph_is_simple" c_igraph_is_simple :: GraphPtr -> Ptr Bool -> IO CInt -- | 13\.1\. `igraph_is_simple` — Decides whether the input graph is a simple graph. -- -- A graph is a simple graph if it does not contain loop edges and multiple -- edges. isSimple :: Graph d a -> Bool isSimple g = unsafePerformIO $ alloca $ \bp -> do _e <- withGraph g $ \gp -> c_igraph_is_simple gp bp peek bp foreign import ccall "is_loop" c_igraph_is_loop :: GraphPtr -> VectorPtr -> EsPtr -> IO CInt -- | 13\.2\. `igraph_is_loop` — Find the loop edges in a graph. -- --A loop edge is an edge from a vertex to itself. isLoop :: Graph d a -> EdgeSelector d a -> [(Edge d a, Bool)] isLoop g es = unsafePerformIO $ do let sel = selectedEdges g es v <- newVector (length sel) _e <- withGraph g $ \gp -> withVector v $ \vp -> withEs es g $ \esp -> c_igraph_is_loop gp vp esp l <- vectorToList v return $ zip sel (map (0 /=) l) -} -------------------------------------------------------------------------------- -- 13.14 Mixing patterns foreign import ccall "igraph_assortativity_nominal" c_igraph_assortativity_nominal :: GraphPtr -> VectorPtr -> Ptr CDouble -> Bool -> IO CInt -- | 14\.1\. `igraph_assortativity_nominal` — Assortativity of a graph based on -- vertex categories -- -- Assuming the vertices of the input graph belong to different categories, this -- function calculates the assortativity coefficient of the graph. The -- assortativity coefficient is between minus one and one and it is one if all -- connections stay within categories, it is minus one, if the network is -- perfectly disassortative. For a randomly connected network it is -- (asymptotically) zero. -- -- See equation (2) in M. E. J. Newman: Mixing patterns in networks, Phys. Rev. -- E 67, 026126 (2003) (http://arxiv.org/abs/cond-mat/0209450) for the proper -- definition. assortativityNominal :: (Eq vertexType) => Graph d (vertexType, a) -> Bool -- ^ whether to consider edge directions in a directed graph. It is -- ignored for undirected graphs -> Double assortativityNominal g b = unsafePerformIO $ alloca $ \dp -> do let all_types = map fst $ nodes g types = map fst $ zip [(0 :: Int)..] (nub all_types) v <- listToVector types _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_assortativity_nominal gp vp dp b realToFrac `fmap` peek dp foreign import ccall "igraph_assortativity" c_igraph_assortativity :: GraphPtr -> VectorPtr -> VectorPtr -> Ptr CDouble -> Bool -> IO CInt -- | 14\.2\. `igraph_assortativity` — Assortativity based on numeric properties of -- vertices -- -- This function calculates the assortativity coefficient of the input graph. -- This coefficient is basically the correlation between the actual connectivity -- patterns of the vertices and the pattern expected from the distribution of -- the vertex types. -- -- See equation (21) in M. E. J. Newman: Mixing patterns in networks, Phys. Rev. -- E 67, 026126 (2003) (http://arxiv.org/abs/cond-mat/0209450) for the proper -- definition. The actual calculation is performed using equation (26) in the -- same paper for directed graphs, and equation (4) in M. E. J. Newman: -- Assortative mixing in networks, Phys. Rev. Lett. 89, 208701 (2002) -- (http://arxiv.org/abs/cond-mat/0205405/) for undirected graphs. assortativity :: (Eq vertexTypeIncoming, Eq vertexTypeOutgoing) => Graph d (vertexTypeIncoming, vertexTypeOutgoing, a) -> Bool -- ^ whether to consider edge directions for directed graphs. It is -- ignored for undirected graphs -> Double assortativity g b = unsafePerformIO $ alloca $ \dp -> do let (all_types_inc, all_types_out) = unzip [ (i,o) | (i,o,_) <- nodes g ] types_inc = map fst $ zip [(0 :: Int)..] (nub all_types_inc) types_out = map fst $ zip [(0 :: Int)..] (nub all_types_out) v1 <- listToVector types_inc v2 <- listToVector types_out _e <- withGraph g $ \gp -> withVector v1 $ \vp1 -> withVector v2 $ \vp2 -> c_igraph_assortativity gp vp1 vp2 dp b realToFrac `fmap` peek dp foreign import ccall "igraph_assortativity_degree" c_igraph_assortativity_degree :: GraphPtr -> Ptr CDouble -> Bool -> IO CInt -- | 14\.3\. `igraph_assortativity_degree` — Assortativity of a graph based on vertex -- degree -- -- Assortativity based on vertex degree, please see the discussion at the -- documentation of igraph_assortativity() for details. assortativityDegree :: Graph d a -> Bool -- ^ whether to consider edge directions for directed graphs. This -- argument is ignored for undirected graphs. Supply `True` here to -- do the natural thing, i.e. use directed version of the measure for -- directed graphs and the undirected version for undirected graphs. -> Double assortativityDegree g b = unsafePerformIO $ alloca $ \dp -> do _e <- withGraph g $ \gp -> c_igraph_assortativity_degree gp dp b realToFrac `fmap` peek dp -------------------------------------------------------------------------------- -- 13.15 K-Cores foreign import ccall "igraph_coreness" c_igraph_coreness :: GraphPtr -> VectorPtr -> CInt -> IO CInt -- | 15\.1\. `igraph_coreness` — Finding the coreness of the vertices in a network. -- -- The k-core of a graph is a maximal subgraph in which each vertex has at least -- degree k. (Degree here means the degree in the subgraph of course.). The -- coreness of a vertex is the highest order of a k-core containing the vertex. -- -- This function implements the algorithm presented in Vladimir Batagelj, Matjaz -- Zaversnik: An O(m) Algorithm for Cores Decomposition of Networks. coreness :: Graph d a -> [(Double, a)] coreness g = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_coreness gp vp (getNeiMode g) r <- vectorToList v return $ zip r (nodes g) -------------------------------------------------------------------------------- -- 13.16 Topological sorting, directed acyclic graphs foreign import ccall "igraph_is_dag" c_igraph_is_dag :: GraphPtr -> Ptr Bool -> IO CInt -- | 16\.1\. `igraph_is_dag` — Checks whether a graph is a directed acyclic graph -- (DAG) or not. -- -- A directed acyclic graph (DAG) is a directed graph with no cycles. isDAG :: Graph d a -> Bool isDAG g = unsafePerformIO $ alloca $ \bp -> do _e <- withGraph g $ \gp -> c_igraph_is_dag gp bp peek bp foreign import ccall "igraph_topological_sorting" c_igraph_topological_sorting :: GraphPtr -> VectorPtr -> CInt -> IO CInt -- | 16\.2\. `igraph_topological_sorting` — Calculate a possible topological sorting -- of the graph. -- -- A topological sorting of a directed acyclic graph is a linear ordering of its -- nodes where each node comes before all nodes to which it has edges. Every DAG -- has at least one topological sort, and may have many. This function returns a -- possible topological sort among them. If the graph is not acyclic (it has at -- least one cycle), a partial topological sort is returned and a warning is -- issued. topologicalSorting :: Graph d a -> [a] topologicalSorting g = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_topological_sorting gp vp (getNeiMode g) vectorToVertices g v foreign import ccall "igraph_feedback_arc_set" c_igraph_feedback_arc_set :: GraphPtr -> VectorPtr -> VectorPtr -> CInt -> IO CInt -- | 16\.3\. `igraph_feedback_arc_set` — Calculates a feedback arc set of the graph -- using different -- -- A feedback arc set is a set of edges whose removal makes the graph acyclic. -- We are usually interested in minimum feedback arc sets, i.e. sets of edges -- whose total weight is minimal among all the feedback arc sets. -- -- For undirected graphs, the problem is simple: one has to find a maximum -- weight spanning tree and then remove all the edges not in the spanning tree. -- For directed graphs, this is an NP-hard problem, and various heuristics are -- usually used to find an approximate solution to the problem. This function -- implements a few of these heuristics. feedbackArcSet :: Graph d a -> FASAlgorithm -> [a] feedbackArcSet g algo = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> withOptionalWeights g $ \wp -> c_igraph_feedback_arc_set gp vp wp (fromIntegral $ fromEnum algo) vectorToVertices g v -------------------------------------------------------------------------------- -- 13.17 Maximum cardinality search, graph decomposition, chordal graphs foreign import ccall "igraph_maximum_cardinality_search" c_igraph_maximum_cardinality_search :: GraphPtr -> VectorPtr -> VectorPtr -> IO CInt -- | 17\.1\. `igraph_maximum_cardinality_search` — Maximum cardinality search -- -- This function implements the maximum cardinality search algorithm discussed -- in Robert E Tarjan and Mihalis Yannakakis: Simple linear-time algorithms to -- test chordality of graphs, test acyclicity of hypergraphs, and selectively -- reduce acyclic hypergraphs. SIAM Journal of Computation 13, 566--579, 1984. maximumCardinalitySearch :: Graph d a -> [(Int, a)] maximumCardinalitySearch g = unsafePerformIO $ do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_maximum_cardinality_search gp vp nullPtr r <- vectorToList v return $ zip (map round r) (nodes g) foreign import ccall "igraph_is_chordal" c_igraph_is_chordal :: GraphPtr -> VectorPtr -> VectorPtr -> Ptr Bool -> VectorPtr -> GraphPtr -> IO CInt -- | 17\.2\. `igraph_is_chordal` — Decides whether a graph is chordal -- -- A graph is chordal if each of its cycles of four or more nodes has a chord, -- which is an edge joining two nodes that are not adjacent in the cycle. An -- equivalent definition is that any chordless cycles have at most three nodes. isChordal :: Graph d a -> (Bool, [Edge d a]) -- ^ returns a list of fill-in edges to make the graph chordal isChordal g@(G _) = unsafePerformIO $ alloca $ \bp -> do v <- newVector 0 _e <- withGraph g $ \gp -> withVector v $ \vp -> c_igraph_is_chordal gp nullPtr nullPtr bp vp nullPtr b <- peek bp as <- vectorToVertices g v let mkEdges (f:t:r) = (toEdge f t : mkEdges r) mkEdges [] = [] mkEdges [_] = error "Error in `isChordal': Invalid number of arguments to `mkEdges'" return (b, mkEdges as) -------------------------------------------------------------------------------- -- 13.18 Matchings -------------------------------------------------------------------------------- -- 13.19 Line graphs -------------------------------------------------------------------------------- -- 13.20 Unfolding a graph into a tree -------------------------------------------------------------------------------- -- 13.21 Other Operations