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)[source]

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

>>> from sage.all import *
>>> from sage.graphs.graph_input import from_adjacency_matrix
>>> g = Graph()
>>> from_adjacency_matrix(g, graphs.PetersenGraph().adjacency_matrix())       # needs sage.modules
>>> 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)[source]

Fill G with the data of a dictionary of dictionaries.

INPUT:

  • G – a graph

  • M – 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

>>> from sage.all import *
>>> from sage.graphs.graph_input import from_dict_of_dicts
>>> g = Graph()
>>> from_dict_of_dicts(g, graphs.PetersenGraph().to_dictionary(edge_labels=True))
>>> g.is_isomorphic(graphs.PetersenGraph())
True

The resulting order of vertices is unspecified but deterministic:

sage: from sage.graphs.graph_input import from_dict_of_dicts
sage: g = Graph()
sage: from_dict_of_dicts(g, {i: {} for i in range(99, 90, -1)})
sage: g.vertices(sort=False)
[99, 98, 97, 96, 95, 94, 93, 92, 91]

>>> from sage.all import *
>>> from sage.graphs.graph_input import from_dict_of_dicts
>>> g = Graph()
>>> from_dict_of_dicts(g, {i: {} for i in range(Integer(99), Integer(90), -Integer(1))})
>>> g.vertices(sort=False)
[99, 98, 97, 96, 95, 94, 93, 92, 91]
sage.graphs.graph_input.from_dict_of_lists(G, D, loops=False, multiedges=False, weighted=False)[source]

Fill G with the data of a dictionary of lists.

INPUT:

  • G – a Graph or DiGraph

  • D – 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

>>> from sage.all import *
>>> from sage.graphs.graph_input import from_dict_of_lists
>>> g = Graph()
>>> from_dict_of_lists(g, graphs.PetersenGraph().to_dictionary())
>>> g.is_isomorphic(graphs.PetersenGraph())
True

The resulting order of vertices is unspecified but deterministic:

sage: from sage.graphs.graph_input import from_dict_of_lists
sage: g = Graph()
sage: from_dict_of_lists(g, {i: [] for i in range(99, 90, -1)})
sage: g.vertices(sort=False)
[99, 98, 97, 96, 95, 94, 93, 92, 91]

>>> from sage.all import *
>>> from sage.graphs.graph_input import from_dict_of_lists
>>> g = Graph()
>>> from_dict_of_lists(g, {i: [] for i in range(Integer(99), Integer(90), -Integer(1))})
>>> g.vertices(sort=False)
[99, 98, 97, 96, 95, 94, 93, 92, 91]
sage.graphs.graph_input.from_dig6(G, dig6_string)[source]

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

>>> from sage.all import *
>>> from sage.graphs.graph_input import from_dig6
>>> g = DiGraph()
>>> from_dig6(g, digraphs.Circuit(Integer(10)).dig6_string())
>>> g.is_isomorphic(digraphs.Circuit(Integer(10)))
True

The string may represent a directed graph with loops:

sage: L = DiGraph(loops=True)
sage: from_dig6(L, 'CW`C')
sage: L.edges(labels=False, sort=True)
[(0, 1), (0, 2), (1, 2), (2, 3), (3, 3)]

>>> from sage.all import *
>>> L = DiGraph(loops=True)
>>> from_dig6(L, 'CW`C')
>>> L.edges(labels=False, sort=True)
[(0, 1), (0, 2), (1, 2), (2, 3), (3, 3)]
sage.graphs.graph_input.from_graph6(G, g6_string)[source]

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

>>> from sage.all import *
>>> from sage.graphs.graph_input import from_graph6
>>> g = Graph()
>>> from_graph6(g, 'IheA@GUAo')
>>> g.is_isomorphic(graphs.PetersenGraph())
True
sage.graphs.graph_input.from_incidence_matrix(G, M, loops=False, multiedges=False, weighted=False)[source]

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

>>> from sage.all import *
>>> from sage.graphs.graph_input import from_incidence_matrix
>>> g = Graph()
>>> from_incidence_matrix(g, graphs.PetersenGraph().incidence_matrix())       # needs sage.modules
>>> 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)[source]

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)]

>>> from sage.all import *
>>> # needs networkx
>>> from sage.graphs.graph_input import from_networkx_graph
>>> import networkx
>>> G = Graph()
>>> _ = gnx = networkx.Graph()
>>> _ = gnx.add_edge(Integer(0), Integer(1))
>>> _ = gnx.add_edge(Integer(1), Integer(2))
>>> from_networkx_graph(G, gnx)
>>> 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)]

