| Copyright | (c) 2003 Graham Klyne 2009 Vasili I Galchin 2011 2012 2022 2024 Douglas Burke |
|---|---|
| License | GPL V2 |
| Maintainer | Douglas Burke |
| Stability | experimental |
| Portability | CPP, DerivingStrategies |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
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:
Constructors
| PartitionedGraph [GraphPartition lb] |
Instances
| Label lb => Show (PartitionedGraph lb) Source # | |
Defined in Swish.GraphPartition Methods showsPrec :: Int -> PartitionedGraph lb -> ShowS # show :: PartitionedGraph lb -> String # showList :: [PartitionedGraph lb] -> ShowS # | |
| Label lb => Eq (PartitionedGraph lb) Source # | |
Defined in Swish.GraphPartition Methods (==) :: PartitionedGraph lb -> PartitionedGraph lb -> Bool # (/=) :: PartitionedGraph lb -> PartitionedGraph lb -> Bool # | |
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 => Show (GraphPartition lb) Source # | |
Defined in Swish.GraphPartition Methods showsPrec :: Int -> GraphPartition lb -> ShowS # show :: GraphPartition lb -> String # showList :: [GraphPartition lb] -> ShowS # | |
| Label lb => Eq (GraphPartition lb) Source # | 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) Source # | |
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 # | |
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.