- Notifications
You must be signed in to change notification settings - Fork0
OCaml bindings to nauty
License
MIT, Unknown licenses found
Licenses found
zajer/onauty
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
An OCaml library for determining whether provided graphs are isomorphic or not.
In case they are, a map between vertices can also be calculated.It uses nauty library as its backbone.
This software usesnauty and Traces library (http://pallini.di.uniroma1.it/) licensed under the Apache License 2.0. A boilerplate declaration is available inLICENSE-Nauty&Traces.txt file.The full license is available at:https://www.apache.org/licenses/LICENSE-2.0
To create a graph one should specify its vertices and adjacency matrix1.
open Onautylet g = Graph.empty () |> Graph.add_vertices 4 |> Graph.add_conns [(0,1);(1,2);(3,2)]It is possible to create a graph all at once (as shown above) or partially.
open Onautylet g = Graph.empty () ;;Graph.add_vertex g |> Graph.add_vertex ;;.. (* doing some stuff*).Graph.add_conn (0,1) g;;1 The order of connections is only important if a graph will be later considered as a digraph (directed graph).
Having two graphs, we can check whether they are isomorphic to each other.
let g1 = Onauty.Graph.empty () |> Onauty.Graph.add_vertices 4 |> Onauty.Graph.add_conns [(0,1);(1,2);(3,2)]let g2 = Onauty.Graph.empty () |> Onauty.Graph.add_vertices 4 |> Onauty.Graph.add_conns [(0,1);(2,1);(3,2)](* g1 and g2 will be considered as undirected graphs *)let are_iso1 = Onauty.Iso.are_graphs_iso g1 g2 (* g1 and g2 will be considered as directed graphs*)let are_iso2 = Onauty.Iso.are_digraphs_iso g1 g2It is also possible to partition a set of vertices into groups of colors.
(*this creates a graph with vertex 0 colored with first color, vertices 2 and 3 are colored with second color and vertex 1 is colored with third color *)let g = Onauty.Graph.empty () |> Onauty.Graph.add_vertices 4 |> Onauty.Graph.add_conns [(0,1);(2,1);(3,2)] |> Onauty.Graph.set_colors (Common.StringMap.empty |> Common.StringMap.add "C1" [0] |> Common.StringMap.add "C2" [2;3] |> Common.StringMap.add "C3" [1]Please note that order of colors is important for determing the ismorphism.For example:
open Onautylet g1 = Graph.empty () |> Graph.add_vertices 4 |> Graph.add_conns [(0,1);(2,1);(3,2)] |> Graph.set_colors (Common.StringMap.empty |> Common.StringMap.add "A" [0] |> Common.StringMap.add "B" [2;3] |> Common.StringMap.add "C" [1] ) let g2 = Graph.empty () |> Graph.add_vertices 4 |> Graph.add_conns [(0,1);(2,1);(3,2)] |> Graph.set_colors (Common.StringMap.empty |> Common.StringMap.add "C" [0] |> Common.StringMap.add "A" [2;3] |> Common.StringMap.add "B" [1] )(*this results in false because colors (represented as strings "A", "B" and "C") are sorted alphbetically so the first graph has vertex 0 assigned to first color while the second graph has vertex 0 assigned to third color. Structurally graphs are identical but colors are different. *)let are_iso = Iso.are_graphs_iso ~check_colors:true g1 g2 ;;Similarly as before, we can generate a mapping between isomorphic graphs (or digraphs).For example:
let g1 = Graph.empty () |> Graph.add_vertices 4 |> Graph.add_conns [(0,1);(2,1);(3,2)] |> Graph.set_colors (Common.StringMap.empty |> Common.StringMap.add "A" [0] |> Common.StringMap.add "B" [1] |> Common.StringMap.add "C" [2;3] ) let g2 = Graph.empty () |> Graph.add_vertices 4 |> Graph.add_conns [(0,1);(2,1);(3,2)]|> Graph.set_colors (Common.StringMap.empty |> Common.StringMap.add "A" [3]|> Common.StringMap.add "B" [2]|> Common.StringMap.add "C" [0;1] )let are_graphs_iso,mapping = Iso.graphs_iso_map ~check_colors:true g1 g2 (* this results in a tuple of the form: (true,[|(0,3);(1,2);(2,1);(3,0)|]) *)let are_digraphs_iso,mapping = Iso.digraphs_iso_map ~check_colors:true g1 g2 (* this results in a tupel of the form: (false,[||]) *)About
OCaml bindings to nauty