>>> from sage.all import *
>>> # needs networkx
>>> G = Graph()
>>> gnx = networkx.MultiGraph()
>>> _ = gnx.add_edge(Integer(0), Integer(1))
>>> _ = gnx.add_edge(Integer(0), Integer(1))
>>> from_networkx_graph(G, gnx)
>>> G.edges(sort=True, labels=False)
[(0, 1), (0, 1)]
>>> G = Graph()
>>> from_networkx_graph(G, gnx, multiedges=False)
>>> 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)]

>>> from sage.all import *
>>> # needs networkx
>>> G = Graph()
>>> D = networkx.DiGraph()
>>> _ = D.add_edge(Integer(0), Integer(1))
>>> from_networkx_graph(G, D)
>>> G.edges(sort=True, labels=False)
[(0, 1)]
>>> G = Graph()
>>> _ = D.add_edge(Integer(1), Integer(0))
>>> from_networkx_graph(G, D)
>>> 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)]

>>> from sage.all import *
>>> # needs networkx
>>> G = Graph()
>>> D = networkx.MultiDiGraph()
>>> _ = D.add_edge(Integer(0), Integer(1))
>>> _ = D.add_edge(Integer(1), Integer(0))
>>> _ = D.add_edge(Integer(1), Integer(0))
>>> D.edges()
OutMultiEdgeDataView([(0, 1), (1, 0), (1, 0)])
>>> from_networkx_graph(G, D)
>>> 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)]

>>> from sage.all import *
>>> # needs networkx
>>> from sage.graphs.graph_input import from_networkx_graph
>>> import networkx
>>> G = DiGraph()
>>> _ = gnx = networkx.DiGraph()
>>> _ = gnx.add_edge(Integer(0), Integer(1))
>>> _ = gnx.add_edge(Integer(1), Integer(2))
>>> from_networkx_graph(G, gnx)
>>> 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)]

>>> from sage.all import *
>>> # needs networkx
>>> G = DiGraph()
>>> gnx = networkx.MultiDiGraph()
>>> _ = gnx.add_edge(Integer(0), Integer(1))
>>> _ = gnx.add_edge(Integer(0), Integer(1))
>>> from_networkx_graph(G, gnx)
>>> G.edges(sort=True, labels=False)
[(0, 1), (0, 1)]
>>> G = DiGraph()
>>> from_networkx_graph(G, gnx, multiedges=False)
>>> 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)]

>>> from sage.all import *
>>> # needs networkx
>>> G = DiGraph()
>>> H = networkx.Graph()
>>> _ = H.add_edge(Integer(0), Integer(1))
>>> from_networkx_graph(G, H)
>>> 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)]

>>> from sage.all import *
>>> # needs networkx
>>> G = DiGraph()
>>> H = networkx.MultiGraph()
>>> _ = H.add_edge(Integer(0), Integer(1))
>>> _ = H.add_edge(Integer(0), Integer(1))
>>> _ = H.add_edge(Integer(0), Integer(1))
>>> H.edges()
MultiEdgeDataView([(0, 1), (0, 1), (0, 1)])
>>> from_networkx_graph(G, H)
>>> G.edges(labels=False, sort=True)
[(0, 1), (0, 1), (0, 1), (1, 0), (1, 0), (1, 0)]
>>> G = DiGraph()
>>> from_networkx_graph(G, H, multiedges=False)
>>> 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)[source]

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

>>> from sage.all import *
>>> from sage.graphs.graph_input import from_oriented_incidence_matrix
>>> g = DiGraph()
>>> im = digraphs.Circuit(Integer(10)).incidence_matrix()                              # needs sage.modules
>>> from_oriented_incidence_matrix(g, im)                                     # needs sage.modules
>>> g.is_isomorphic(digraphs.Circuit(Integer(10)))                                     # needs sage.modules
True
sage.graphs.graph_input.from_seidel_adjacency_matrix(G, M)[source]

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

>>> from sage.all import *
>>> from sage.graphs.graph_input import from_seidel_adjacency_matrix
>>> g = Graph()
>>> sam = graphs.PetersenGraph().seidel_adjacency_matrix()                    # needs sage.modules
>>> from_seidel_adjacency_matrix(g, sam)                                      # needs sage.modules
>>> g.is_isomorphic(graphs.PetersenGraph())                                   # needs sage.modules
True
sage.graphs.graph_input.from_sparse6(G, g6_string)[source]

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

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