{-# LANGUAGE TypeFamilies, EmptyDataDecls, TypeOperators, FlexibleInstances, MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleContexts #-}
-- |
-- Module : GraphHammer.TriangleCount
-- Copyright : (C) 2013 Parallel Scientific Labs, LLC.
-- License : GPLv2
--
--
-- Computing number of the triangles that can be built with respect to each
-- node.
--
-- A /triangle/ exists when a vertex has two adjacent vertexes that are
-- also adjacent to each other.
--
-- An example of such problem is a friendship in a social graph where
-- triangle is a minimal unit of friendship relations.
module GraphHammer.TriangleCount(
TriangleCount(..)
, triangleCount
) where
import GraphHammer
import GraphHammer.VertexDegree
-------------------------------------------------------------------------------
-- Typical derived analysis.
-- Closed triangle count.
-- |The name of analysis.
data TriangleCount = TriangleCount
-- |What analyses are required to be done before ours.
type instance RequiredAnalyses TriangleCount = VertexDegree :. Nil
-- | Run triangle analysis:
--
-- For each node calculate number of triangles that can be built starting
-- from the node.
triangleCount :: (EnabledAnalyses (TriangleCount :. VertexDegree :.Nil) wholeset
, EnabledAnalysis VertexDegree wholeset) =>
Analysis (TriangleCount :. VertexDegree :. Nil) wholeset
triangleCount = derivedAnalysis vertexDegree TriangleCount $ \tc from to -> do
count <- localValue 0
onIntersectingNeighbors from to $ \neighbor -> do
-- atomically update both nodes neighbor's triangle count.
incrementAnalysisResult tc neighbor (cst 1)
count $= count +. cst 1
-- atomically update ours triangle count.
incrementAnalysisResult tc from count
incrementAnalysisResult tc to count
return ()
onIntersectingNeighbors :: Value Composed Index -> Value Composed Index
-> (Value Composed Index -> AnM as ()) -> AnM as ()
onIntersectingNeighbors u v action = do
onEdges u $
\x -> onEdges v $
\y -> anIf (x === y) (action x) (return ())