Functions for reading/building graphs/digraphs#

This module gathers functions needed to build a graph from any other data.

Note

This is an internal module of Sage. All features implemented here are made available to end-users through the constructors of Graph and DiGraph.

Note that because they are called by the constructors of Graph and DiGraph, most of these functions modify a graph inplace.

from_adjacency_matrix()

Fill G with the data of an adjacency matrix.

from_dict_of_dicts()

Fill G with the data of a dictionary of dictionaries.

from_dict_of_lists()

Fill G with the data of a dictionary of lists.

from_dig6()

Fill G with the data of a dig6 string.

from_graph6()

Fill G with the data of a graph6 string.

from_incidence_matrix()

Fill G with the data of an incidence matrix.

from_networkx_graph()

Fill \(G\) with the data of a NetworkX (di)graph.

from_oriented_incidence_matrix()

Fill G with the data of an oriented incidence matrix.

from_seidel_adjacency_matrix()

Fill G with the data of a Seidel adjacency matrix.

from_sparse6()

Fill G with the data of a sparse6 string.

Functions#

sage.graphs.graph_input.from_adjacency_matrix(G, M, loops=False, multiedges=False, weighted=False)#

Fill G with the data of an adjacency matrix.

INPUT:

  • G – a Graph or DiGraph

  • M – an adjacency matrix

  • loops, multiedges, weighted – booleans (default: False); whether to consider the graph as having loops, multiple edges, or weights

EXAMPLES:

sage: from sage.graphs.graph_input import from_adjacency_matrix
sage: g = Graph()
sage: from_adjacency_matrix(g, graphs.PetersenGraph().adjacency_matrix())       # needs sage.modules
sage: g.is_isomorphic(graphs.PetersenGraph())                                   # needs sage.modules
True
sage.graphs.graph_input.from_dict_of_dicts(G, M, loops=False, multiedges=False, weighted=False, convert_empty_dict_labels_to_None=False)#

Fill G with the data of a dictionary of dictionaries.

INPUT:

  • G – a graph

  • M – a dictionary of dictionaries

  • loops, multiedges, weighted – booleans (default: False); whether to consider the graph as having loops, multiple edges, or weights

  • convert_empty_dict_labels_to_None – booleans (default: False); whether to adjust for empty dicts instead of None in NetworkX default edge labels

EXAMPLES:

sage: from sage.graphs.graph_input import from_dict_of_dicts
sage: g = Graph()
sage: from_dict_of_dicts(g, graphs.PetersenGraph().to_dictionary(edge_labels=True))
sage: g.is_isomorphic(graphs.PetersenGraph())
True
sage.graphs.graph_input.from_dict_of_lists(G, D, loops=False, multiedges=False, weighted=False)#

Fill G with the data of a dictionary of lists.

INPUT:

  • G – a Graph or DiGraph

  • D – a dictionary of lists

  • loops, multiedges, weighted – booleans (default: False); whether to consider the graph as having loops, multiple edges, or weights

EXAMPLES:

sage: from sage.graphs.graph_input import from_dict_of_lists
sage: g = Graph()
sage: from_dict_of_lists(g, graphs.PetersenGraph().to_dictionary())
sage: g.is_isomorphic(graphs.PetersenGraph())
True
sage.graphs.graph_input.from_dig6(G, dig6_string)#

Fill G with the data of a dig6 string.

INPUT:

  • G – a graph

  • dig6_string – a dig6 string

EXAMPLES:

sage: from sage.graphs.graph_input import from_dig6
sage: g = DiGraph()
sage: from_dig6(g, digraphs.Circuit(10).dig6_string())
sage: g.is_isomorphic(digraphs.Circuit(10))
True
sage.graphs.graph_input.from_graph6(G, g6_string)#

Fill G with the data of a graph6 string.

INPUT:

  • G – a graph

  • g6_string – a graph6 string

EXAMPLES:

sage: from sage.graphs.graph_input import from_graph6
sage: g = Graph()
sage: from_graph6(g, 'IheA@GUAo')
sage: g.is_isomorphic(graphs.PetersenGraph())
True
sage.graphs.graph_input.from_incidence_matrix(G, M, loops=False, multiedges=False, weighted=False)#

