Graph

Graph()

A graph that supported directional edges, parallel edges, self-edges and custom data on the nodes and edges.

Warning: modifying the graph if it is contained in a dict or set will invalidate the hash.

Methods

Name	Description
add_edge	Add an edge between the source and target nodes, returning the index of the edge.
add_node	Add a node with data data to the graph, returning the index of the node.
canonize	Write the graph in a canonical form.
canonize_edges	Sort and relabel the edges of the graph, keeping the vertices fixed.
edge	Get the idxth edge, consisting of the the source vertex, target vertex, whether the edge is directed, and the data.
edges	Get all edges, consisting of the the source vertex, target vertex, whether the edge is directed, and the data.
generate	Generate all connected graphs with external_edges half-edges and the given allowed list
is_isomorphic	Return true iff the graph is isomorphic to other.
node	Get the idxth node, consisting of the edge indices and the data.
nodes	Get all nodes, consisting of the edge indices and the data.
num_edges	Get the number of edges.
num_loops	Get the number of loops.
num_nodes	Get the number of nodes.
set_directed	Set the directed status of the edge at index index, returning the old value.
set_edge_data	Set the data of the edge at index index, returning the old data.
set_node_data	Set the data of the node at index index, returning the old data.
to_dot	Convert the graph to a graphviz dot string.
to_mermaid	Convert the graph to a mermaid string.

add_edge

Graph.add_edge(source, target, directed=False, data=None)

Add an edge between the source and target nodes, returning the index of the edge. Optionally, the edge can be set as directed. The default data is the number 0.

add_node

Graph.add_node(data=None)

Add a node with data data to the graph, returning the index of the node. The default data is the number 0.

canonize

Graph.canonize()

Write the graph in a canonical form. Returns the canonicalized graph, the vertex map, the automorphism group size, and the orbit.

canonize_edges

Graph.canonize_edges()

Sort and relabel the edges of the graph, keeping the vertices fixed.

edge

Graph.edge(idx)

Get the idxth edge, consisting of the the source vertex, target vertex, whether the edge is directed, and the data.

edges

Graph.edges()

Get all edges, consisting of the the source vertex, target vertex, whether the edge is directed, and the data.

generate

Graph.generate(
    external_edges,
    vertex_signatures,
    max_vertices=None,
    max_loops=None,
    max_bridges=None,
    allow_self_loops=None,
    allow_zero_flow_edges=None,
    filter_fn=None,
    progress_fn=None,
)

Generate all connected graphs with external_edges half-edges and the given allowed list of vertex connections. The vertex signatures are given in terms of an edge direction (or None if there is no direction) and edge data.

Returns the canonical form of the graph and the size of its automorphism group (including edge permutations). If KeyboardInterrupt is triggered during the generation, the generation will stop and will yield the currently generated graphs.

Examples

>>> from symbolica import *
>>> g, q, gh = HalfEdge(S("g")), HalfEdge(S("q"), True), HalfEdge(S("gh"), True)
>>> graphs = Graph.generate(
>>>     external_nodes=[(1, g), (2, g)],
>>>     vertex_signatures=[[g, g, g], [g, g, g, g],
>>>                        [q.flip(), q, g], [gh.flip(), gh, g]],
>>>     max_loops=2,
>>> )
>>> for (g, sym) in graphs.items():
>>>     print(f'Symmetry factor = 1/{sym}:')
>>>     print(g.to_dot())

generates all connected graphs up to 2 loops with the specified vertices.

Parameters

Name	Type	Description	Default
external_nodes		The external edges, consisting of a tuple of the node data and a tuple of the edge direction and edge data. If the node data is the same, flip symmetries will be recognized.	required
vertex_signatures	Sequence[Sequence[HalfEdge]]	The allowed connections for each vertex.	required
max_vertices	Optional[int]	The maximum number of vertices in the graph.	None
max_loops	Optional[int]	The maximum number of loops in the graph.	None
max_bridges	Optional[int]	The maximum number of bridges in the graph.	None
allow_self_loops	bool	Whether self-edges are allowed.	None
allow_zero_flow_edges	bool	Whether bridges that do not need to be crossed to connect external vertices are allowed.	None
filter_fn	Optional[Callable[[Graph, int], bool]]	Set a filter function that is called during the graph generation. The first argument is the graph g and the second argument the vertex count n that specifies that the first n vertices are completed (no new edges will) be assigned to them. The filter function should return true if the current incomplete graph is allowed, else it should return false and the graph is discarded.	None
progress_fn	Optional[Callable[[Graph], bool]]	Set a progress function that is called every time a new unique graph is created. The argument is the newly created graph. If the function returns false, the generation is aborted and the currently generated graphs are returned.	None

is_isomorphic

Graph.is_isomorphic(other)

Return true iff the graph is isomorphic to other.

node

Graph.node(idx)

Get the idxth node, consisting of the edge indices and the data.

nodes

Graph.nodes()

Get all nodes, consisting of the edge indices and the data.

num_edges

Graph.num_edges()

Get the number of edges.

num_loops

Graph.num_loops()

Get the number of loops.

num_nodes

Graph.num_nodes()

Get the number of nodes.

set_directed

Graph.set_directed(index, directed)

Set the directed status of the edge at index index, returning the old value.

set_edge_data

Graph.set_edge_data(index, data)

Set the data of the edge at index index, returning the old data.

set_node_data

Graph.set_node_data(index, data)

Set the data of the node at index index, returning the old data.

to_dot

Graph.to_dot()

Convert the graph to a graphviz dot string.

to_mermaid

Graph.to_mermaid()

Convert the graph to a mermaid string.