Partitioned graphs

[JoeyT1994]

This PR adds support for partitioned graphs (see https://en.wikipedia.org/wiki/Graph_partition and the relevant issue #41)

Specifically an AbstractPartitionedGraph pg is a structure which contains:

• The graph which was partitioned g (can be accessed via graph(pg))
• The new, simpler graph, g_partitioned (can be accessed via partitioned_graph(pg))
• A map from each of the vertices pv of g_partitioned to the corresponding set of vertices in g. This information can be accessed via vertices(pg, pv).
• A map from each vertex v in g to its corresponding vertex in g_partitioned. This can be accessed with partition_vertex(pg, v)

As the AbstractPartitionedGraph is a subtype of the AbstractNamedGraph, NamedGraphs functions immediately can be applied to it. Most functions will simply forward to the underlying graph g, i.e. is_tree(pg) = is_tree(graph(g)). However, for functions which actually modify the graph or return a NamedGraph type we modify the whole partitioned_graph. E.g. rem_vertex!(pg, v) will remove vertex from graph(pg) and also modify partitioned_graph(pg) and the corresponding vertex maps appropriately.

We also introduce the AbstractPartitionVertex and AbstractPartitionEdge type to overload a function like rem_vertex so that rem_vertex!(pg, pv::AbstractPartitionVertex) exists and will remove pv from partitioned_graph(pg) and then update graph(pg) and the relevant maps correspondingly.

This PR also introduces the concrete PartitionedGraph type which is structured explicitly as:

struct PartitionedGraph{V,PV,G<:AbstractNamedGraph{V},PG<:AbstractNamedGraph{PV}} <:
       AbstractPartitionedGraph{V,PV}
  graph::G
  partitioned_graph::PG
  partition_vertices::Dictionary{PV,Vector{V}}
  partition_vertex::Dictionary{V,PV}
end

and operates as expected. Some example code that can now be written with this PR is:

  using NamedGraphs
  nx, ny = 5, 5
  g = named_grid((nx, ny))

  partitions = [[(i, j) for j in 1:ny] for i in 1:nx]
  pg = PartitionedGraph(g, partitions)
  @assert is_path_graph(pg.partitioned_graph)

which partitions the grid by its rows resulting in `pg.pg.partitioned_graph' being a 5-site path graph.

Extensive testing is included in tests/test_partitionedgraph.jl and an example is included in examples/partitioning.jl. The partitioning libraries KaHyPar.jl and Metis.jl can be called to build a PartitionedGraph from a NamedGraph g based on specifying some parameter like the number of partitions and minimising some cost function like the number of edges between partitions. This is the default cost function.

E.g. PartitionedGraph(g; npartitions, backend = "KaHyPar") will construct a PartitionedGraph with npartitions and attempt to partition in such a way as to minimise the number of edges between partitions.

Lots of the code here supercedes the code in src/partition.jl of ITensorNetworks.jl and thus that will be removed in a near term PR.

[codecov-commenter]

Codecov Report

Attention: 110 lines in your changes are missing coverage. Please review.

Comparison is base (1b356a9) 82.86% compared to head (30dfeb0) 78.09%.

Files	Patch %	Lines
...aphs/partitionedgraphs/abstractpartitionedgraph.jl	41.28%	64 Missing :warning:
src/Graphs/abstractgraph.jl	5.55%	17 Missing :warning:
src/Graphs/partitionedgraphs/partitionedgraph.jl	83.56%	12 Missing :warning:
src/Graphs/partitionedgraphs/partitioning.jl	68.00%	8 Missing :warning:
.../Graphs/partitionedgraphs/abstractpartitionedge.jl	0.00%	3 Missing :warning:
src/abstractnamedgraph.jl	81.25%	3 Missing :warning:
src/Graphs/partitionedgraphs/partitionedge.jl	60.00%	2 Missing :warning:
...raphs/partitionedgraphs/abstractpartitionvertex.jl	0.00%	1 Missing :warning:

:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.

Additional details and impacted files

```diff @@ Coverage Diff @@ ## main #44 +/- ## ========================================== - Coverage 82.86% 78.09% -4.78% ========================================== Files 22 31 +9 Lines 934 1178 +244 ========================================== + Hits 774 920 +146 - Misses 160 258 +98 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[mtfishman]

@JoeyT1994 could you remind me of the status of this? Is the only thing remaining to change the code organization of insert_vertex! and related functions?

[JoeyT1994]

Yeah I believe that is the case! And I just re-organised it so that add_vertex! is required for the core interface of an abstractgraph

[mtfishman]

I think after addressing the last few comments I left this should be good to go.

[JoeyT1994]

Great! I believe I have resolved the above.

[mtfishman]

Looks good, thanks! Interested to see how this works out in the BP code.