Fill G with the data of an incidence matrix.

INPUT:

  • G – a graph

  • M – an incidence matrix

  • loops, multiedges, weighted – booleans (default: False); whether to consider the graph as having loops, multiple edges, or weights

EXAMPLES:

sage: from sage.graphs.graph_input import from_incidence_matrix
sage: g = Graph()
sage: from_incidence_matrix(g, graphs.PetersenGraph().incidence_matrix())       # needs sage.modules
sage: g.is_isomorphic(graphs.PetersenGraph())                                   # needs sage.modules
True
sage.graphs.graph_input.from_networkx_graph(G, gnx, weighted=None, loops=None, multiedges=None, convert_empty_dict_labels_to_None=None)#

Fill \(G\) with the data of a NetworkX (di)graph.

INPUT:

  • G – a Graph or DiGraph

  • gnx – a NetworkX Graph, MultiGraph, DiGraph or MultiDiGraph

  • weighted – boolean (default: None); whether graph thinks of itself as weighted or not. See weighted().

  • loops – boolean (default: None); whether to allow loops

  • multiedges – boolean (default: None); whether to allow multiple edges

  • convert_empty_dict_labels_to_None – boolean (default: None); whether to replace the default edge labels used by NetworkX (empty dictionaries) by None, the default Sage edge label. When set to False, empty dictionaries are not converted to None.

EXAMPLES:

Feeding a Graph with a NetworkX Graph:

sage: # needs networkx
sage: from sage.graphs.graph_input import from_networkx_graph
sage: import networkx
sage: G = Graph()
sage: _ = gnx = networkx.Graph()
sage: _ = gnx.add_edge(0, 1)
sage: _ = gnx.add_edge(1, 2)
sage: from_networkx_graph(G, gnx)
sage: G.edges(sort=True, labels=False)
[(0, 1), (1, 2)]

Feeding a Graph with a NetworkX MultiGraph:

sage: # needs networkx
sage: G = Graph()
sage: gnx = networkx.MultiGraph()
sage: _ = gnx.add_edge(0, 1)
sage: _ = gnx.add_edge(0, 1)
sage: from_networkx_graph(G, gnx)
sage: G.edges(sort=True, labels=False)
[(0, 1), (0, 1)]
sage: G = Graph()
sage: from_networkx_graph(G, gnx, multiedges=False)
sage: G.edges(sort=True, labels=False)
[(0, 1)]

When feeding a Graph \(G\) with a NetworkX DiGraph \(D\), \(G\) has one edge \((u, v)\) whenever \(D\) has arc \((u, v)\) or \((v, u)\) or both:

sage: # needs networkx
sage: G = Graph()
sage: D = networkx.DiGraph()
sage: _ = D.add_edge(0, 1)
sage: from_networkx_graph(G, D)
sage: G.edges(sort=True, labels=False)
[(0, 1)]
sage: G = Graph()
sage: _ = D.add_edge(1, 0)
sage: from_networkx_graph(G, D)
sage: G.edges(sort=True, labels=False)
[(0, 1)]

