{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}

-- | GraphClassifier defines the shared vocabulary for categorizing pattern structures.
module Pattern.Graph.GraphClassifier
  ( GraphClass(..)
  , GraphClassifier(..)
  , classifyByShape
  , canonicalClassifier
  , GraphValue(..)
  ) where

import Pattern.Core (Pattern(..))

-- | Typeclass providing identity and classification for the value type @v@.
-- Used to classify patterns as Node/Annotation/Relationship/Walk/Unrecognized.
class Ord (Id v) => GraphValue v where
  type Id v
  identify :: v -> Id v

-- | Represents the five structural categories of graph elements.
-- 'GOther' allows open extension.
data GraphClass extra
  = GNode
  | GRelationship
  | GAnnotation
  | GWalk
  | GOther extra
  deriving (GraphClass extra -> GraphClass extra -> Bool
(GraphClass extra -> GraphClass extra -> Bool)
-> (GraphClass extra -> GraphClass extra -> Bool)
-> Eq (GraphClass extra)
forall extra.
Eq extra =>
GraphClass extra -> GraphClass extra -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall extra.
Eq extra =>
GraphClass extra -> GraphClass extra -> Bool
== :: GraphClass extra -> GraphClass extra -> Bool
$c/= :: forall extra.
Eq extra =>
GraphClass extra -> GraphClass extra -> Bool
/= :: GraphClass extra -> GraphClass extra -> Bool
Eq, Int -> GraphClass extra -> ShowS
[GraphClass extra] -> ShowS
GraphClass extra -> String
(Int -> GraphClass extra -> ShowS)
-> (GraphClass extra -> String)
-> ([GraphClass extra] -> ShowS)
-> Show (GraphClass extra)
forall extra. Show extra => Int -> GraphClass extra -> ShowS
forall extra. Show extra => [GraphClass extra] -> ShowS
forall extra. Show extra => GraphClass extra -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall extra. Show extra => Int -> GraphClass extra -> ShowS
showsPrec :: Int -> GraphClass extra -> ShowS
$cshow :: forall extra. Show extra => GraphClass extra -> String
show :: GraphClass extra -> String
$cshowList :: forall extra. Show extra => [GraphClass extra] -> ShowS
showList :: [GraphClass extra] -> ShowS
Show, (forall a b. (a -> b) -> GraphClass a -> GraphClass b)
-> (forall a b. a -> GraphClass b -> GraphClass a)
-> Functor GraphClass
forall a b. a -> GraphClass b -> GraphClass a
forall a b. (a -> b) -> GraphClass a -> GraphClass b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall a b. (a -> b) -> GraphClass a -> GraphClass b
fmap :: forall a b. (a -> b) -> GraphClass a -> GraphClass b
$c<$ :: forall a b. a -> GraphClass b -> GraphClass a
<$ :: forall a b. a -> GraphClass b -> GraphClass a
Functor, Functor GraphClass
Foldable GraphClass
(Functor GraphClass, Foldable GraphClass) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> GraphClass a -> f (GraphClass b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    GraphClass (f a) -> f (GraphClass a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> GraphClass a -> m (GraphClass b))
-> (forall (m :: * -> *) a.
    Monad m =>
    GraphClass (m a) -> m (GraphClass a))
-> Traversable GraphClass
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a.
Monad m =>
GraphClass (m a) -> m (GraphClass a)
forall (f :: * -> *) a.
Applicative f =>
GraphClass (f a) -> f (GraphClass a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> GraphClass a -> m (GraphClass b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> GraphClass a -> f (GraphClass b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> GraphClass a -> f (GraphClass b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> GraphClass a -> f (GraphClass b)
$csequenceA :: forall (f :: * -> *) a.
Applicative f =>
GraphClass (f a) -> f (GraphClass a)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
GraphClass (f a) -> f (GraphClass a)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> GraphClass a -> m (GraphClass b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> GraphClass a -> m (GraphClass b)
$csequence :: forall (m :: * -> *) a.
Monad m =>
GraphClass (m a) -> m (GraphClass a)
sequence :: forall (m :: * -> *) a.
Monad m =>
GraphClass (m a) -> m (GraphClass a)
Traversable, (forall m. Monoid m => GraphClass m -> m)
-> (forall m a. Monoid m => (a -> m) -> GraphClass a -> m)
-> (forall m a. Monoid m => (a -> m) -> GraphClass a -> m)
-> (forall a b. (a -> b -> b) -> b -> GraphClass a -> b)
-> (forall a b. (a -> b -> b) -> b -> GraphClass a -> b)
-> (forall b a. (b -> a -> b) -> b -> GraphClass a -> b)
-> (forall b a. (b -> a -> b) -> b -> GraphClass a -> b)
-> (forall a. (a -> a -> a) -> GraphClass a -> a)
-> (forall a. (a -> a -> a) -> GraphClass a -> a)
-> (forall a. GraphClass a -> [a])
-> (forall a. GraphClass a -> Bool)
-> (forall a. GraphClass a -> Int)
-> (forall a. Eq a => a -> GraphClass a -> Bool)
-> (forall a. Ord a => GraphClass a -> a)
-> (forall a. Ord a => GraphClass a -> a)
-> (forall a. Num a => GraphClass a -> a)
-> (forall a. Num a => GraphClass a -> a)
-> Foldable GraphClass
forall a. Eq a => a -> GraphClass a -> Bool
forall a. Num a => GraphClass a -> a
forall a. Ord a => GraphClass a -> a
forall m. Monoid m => GraphClass m -> m
forall a. GraphClass a -> Bool
forall a. GraphClass a -> Int
forall a. GraphClass a -> [a]
forall a. (a -> a -> a) -> GraphClass a -> a
forall m a. Monoid m => (a -> m) -> GraphClass a -> m
forall b a. (b -> a -> b) -> b -> GraphClass a -> b
forall a b. (a -> b -> b) -> b -> GraphClass a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall m. Monoid m => GraphClass m -> m
fold :: forall m. Monoid m => GraphClass m -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> GraphClass a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> GraphClass a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> GraphClass a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> GraphClass a -> m
$cfoldr :: forall a b. (a -> b -> b) -> b -> GraphClass a -> b
foldr :: forall a b. (a -> b -> b) -> b -> GraphClass a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> GraphClass a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> GraphClass a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> GraphClass a -> b
foldl :: forall b a. (b -> a -> b) -> b -> GraphClass a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> GraphClass a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> GraphClass a -> b
$cfoldr1 :: forall a. (a -> a -> a) -> GraphClass a -> a
foldr1 :: forall a. (a -> a -> a) -> GraphClass a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> GraphClass a -> a
foldl1 :: forall a. (a -> a -> a) -> GraphClass a -> a
$ctoList :: forall a. GraphClass a -> [a]
toList :: forall a. GraphClass a -> [a]
$cnull :: forall a. GraphClass a -> Bool
null :: forall a. GraphClass a -> Bool
$clength :: forall a. GraphClass a -> Int
length :: forall a. GraphClass a -> Int
$celem :: forall a. Eq a => a -> GraphClass a -> Bool
elem :: forall a. Eq a => a -> GraphClass a -> Bool
$cmaximum :: forall a. Ord a => GraphClass a -> a
maximum :: forall a. Ord a => GraphClass a -> a
$cminimum :: forall a. Ord a => GraphClass a -> a
minimum :: forall a. Ord a => GraphClass a -> a
$csum :: forall a. Num a => GraphClass a -> a
sum :: forall a. Num a => GraphClass a -> a
$cproduct :: forall a. Num a => GraphClass a -> a
product :: forall a. Num a => GraphClass a -> a
Foldable)

-- | Pluggable record of functions defining the categorization logic.
data GraphClassifier extra v = GraphClassifier
  { forall extra v.
GraphClassifier extra v -> Pattern v -> GraphClass extra
classify :: Pattern v -> GraphClass extra
  }

-- | Default classification logic based on the shape/arity of the pattern.
-- Falls back to 'GOther ()' for patterns that don't match standard graph structures.
classifyByShape :: GraphValue v => Pattern v -> GraphClass ()
classifyByShape :: forall v. GraphValue v => Pattern v -> GraphClass ()
classifyByShape (Pattern v
_ [Pattern v]
els)
  | [Pattern v] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Pattern v]
els = GraphClass ()
forall extra. GraphClass extra
GNode
  | [Pattern v] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Pattern v]
els Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 = GraphClass ()
forall extra. GraphClass extra
GAnnotation
  | [Pattern v] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Pattern v]
els Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
2 Bool -> Bool -> Bool
&& (Pattern v -> Bool) -> [Pattern v] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Pattern v -> Bool
forall {v}. Pattern v -> Bool
isNodeLike [Pattern v]
els = GraphClass ()
forall extra. GraphClass extra
GRelationship
  | [Pattern v] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Pattern v]
els Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
1 Bool -> Bool -> Bool
&& (Pattern v -> Bool) -> [Pattern v] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Pattern v -> Bool
forall {v}. Pattern v -> Bool
isRelationshipLike [Pattern v]
els Bool -> Bool -> Bool
&& [Pattern v] -> Bool
forall v. GraphValue v => [Pattern v] -> Bool
isValidWalk [Pattern v]
els = GraphClass ()
forall extra. GraphClass extra
GWalk
  | Bool
otherwise = () -> GraphClass ()
forall extra. extra -> GraphClass extra
GOther ()
  where
    isNodeLike :: Pattern v -> Bool
isNodeLike (Pattern v
_ [Pattern v]
inner) = [Pattern v] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Pattern v]
inner
    isRelationshipLike :: Pattern v -> Bool
isRelationshipLike (Pattern v
_ [Pattern v]
inner) = [Pattern v] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Pattern v]
inner Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
2 Bool -> Bool -> Bool
&& (Pattern v -> Bool) -> [Pattern v] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Pattern v -> Bool
forall {v}. Pattern v -> Bool
isNodeLike [Pattern v]
inner

