Reference

DefaultNamedCapacity{T}

Structure that returns 1 if a forward edge exists in flow_graph, and 0 otherwise.

struct NamedDijkstraState{V,T}

An AbstractPathState designed for Dijkstra shortest-paths calculations.

edgeinduced_subgraphs_no_leaves(g::AbstractNamedGraph, max_number_of_edges::Int64)

Enumerate all unique, connected edgesubgraphs without any leaf vertices (degree 1) and with Nedges <= maxnumberof_edges

Current default graph partitioning backend

Graph partitioning backend

Add a list of edges to a graph g

Get the graph partitioning backend

Get distance of a vertex from a leaf

Determine if a node has any neighbors which are leaves

incident_edges(graph::AbstractGraph, vertex; dir=:out)

Edges incident to the vertex vertex.

dir ∈ (:in, :out, :both), defaults to :out.

For undirected graphs, returns all incident edges.

Like: https://juliagraphs.org/Graphs.jl/v1.7/algorithms/linalg/#Graphs.LinAlg.adjacency_matrix

https://juliagraphs.org/Graphs.jl/dev/corefunctions/simplegraphsgenerators/#Graphs.SimpleGraphs.cyclegraph-Tuple%7BT%7D%20where%20T%3C:Integer https://en.wikipedia.org/wiki/Cyclegraph

Determine if an edge involves a leaf (at src or dst)

Check if an undirected graph is a path/linear graph:

https://en.wikipedia.org/wiki/Path_graph

but not a path/linear forest:

https://en.wikipedia.org/wiki/Linear_forest

Get all edges which do not involve a leaf

https://en.wikipedia.org/wiki/Tree(graphtheory)#Definitions

Do a BFS search to construct a tree, but do it with randomness to avoid generating the same tree. Based on Int. J. Comput. Their Appl. 15 pp 177-186 (2008). Edges will point away from source vertex s.

Remove a list of edges from a graph g

Remove a list of vertices from a graph g

Return the root vertex of a rooted directed graph.

This will return the first root vertex that is found, so won't error if there is more than one.

Set the graph partitioning backend

Generate a graph which corresponds to a hexagonal tiling of the plane. There are m rows and n columns of hexagons. Based off of the generator in Networkx hexagonallatticegraph()

Generate a graph which corresponds to a equilateral triangle tiling of the plane. There are m rows and n columns of triangles. Based off of the generator in Networkx triangularlatticegraph()

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}

To use AbstractPartitionedGraph one should defined unpartitioned_graph that returns an underlying graph without any partitioning. One should also define:

QuotientEdge(e)

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

QuotientVertex(v)

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

edges(g::AbstractGraph, quotientedge::QuotientEdge)
edges(g::AbstractGraph, quotientedges::Vector{QuotientEdge})

Return the set of edges in the graph g that correspond to a single quotient edge or a list of quotient edges.

ne(g::AbstractGraph, qe::QuotientEdge) -> Int

Returns the number of edges in g that correspond to the quotient edge qe.

See also: nv.

vertices(g::AbstractGraph, quotientvertex::QuotientVertex)
vertices(g::AbstractGraph, quotientvertices::Vector{QuotientVertex})

Return the set of vertices in the graph g associated with the quotient vertex quotientvertex or set of quotient vertices quotientvertices.

rem_edges!(g::AbstractGraph, qe::QuotientEdge) -> Int

Remove, in place, all the edges of g that correspond to the quotient edge qe.

has_quotientedge(g::AbstractGraph, qe::QuotientEdge) -> Bool

Returns true if the quotient edge qe exists in the quotient graph of g.

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(pg))

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

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

Return all unique quotient vertices corresponding to the set vertices vs of the graph pg.

Key{K}

A key (index) type, used for unambiguously identifying an object as a key or index of an indexible object AbstractArray, AbstractDict, etc.

Useful for nested structures of indices, for example:

[Key([1, 2]), [Key([3, 4]), Key([5, 6])]]

which could represent partitioning a set of vertices

[Key([1, 2]), Key([3, 4]), Key([5, 6])]