Copyright	(c) 2003 Graham Klyne 2009 Vasili I Galchin 2011 2012 Douglas Burke
License	GPL V2
Maintainer	Douglas Burke
Stability	experimental
Portability	H98
Safe Haskell	Safe
Language	Haskell98

Swish.GraphPartition

Description

This module contains functions for partitioning a graph into subgraphs that rooted from different subject nodes.

Synopsis

data PartitionedGraph lb = PartitionedGraph [GraphPartition lb]
getArcs :: PartitionedGraph lb -> [Arc lb]
getPartitions :: PartitionedGraph lb -> [GraphPartition lb]
data GraphPartition lb
- = PartObj lb
- | PartSub lb (NonEmpty (lb, GraphPartition lb))
node :: GraphPartition lb -> lb
toArcs :: GraphPartition lb -> [Arc lb]
partitionGraph :: Label lb => [Arc lb] -> PartitionedGraph lb
comparePartitions :: Label lb => PartitionedGraph lb -> PartitionedGraph lb -> [(Maybe (GraphPartition lb), Maybe (GraphPartition lb))]
partitionShowP :: Label lb => String -> GraphPartition lb -> String

Documentation

data PartitionedGraph lb Source #

Representation of a graph as a collection of (possibly nested) partitions. Each node in the graph appears at least once as the root value of a GraphPartition value:

Nodes that are the subject of at least one statement appear as the first value of exactly one PartSub constructor, and may also appear in any number of PartObj constructors.
Nodes appearing only as objects of statements appear only in PartObj constructors.

Constructors

PartitionedGraph [GraphPartition lb]

Instances

Label lb => Eq (PartitionedGraph lb) Source #
Instance details Defined in Swish.GraphPartition Methods (==) :: PartitionedGraph lb -> PartitionedGraph lb -> Bool # (/=) :: PartitionedGraph lb -> PartitionedGraph lb -> Bool #
Label lb => Show (PartitionedGraph lb) Source #
Instance details Defined in Swish.GraphPartition Methods showsPrec :: Int -> PartitionedGraph lb -> ShowS # show :: PartitionedGraph lb -> String # showList :: [PartitionedGraph lb] -> ShowS #

getArcs :: PartitionedGraph lb -> [Arc lb] Source #

Returns all the arcs in the partitioned graph.

getPartitions :: PartitionedGraph lb -> [GraphPartition lb] Source #

Returns a list of partitions.

data GraphPartition lb Source #

Represent a partition of a graph by a node and (optional) contents.

Constructors

PartObj lb
PartSub lb (NonEmpty (lb, GraphPartition lb))

Instances

Label lb => Eq (GraphPartition lb) Source #	Equality is based on total structural equivalence rather than graph equality.
Instance details Defined in Swish.GraphPartition Methods (==) :: GraphPartition lb -> GraphPartition lb -> Bool # (/=) :: GraphPartition lb -> GraphPartition lb -> Bool #
Label lb => Ord (GraphPartition lb) Source #
Instance details Defined in Swish.GraphPartition Methods compare :: GraphPartition lb -> GraphPartition lb -> Ordering # (<) :: GraphPartition lb -> GraphPartition lb -> Bool # (<=) :: GraphPartition lb -> GraphPartition lb -> Bool # (>) :: GraphPartition lb -> GraphPartition lb -> Bool # (>=) :: GraphPartition lb -> GraphPartition lb -> Bool # max :: GraphPartition lb -> GraphPartition lb -> GraphPartition lb # min :: GraphPartition lb -> GraphPartition lb -> GraphPartition lb #
Label lb => Show (GraphPartition lb) Source #
Instance details Defined in Swish.GraphPartition Methods showsPrec :: Int -> GraphPartition lb -> ShowS # show :: GraphPartition lb -> String # showList :: [GraphPartition lb] -> ShowS #

node :: GraphPartition lb -> lb Source #

Returns the node for the partition.

toArcs :: GraphPartition lb -> [Arc lb] Source #

Creates a list of arcs from the partition. The empty list is returned for PartObj.

partitionGraph :: Label lb => [Arc lb] -> PartitionedGraph lb Source #

Turning a partitioned graph into a flat graph is easy. The interesting challenge is to turn a flat graph into a partitioned graph that is more useful for certain purposes. Currently, I'm interested in:

isolating differences between graphs
pretty-printing graphs

For (1), the goal is to separate subgraphs that are known to be equivalent from subgraphs that are known to be different, such that:

different sub-graphs are minimized,
different sub-graphs are placed into 1:1 correspondence (possibly with null subgraphs), and
only deterministic matching decisions are made.

For (2), the goal is to decide when a subgraph is to be treated as nested in another partition, or treated as a new top-level partition. If a subgraph is referenced by exactly one graph partition, it should be nested in that partition, otherwise it should be a new top-level partition.

Strategy. Examining just subject and object nodes:

all non-blank subject nodes are the root of a top-level partition
blank subject nodes that are not the object of exactly one statement are the root of a top-level partition.
blank nodes referenced as the object of exactly 1 statement of an existing partition are the root of a sub-partition of the refering partition.
what remain are circular chains of blank nodes not referenced elsewhere: for each such chain, pick a root node arbitrarily.

comparePartitions :: Label lb => PartitionedGraph lb -> PartitionedGraph lb -> [(Maybe (GraphPartition lb), Maybe (GraphPartition lb))] Source #

Create a list of pairs of corresponding Partitions that are unequal.

partitionShowP :: Label lb => String -> GraphPartition lb -> String Source #

Convert a partition into a string with a leading separator string.