Partitioned graphs

module PartitionedGraphs

A library for partitioned graphs and their quotients.

This module provides data structures and functionalities to work with partitioned graphs, including quotient vertices and edges, as well as views of partitioned graphs. It defines an abstract supertype AbstractPartitionedGraph for graphs that have some notion of a non-trivial partitioning of their vertices. It also provides a interface of functions that can be overloaded on any subtype of Graphs.AbstractGraph to make this subtype behave like a partitioned graph, without itself subtyping AbstractPartitionedGraph.

It defines the following concrete types:

• QuotientVertex: Represents a vertex in the quotient graph.
• QuotientEdge: Represents an edge in the quotient graph.
• PartitionedView: A lightweight view of a partitioned graph.
• PartitionedGraph: An implementation of a partitioned graph with extra caching not provided by PartitionedView.
• QuotientView: A view of the quotient graph derived from a partitioned graph. It provides the following functions:
• partitionedgraph: Partitions an AbstractGraph.
• departition: Removes a single layer of partitioning from a partitioned graph.
• unpartition: Recursively removes all layers of partitioning from a partitioned graph.

Interfaces

For a type MyGraphType{V} <: Graphs.AbstractGraph{V}, to have a non-trivial partitioning then the interface can be summarized as follows:

# 1. If you want a non-trivial partitioning, then overload the method:
partitioned_vertices(g::MyGraphType)

# 2a. For fast quotient graph construction and fast `has_edge` at the quotient_graph level:
quotient_graph(g::MyGraphType)
# 2b. If Julia is unable to infer the returned type of `quotient_graph` then you should
# also define the `quotient_graph_type` function:
quotient_graph_type(g::MyGraphType)

# 3. For a fast vertex to quotient-vertex map then:
quotientvertex(g::MyGraphType, vertex)
# ...which automatically gives a fast edge to quotient-edge map via:
quotientedge(g, edge) # no need to overload this.

# 4. For fast finding of edge partitions: 
partitioned_edges(g::MyGraphType)

If any of the above properties are desirable for MyGraphType, then store the data in a field and overload the associated function to get that field, e.g.

quotientvertex(g::MyGraphType, vertex) = g.inverse_vertex_map[vertex]

where we have chosen to store the map in the field inverse_vertex_map of the MyGraphType type. Doing this is not essential as everything can and will be derived from partitioned_vertices as a fallback.

Interface for adding and removing vertices

For a given partitioned graph, all vertices must live in a quotient vertex and there should be no empty quotient vertices. The methods:

Graphs.rem_vertex!(g::MyGraphType, vertex)
Graphs.add_edge!(g::MyGraphType, edge)
Graphs.rem_edge!(g::MyGraphType, edge)

should be overloaded to ensure that these properties are maintained for the particular implementation of MyGraphType. Note, that the method:

Graphs.add_vertex!(g::MyGraphType, vertex)

is not supported for partitioned graphs as it is ambiguous which quotient vertex the new vertex should belong to. To add a vertex to a partitioned graph, one should define the method:

Graphs.add_subquotientvertex!(g::MyGraphType, quotientvertex::QuotientVertex, vertex)

Doing so enables the syntax:

Graphs.add_vertex!(graph, QuotientVertex(quotientvertex)[vertex])

for adding vertex to the quotient vertex quotientvertex in the partitioned graph.

abstract type AbstractPartitionedGraph{V, PV} <: AbstractNamedGraph{V}

Supertype for named graphs that carry a partitioning of their vertices, with vertex type V and quotient vertex type PV.

A subtype must define unpartitioned_graph, returning the underlying graph without any partitioning, on top of the partitioned-graph interface documented in PartitionedGraphs. Note that interface can also be implemented by a graph type that does not subtype AbstractPartitionedGraph.

PartitionedGraph(graph::AbstractGraph, partitioned_vertices)
PartitionedGraph(partitioned_vertices)
PartitionedGraph(graph::AbstractGraph; kwargs...)

A graph together with a partitioning of its vertices into quotient vertices. It caches the quotient graph and the vertex to quotient vertex map, so quotient level queries do not search the partitioning. PartitionedView is the alternative that stores neither.

The vertices of graph are partitioned according to partitioned_vertices, whose keys are the quotient vertices and whose values are the sets of vertices in each partition. It can be a Dictionaries.Dictionary, a Dict, or a vector of vertex collections keyed by 1:length(partitioned_vertices). Every vertex must land in exactly one quotient vertex.

Passing partitioned_vertices alone gives the discrete partitioning of an edgeless graph. Passing graph alone partitions with partition_vertices, which the keyword arguments go to: it needs either npartitions or nvertices_per_partition, and a backend such as Metis.jl loaded.

Examples

julia> using Graphs: ne, nv, path_graph, vertices

julia> using NamedGraphs: NamedGraph

julia> using NamedGraphs.PartitionedGraphs: PartitionedGraph, QuotientVertex, QuotientView

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> pg = PartitionedGraph(g, [["a", "b"], ["c", "d"]]);

julia> (nv(pg), ne(pg))
(4, 3)

julia> vertices(pg, QuotientVertex(1))
2-element Vector{String}:
 "a"
 "b"

julia> (nv(QuotientView(pg)), ne(QuotientView(pg)))
(2, 1)

