| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Math.Grads.Algo.Isomorphism
Description
Module that provides functions for identifying graph/subgraph isomorphism.
Synopsis
- type EComparator e1 e2 = GraphEdge e1 -> GraphEdge e2 -> Bool
- type VComparator v1 v2 = VertexIndex -> VertexIndex -> Bool
- class (Graph g1, Graph g2) => GComparable g1 v1 e1 g2 v2 e2 where
- vComparator :: g1 v1 e1 -> g2 v2 e2 -> VComparator v1 v2
- eComparator :: g1 v1 e1 -> g2 v2 e2 -> EComparator e1 e2
- type VertexIndex = Int
- getIso :: (Ord v1, Ord v2, GComparable GenericGraph v1 e1 GenericGraph v2 e2, Eq e1, Eq e2) => GenericGraph v1 e1 -> GenericGraph v2 e2 -> Maybe (Map Int Int)
- getMultiIso :: (Ord v1, Ord v2, GComparable GenericGraph v1 e1 GenericGraph v2 e2, Eq e1, Eq e2) => GenericGraph v1 e1 -> GenericGraph v2 e2 -> [Map Int Int]
- isIso :: (Ord v1, Ord v2, GComparable GenericGraph v1 e1 GenericGraph v2 e2, Eq e1, Eq e2) => GenericGraph v1 e1 -> GenericGraph v2 e2 -> Bool
- isIsoSub :: (Ord v1, Ord v2, GComparable GenericGraph v1 e1 GenericGraph v2 e2, Eq e1, Eq e2) => GenericGraph v1 e1 -> GenericGraph v2 e2 -> Bool
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.
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.
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.
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.