-- | Determines if a sequence of relationships forms a valid walk.
-- Consecutive relationships must share at least one node (ignoring direction),
-- and must chain end-to-end.
isValidWalk :: GraphValue v => [Pattern v] -> Bool
isValidWalk :: forall v. GraphValue v => [Pattern v] -> Bool
isValidWalk [] = Bool
False
isValidWalk [Pattern v]
rels = Bool -> Bool
not ([Pattern v] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null (([Pattern v] -> Pattern v -> [Pattern v])
-> [Pattern v] -> [Pattern v] -> [Pattern v]
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl [Pattern v] -> Pattern v -> [Pattern v]
forall {v} {v}.
(Id v ~ Id v, GraphValue v, GraphValue v) =>
[Pattern v] -> Pattern v -> [Pattern v]
step [] [Pattern v]
rels))
  where
    step :: [Pattern v] -> Pattern v -> [Pattern v]
step [] (Pattern v
_ [Pattern v
a, Pattern v
b]) = [Pattern v
a, Pattern v
b]
    step [Pattern v]
active (Pattern v
_ [Pattern v
a, Pattern v
b]) =
      let fromA :: [Pattern v]
fromA = if (Pattern v -> Bool) -> [Pattern v] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (\Pattern v
x -> v -> Id v
forall v. GraphValue v => v -> Id v
identify (Pattern v -> v
forall v. Pattern v -> v
value Pattern v
a) Id v -> Id v -> Bool
forall a. Eq a => a -> a -> Bool
== v -> Id v
forall v. GraphValue v => v -> Id v
identify (Pattern v -> v
forall v. Pattern v -> v
value Pattern v
x)) [Pattern v]
active then [Pattern v
b] else []
          fromB :: [Pattern v]
fromB = if (Pattern v -> Bool) -> [Pattern v] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (\Pattern v
x -> v -> Id v
forall v. GraphValue v => v -> Id v
identify (Pattern v -> v
forall v. Pattern v -> v
value Pattern v
b) Id v -> Id v -> Bool
forall a. Eq a => a -> a -> Bool
== v -> Id v
forall v. GraphValue v => v -> Id v
identify (Pattern v -> v
forall v. Pattern v -> v
value Pattern v
x)) [Pattern v]
active then [Pattern v
a] else []
      in [Pattern v]
fromA [Pattern v] -> [Pattern v] -> [Pattern v]
forall a. [a] -> [a] -> [a]
++ [Pattern v]
fromB
    step [Pattern v]
_ Pattern v
_ = []

-- | The standard classifier used for canonical graph construction.
canonicalClassifier :: GraphValue v => GraphClassifier () v
canonicalClassifier :: forall v. GraphValue v => GraphClassifier () v
canonicalClassifier = GraphClassifier
  { classify :: Pattern v -> GraphClass ()
classify = Pattern v -> GraphClass ()
forall v. GraphValue v => Pattern v -> GraphClass ()
classifyByShape
  }