math-grads-0.1.6.7: Library containing graph data structures and graph algorithms

Safe HaskellNone
LanguageHaskell2010

Math.Grads.Algo.Isomorphism

Description

Module that provides functions for identifying graph/subgraph isomorphism.

Synopsis

Documentation

type EComparator e1 e2 = GraphEdge e1 -> GraphEdge e2 -> Bool Source #

Function that checks whether two edges are identical. Due to properties related to index of vertex, like belonging to a cycle, we consider GraphEdge (Int, Int, e) instead of e.

type VComparator v1 v2 = VertexIndex -> VertexIndex -> Bool Source #

Function that checks whether two vertices are identical. Due to properties related to index of vertex, like number of neighbors, we consider vertex indices instead of vertices.

class (Graph g1, Graph g2) => GComparable g1 v1 e1 g2 v2 e2 where Source #

Type class for graphs that could be checked for isomorphism.

Methods

vComparator :: g1 v1 e1 -> g2 v2 e2 -> VComparator v1 v2 Source #

eComparator :: g1 v1 e1 -> g2 v2 e2 -> EComparator e1 e2 Source #

type VertexIndex = Int Source #

Type alias for Int.

getIso Source #

Arguments

:: (Ord v1, Ord v2, GComparable GenericGraph v1 e1 GenericGraph v2 e2, Eq e1, Eq e2) 
=> GenericGraph v1 e1

queryGraph

-> GenericGraph v2 e2

targetGraph

-> Maybe (Map Int Int) 

Get one vertices matching (if exists) from queryGraph to targetGraph.

getMultiIso Source #

Arguments

:: (Ord v1, Ord v2, GComparable GenericGraph v1 e1 GenericGraph v2 e2, Eq e1, Eq e2) 
=> GenericGraph v1 e1

queryGraph

-> GenericGraph v2 e2

targetGraph

-> [Map Int Int] 

Get all possible vertices matchings from queryGraph to targetGraph.

isIso :: (Ord v1, Ord v2, GComparable GenericGraph v1 e1 GenericGraph v2 e2, Eq e1, Eq e2) => GenericGraph v1 e1 -> GenericGraph v2 e2 -> Bool Source #

Checks whether two graphs are isomorphic.

isIsoSub Source #

Arguments

:: (Ord v1, Ord v2, GComparable GenericGraph v1 e1 GenericGraph v2 e2, Eq e1, Eq e2) 
=> GenericGraph v1 e1

queryGraph

-> GenericGraph v2 e2

targetGraph

-> Bool 

Check for queryGraph \( \subseteq \) targetGraph.