Adding Edge Coloring/weight functionality

[rightleftspin]

Add the functionality to deal with edge weighted graphs similar to nauty-pet, which is the rust library that implements nauty for petgraphs. The code for it in rust is in this file

https://github.com/a-maier/nauty-pet/blob/7aa4f4407ad56df9b0cf086e4ebc261c582f0f9b/src/nauty_graph.rs#L98

It comes in place when importing a graph from petgraph I believe. It should be possible to follow the same format, when importing a graph with edge weights from Graphs.jl, we can convert it into a graph that nauty can deal with.

[mxhbl]

Hey, this sounds great. I will probably not have time to work on this for another few weeks, but please feel free to submit a PR in the meantime! :)

[rightleftspin]

I'm working on this over the next few days, your library is really well structured!

I'm struggling to see where to add this functionality exactly, since it seems like it might break some existing code. I'm going to outline my approach and see if you think it's a good idea.

1. Add a field to the DenseNautyGraph struct that holds the edge weights for each edge

2. Add a field to the DenseNautyGraph struct that indicates if there is more than one edge weight, or add a type parameter similar to the type parameter used to indicate if a graph is directed or undirected.

3. Add the ability to deal with edge-colored graphs in the nauty function right before the ccall line to create a copy of the graphset and edit that copy to account for edge weights using a similar algorithm as used in rust's nauty-pet library.

(option 1) 4) Add new functions that to the basic graph api and graph modification section that can account for edge weighted graphs

(option 2) 4) Edit the existing functions in the basic graph api and graph modification section so that they can deal with edge weighted graphs, set the edge weight to 1 as the default, assuming all edges have the same weight.

Let me know if this makes sense, I'll hold off on working on it till I have a good idea of what you think would be good. Either way, thank you for your help!

Also, it seems we're both physics PhD students, so that's pretty funny :)

[mxhbl]

Hey, thanks for thinking this through. I think your approach is good, but I'm wondering if there is a way to implement this with as few changes to the existing code as possible.

I think the most important addition would be a method that implements the automorphism-group-preserving mapping from an edge-colored to a vertex-colored graph. I know that such a mapping is described in the nauty user guide, but there are probably more efficient versions of it out there. With that mapping, the user can then convert their edge-colored graphs to vertex-colored graphs and then use NautyGraphs as normal.

Everything that is left after that are just convenience methods for applying that mapping and reading out the results. We could in principle define a new type like EdgeWeightedNautyGraph to wrap regular NautyGraphs and handle all the necessary conversions. Eventually we would probably also want to interface with MetaGraphs.jl, which makes everything a bit more complicated.

I am not sure what the best approach is here. I think for now just implementing the edge-color to vertex-color mapping, together with documentation for when and how to use it might be the easiest. Would that be enough for your use-case, or would you need full support, including graph modification methods (add_vertex!, rem_vertex!,...) and so on?

[rightleftspin]

This sounds good for my use case, but I would be willing to help with the full implementation in the future! I'll aim to implement the function that does the conversion between edge weighted graphs and non-weighted graphs. I'll probably just follow the suggestion in Nauty for now and search for some more efficient algorithms after I get a simple one working. I think getting full support for MetaGraphs.jl and MetaGraphsNext.jl would be good, but definitely can be long term goal. For an example of the function(s) I'm thinking of:

function convert_to_unweighted(weighted_directed_adjacency_matrix, vertex_labels) -> (unweighted_directed_adjacency_matrix, new_vertex_labels)

• Note: The adjacency matrix can be either directed or undirected, I'm pretty sure the example in Nauty works for either case, just left it directed here.

[rightleftspin]

I completely dropped the ball on this, very sorry. I have here a quick function I have been using for a bit to convert between a weighted adjacency matrix and an unweighted adjacency matrix. I took this from the rust implementation, but it should be simple enough to recreate. I cannot guarantee it is the most efficient piece of code, but it does work for many use cases. Its been rewritten from some other projects I am working on, so I don't know if the function works out of the box, but its the general outline for this conversion.

The function takes in the weighted adjacency matrix and a vector of the vertex labels and returns the unweighted adjacency matrix.

function convert_to_unweighted(weighted_adj_mat, graph_labels)

nauty_labels = vcat(
        graph_labels,
        zeros(Int64, fld(count(>(1), weighted_adj_mat), 2)),
)

unweighted_adjacency_matrix =
        zeros(Int64, length(nauty_labels), length(nauty_labels))

current_aux_vert = length(graph_labels) + 1
for j = 1:size(weighted_adj_mat, 2)
        for i = j:size(weighted_adj_mat, 1)

                if (weighted_adj_mat[i, j] == 1)
                        # Add an edge if there is already an edge
                        unweighted_adjacency_matrix[i, j] = 1
                        unweighted_adjacency_matrix[j, i] = 1
                elseif (weighted_adj_mat[i, j] != 0)
                        # Add an edge to the auxilary vertex here
                        unweighted_adjacency_matrix[i, current_aux_vert] = 1
                        unweighted_adjacency_matrix[j, current_aux_vert] = 1
                        unweighted_adjacency_matrix[current_aux_vert, i] = 1
                        unweighted_adjacency_matrix[current_aux_vert, j] = 1
                        # Color the aux vertex the same as the edge
                        nauty_labels[current_aux_vert] = weighted_adj_mat[i, j]
                        current_aux_vert += 1
                end
        end
end

unweighted_adjacency_matrix
end