swish- A semantic web toolkit.

MaintainerDouglas Burke



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



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.


PartitionedGraph [GraphPartition lb] 


data GraphPartition lb Source


PartObj lb 
PartSub lb [(lb, GraphPartition lb)] 


Label lb => Eq (GraphPartition lb) 
Label lb => Show (GraphPartition lb) 

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:

  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.