Portability | H98 |
---|---|

Stability | experimental |

Maintainer | Douglas Burke |

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

- data PartitionedGraph lb = PartitionedGraph [GraphPartition lb]
- getArcs :: PartitionedGraph lb -> [Arc lb]
- getPartitions :: PartitionedGraph lb -> [GraphPartition lb]
- data GraphPartition lb
- = PartObj lb
- | PartSub lb [(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:

Label lb => Eq (PartitionedGraph lb) | |

Label lb => Show (PartitionedGraph lb) |

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

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

data GraphPartition lb Source

PartObj lb | |

PartSub lb [(lb, GraphPartition lb)] |

Label lb => Eq (GraphPartition lb) | |

Label lb => Show (GraphPartition lb) |

node :: GraphPartition lb -> lbSource

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

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

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

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