PartitionedView(graph::AbstractGraph, partitioned_vertices)

A lightweight view of graph as a partitioned graph. See PartitionedGraph for the accepted forms of partitioned_vertices.

Unlike PartitionedGraph, it stores nothing beyond graph and partitioned_vertices, recomputing the quotient graph and the vertex to quotient vertex map on each use, so it is cheaper to construct but slower to query at the quotient level.

Examples

julia> using Graphs: ne, nv, path_graph

julia> using NamedGraphs: NamedGraph

julia> using NamedGraphs.PartitionedGraphs: PartitionedView, QuotientView

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> pv = PartitionedView(g, [["a", "b"], ["c", "d"]]);

julia> (nv(pv), ne(pv))
(4, 3)

julia> (nv(QuotientView(pv)), ne(QuotientView(pv)))
(2, 1)

partitionedgraph(graph::AbstractGraph, partitioned_vertices) -> PartitionedGraph

The function form of the PartitionedGraph constructor, which documents the accepted forms of partitioned_vertices.

graph may itself be a partitioned graph, giving two layers of partitioning, which departition and unpartition remove.

departition(graph::AbstractGraph)

The graph underlying graph with a single layer of partitioning removed: the graph that was partitioned to make graph, without the partitioning. Graphs that are not an AbstractPartitionedGraph are returned as-is, so departition is the identity on them.

Note that a partitioned graph can itself be partitioned, so removing one layer may leave a graph that is still partitioned. Use unpartition to remove every layer at once.

Examples

julia> using Graphs: path_graph

julia> using NamedGraphs: NamedGraph

julia> using NamedGraphs.PartitionedGraphs: departition, partitionedgraph

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> pg = partitionedgraph(g, [["a", "b"], ["c", "d"]]);

julia> departition(pg) === g
true

julia> departition(g) === g
true

julia> departition(partitionedgraph(pg, [["a", "c"], ["b", "d"]])) === pg
true

unpartition(graph::AbstractGraph)

The graph underlying graph with every layer of partitioning removed, i.e. departition applied repeatedly until the result is no longer partitioned. Graphs that are not an AbstractPartitionedGraph are returned as-is.

Examples

julia> using Graphs: path_graph

julia> using NamedGraphs: NamedGraph

julia> using NamedGraphs.PartitionedGraphs: partitionedgraph, unpartition

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> pg = partitionedgraph(g, [["a", "b"], ["c", "d"]]);

julia> pg2 = partitionedgraph(pg, [["a", "c"], ["b", "d"]]);

julia> unpartition(pg2) === g
true

julia> unpartition(g) === g
true

QuotientView(graph::AbstractGraph)

A view of graph as its quotient graph: the graph whose vertices are the quotient vertices of graph and which has an edge between two quotient vertices whenever graph has an edge between them. Its vertices are the quotient vertices themselves rather than QuotientVertex wrappers, so it can be used with the Graphs.jl interface like any other named graph.

The view is backed by graph, so mutating it mutates graph: removing a vertex of the view removes all of the vertices of graph in that quotient vertex, and removing an edge of the view removes all of the edges of graph between those two quotient vertices.

Any Graphs.AbstractGraph can be viewed this way. A graph with no partitioning defined has the trivial partitioning with all of its vertices in a single quotient vertex, so its quotient graph is a single vertex with no edges.

Examples

julia> using Graphs: edges, ne, nv, path_graph, vertices

julia> using NamedGraphs: NamedEdge, NamedGraph

julia> using NamedGraphs.PartitionedGraphs: PartitionedGraph, QuotientView

julia> g = NamedGraph(path_graph(4), ["a", "b", "c", "d"]);

julia> pg = PartitionedGraph(g, [["a", "b"], ["c", "d"]]);

julia> qg = QuotientView(pg);

julia> collect(vertices(qg))
2-element Vector{Int64}:
 1
 2

julia> collect(edges(qg))
1-element Vector{NamedEdge{Int64}}:
 1 => 2

julia> (nv(QuotientView(g)), ne(QuotientView(g)))
(1, 0)

QuotientVertex(v)

Represents a super-vertex in a partitioned graph corresponding to the set of vertices in partition v.

quotientvertices(g::AbstractGraph, vs = vertices(g))

Return an iterator over unique quotient vertices corresponding to the set vertices vs of the graph pg.

QuotientEdge(e)

Represents a super-edge in a partitioned graph corresponding to the set of edges in between partitions src(e) and dst(e).

quotientedge(g::AbstractGraph{V}, edge) -> QuotientEdge{V}

Return the the quotient edge corresponding to edge of the graph g. Note, the returned quotient edge may be a self-loop.

See also: quotientedges, quotienttvertex.

quotientedges(g::AbstractGraph, es = edges(g)) -> QuotientEdges

Return an iterator over all unique quotient edges corresponding to the set of edges es of the graph g.

boundary_quotientedges(graph::AbstractGraph, quotientvertices; dir = :out)
boundary_quotientedges(graph::AbstractGraph, quotientvertex::QuotientVertex; dir = :out)

The QuotientEdges of graph that connect the given quotient vertices to the quotient vertices outside of them, i.e. the boundary edges of quotientvertices in the quotient graph of graph.

Keyword arguments are forwarded to boundary_edges, in particular dir, which selects the edge direction to consider in a directed graph.