When feeding a Graph \(G\) with a NetworkX MultiDiGraph \(D\), the number of edges between \(u\) and \(v\) in \(G\) is the maximum between the number of arcs \((u, v)\) and the number of arcs \((v, u)\) in D`:

sage: # needs networkx
sage: G = Graph()
sage: D = networkx.MultiDiGraph()
sage: _ = D.add_edge(0, 1)
sage: _ = D.add_edge(1, 0)
sage: _ = D.add_edge(1, 0)
sage: D.edges()
OutMultiEdgeDataView([(0, 1), (1, 0), (1, 0)])
sage: from_networkx_graph(G, D)
sage: G.edges(sort=True, labels=False)
[(0, 1), (0, 1)]

Feeding a DiGraph with a NetworkX DiGraph:

sage: # needs networkx
sage: from sage.graphs.graph_input import from_networkx_graph
sage: import networkx
sage: G = DiGraph()
sage: _ = gnx = networkx.DiGraph()
sage: _ = gnx.add_edge(0, 1)
sage: _ = gnx.add_edge(1, 2)
sage: from_networkx_graph(G, gnx)
sage: G.edges(sort=True, labels=False)
[(0, 1), (1, 2)]

Feeding a DiGraph with a NetworkX MultiDiGraph:

sage: # needs networkx
sage: G = DiGraph()
sage: gnx = networkx.MultiDiGraph()
sage: _ = gnx.add_edge(0, 1)
sage: _ = gnx.add_edge(0, 1)
sage: from_networkx_graph(G, gnx)
sage: G.edges(sort=True, labels=False)
[(0, 1), (0, 1)]
sage: G = DiGraph()
sage: from_networkx_graph(G, gnx, multiedges=False)
sage: G.edges(sort=True, labels=False)
[(0, 1)]

When feeding a DiGraph \(G\) with a NetworkX Graph \(H\), \(G\) has both arcs \((u, v)\) and \((v, u)\) if \(G\) has edge \((u, v)\):

sage: # needs networkx
sage: G = DiGraph()
sage: H = networkx.Graph()
sage: _ = H.add_edge(0, 1)
sage: from_networkx_graph(G, H)
sage: G.edges(labels=False, sort=True)
[(0, 1), (1, 0)]

When feeding a DiGraph \(G\) with a NetworkX MultiGraph \(H\), \(G\) has \(k\) arcs \((u, v)\) and \(k\) arcs \((v, u)\) if \(H\) has \(k\) edges \((u, v)\), unless parameter multiedges is set to False:

sage: # needs networkx
sage: G = DiGraph()
sage: H = networkx.MultiGraph()
sage: _ = H.add_edge(0, 1)
sage: _ = H.add_edge(0, 1)
sage: _ = H.add_edge(0, 1)
sage: H.edges()
MultiEdgeDataView([(0, 1), (0, 1), (0, 1)])
sage: from_networkx_graph(G, H)
sage: G.edges(labels=False, sort=True)
[(0, 1), (0, 1), (0, 1), (1, 0), (1, 0), (1, 0)]
sage: G = DiGraph()
sage: from_networkx_graph(G, H, multiedges=False)
sage: G.edges(labels=False, sort=True)
[(0, 1), (1, 0)]
sage.graphs.graph_input.from_oriented_incidence_matrix(G, M, loops=False, multiedges=False, weighted=False)#

Fill G with the data of an oriented incidence matrix.

An oriented incidence matrix is the incidence matrix of a directed graph, in which each non-loop edge corresponds to a \(+1\) and a \(-1\), indicating its source and destination.

INPUT:

  • G – a DiGraph

  • M – an incidence matrix

  • loops, multiedges, weighted – booleans (default: False); whether to consider the graph as having loops, multiple edges, or weights

Note

weighted is currently ignored.

EXAMPLES:

sage: from sage.graphs.graph_input import from_oriented_incidence_matrix
sage: g = DiGraph()
sage: im = digraphs.Circuit(10).incidence_matrix()                              # needs sage.modules
sage: from_oriented_incidence_matrix(g, im)                                     # needs sage.modules
sage: g.is_isomorphic(digraphs.Circuit(10))                                     # needs sage.modules
True
sage.graphs.graph_input.from_seidel_adjacency_matrix(G, M)#

Fill G with the data of a Seidel adjacency matrix.

INPUT:

  • G – a graph

  • M – a Seidel adjacency matrix

EXAMPLES:

sage: from sage.graphs.graph_input import from_seidel_adjacency_matrix
sage: g = Graph()
sage: sam = graphs.PetersenGraph().seidel_adjacency_matrix()                    # needs sage.modules
sage: from_seidel_adjacency_matrix(g, sam)                                      # needs sage.modules
sage: g.is_isomorphic(graphs.PetersenGraph())                                   # needs sage.modules
True
sage.graphs.graph_input.from_sparse6(G, g6_string)#

Fill G with the data of a sparse6 string.

INPUT:

  • G – a graph

  • g6_string – a sparse6 string

EXAMPLES:

sage: from sage.graphs.graph_input import from_sparse6
sage: g = Graph()
sage: from_sparse6(g, ':I`ES@obGkqegW~')
sage: g.is_isomorphic(graphs.PetersenGraph())
True