Swish.GraphPartition

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

Documentation

data PartitionedGraph lb

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)

Defined in Swish.GraphPartition

Methods

(==) :: PartitionedGraph lb -> PartitionedGraph lb -> Bool

(/=) :: PartitionedGraph lb -> PartitionedGraph lb -> Bool

Label lb => Show (PartitionedGraph lb)

Defined in Swish.GraphPartition

Methods

showsPrec :: Int -> PartitionedGraph lb -> ShowS

show :: PartitionedGraph lb -> String

showList :: [PartitionedGraph lb] -> ShowS

getArcs :: PartitionedGraph lb -> [Arc lb]

Returns all the arcs in the partitioned graph.

getPartitions :: PartitionedGraph lb -> [GraphPartition lb]

Returns a list of partitions.

data GraphPartition lb

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)

Equality is based on total structural equivalence rather than graph equality.

Defined in Swish.GraphPartition

Methods

(==) :: GraphPartition lb -> GraphPartition lb -> Bool

(/=) :: GraphPartition lb -> GraphPartition lb -> Bool

Label lb => Ord (GraphPartition lb)

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)

Defined in Swish.GraphPartition

Methods

showsPrec :: Int -> GraphPartition lb -> ShowS

show :: GraphPartition lb -> String

showList :: [GraphPartition lb] -> ShowS

node :: GraphPartition lb -> lb

Returns the node for the partition.

toArcs :: GraphPartition lb -> [Arc lb]

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

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

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:

1. isolating differences between graphs
2. 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))]

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

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

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