Graphs Core API

Core

The core utilities module provides foundational functions for graph analysis and neighborhood exploration.

graphcalc.graphs.core.basics.K_4_free(G: Graph | SimpleGraph) → bool[source]

Returns True if G does not contain an induced subgraph isomorphic to the complete graph on 4 vertices, and False otherwise.

Parameters:

G (NetworkX graph) – An undirected graph.

Returns:

True if G does not contain the complete graph K_4 as a subgraph, False otherwise.

Return type:

boolean

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph, star_graph

>>> G = complete_graph(4)
>>> gc.K_4_free(G)
False

>>> H = star_graph(6)
>>> gc.triangle_free(H)
True
class graphcalc.graphs.core.basics.SimpleGraph(*args, backend=None, **kwargs)[source]

Bases: Graph

A subclass of networkx.Graph with additional functionality.

Features: - Optional name and info attributes for metadata. - Default integer labels for nodes. - Methods to read and write edge lists to/from CSV files. - Method to draw the graph using Matplotlib.

Parameters:

  • edges (list of tuple, optional) – A list of edges to initialize the graph.

  • nodes (list, optional) – A list of nodes to initialize the graph.

  • name (str, optional) – An optional name for the graph.

  • info (str, optional) – Additional information about the graph.

  • *args (arguments) – Arguments passed to the base networkx.Graph class.

  • **kwargs (arguments) – Arguments passed to the base networkx.Graph class.

complement()[source]

Returns the complement of the graph as a GraphCalc SimpleGraph.

This ensures that constraints specific to SimpleGraph or its subclasses are not applied to the complement graph.

Returns:

The complement of the graph.

Return type:

graphcalc.core.basics.SimpleGraph

Examples

>>> import graphcalc.graphs as gc
>>> G = gc.SimpleGraph()
>>> G.add_edges_from([(0, 1), (1, 2), (2, 3)])
>>> H = G.complement()
draw(with_labels=True, node_color='lightblue', node_size=500, font_size=10)[source]

Draw the graph using Matplotlib.

Parameters:

  • with_labels (bool, optional) – Whether to display node labels (default is True).

  • node_color (str or list, optional) – The color of the nodes (default is “lightblue”).

  • node_size (int, optional) – The size of the nodes (default is 500).

  • font_size (int, optional) – The font size of the labels (default is 10).

get_adjacency_matrix(as_numpy_array=True)[source]

Returns the adjacency matrix of the graph.

Parameters:

as_numpy_array (bool, optional) – If True (default), returns the adjacency matrix as a NumPy array. If False, returns the adjacency matrix as a SciPy sparse matrix.

Returns:

The adjacency matrix of the graph.

Return type:

numpy.ndarray or scipy.sparse.csr_matrix

Examples

>>> import graphcalc.graphs as gc
>>> G = gc.SimpleGraph()
>>> G.add_edges_from([(0, 1), (1, 2), (2, 3)])
>>> adjacency_matrix = G.get_adjacency_matrix()
>>> print(adjacency_matrix)
[[0. 1. 0. 0.]
 [1. 0. 1. 0.]
 [0. 1. 0. 1.]
 [0. 0. 1. 0.]]
read_adjacency_matrix(filepath, delimiter=None)[source]

Read an adjacency matrix from a file (CSV or TXT) and create the graph.

Parameters:

  • filepath (str) – The path to the file containing the adjacency matrix.

  • delimiter (str, optional) – The delimiter used in the file (default is ‘,’ for CSV and whitespace for TXT).

Raises:

  • FileNotFoundError – If the file does not exist.

  • ValueError – If the file format is invalid or the adjacency matrix is not square.

read_edge_list(filepath, delimiter=None)[source]

Read an edge list from a file (CSV or TXT) and add edges to the graph.

Parameters:

  • filepath (str) – The path to the file containing the edge list.

  • delimiter (str, optional) – The delimiter used in the file (default is ‘,’ for CSV and whitespace for TXT).

Return type:

None

Raises:

  • FileNotFoundError – If the file does not exist.

  • ValueError – If the file format is invalid.

Notes

  • For CSV files, the file must have a header with “Source” and “Target”.

  • For TXT files, the file should contain one edge per line with node pairs separated by whitespace.

write_edgelist_to_csv(filepath)[source]

Write the edge list of the graph to a CSV file.

Parameters:

filepath (str) – The path to the CSV file where the edge list will be written.

graphcalc.graphs.core.basics.average_shortest_path_length(G: Graph | SimpleGraph) → float[source]

Returns the average shortest path length of the graph.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

The average shortest path length of the graph.

Return type:

float

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> gc.average_shortest_path_length(G)
1.6666666666666667
graphcalc.graphs.core.basics.bipartite(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is both connected and bipartite.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is bipartite, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = nx.path_graph(4)
>>> gc.bipartite(G)
True
graphcalc.graphs.core.basics.chordal(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is chordal.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is chordal, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph

>>> G = complete_graph(4)
>>> gc.chordal(G)
True
graphcalc.graphs.core.basics.claw_free(G: Graph | SimpleGraph) → bool[source]

Checks if a graph is claw-free. A claw is a tree with three leaves adjacent to a single vertex.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is claw-free, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph, star_graph

>>> G = path_graph(4)
>>> gc.claw_free(G)
True

>>> H = star_graph(6)
>>> gc.claw_free(H)
False
graphcalc.graphs.core.basics.cograph(G: Graph | SimpleGraph) → bool[source]

Determine whether a graph is a cograph (P4-free).

A cograph is any graph that contains no induced path on four vertices (P4). Equivalently, the class is generated from K1 by repeatedly taking disjoint unions and joins; or, recursively: a graph is a cograph iff it has at most one vertex, or it is disconnected and each connected component is a cograph, or its complement is disconnected and each complement-component induces a cograph.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – An undirected graph (not necessarily connected).

Returns:

True if the graph is a cograph (P4-free), False otherwise.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph, complete_graph, cycle_graph

>>> # P4 is not a cograph
>>> gc.cograph(path_graph(4))
False

>>> # Complete graphs are cographs
>>> gc.cograph(complete_graph(5))
True

>>> # C4 is P4-free, hence a cograph
>>> gc.cograph(cycle_graph(4))
True
graphcalc.graphs.core.basics.connected(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is connected.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is connected, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> gc.connected(G)
True
graphcalc.graphs.core.basics.connected_and_K_4_free(G: Graph | SimpleGraph) → bool[source]

Returns True if G is connected and does not contain an induced subgraph isomorphic to the complete graph on 4 vertices, and False otherwise.

Parameters:

G (NetworkX graph) – An undirected graph.

Returns:

True if G is connected and does not contain the complete graph K_4 as a subgraph, False otherwise.

Return type:

boolean

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph

>>> G = complete_graph(4)
>>> gc.connected_and_K_4_free(G)
False
graphcalc.graphs.core.basics.connected_and_bipartite(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is both connected and bipartite.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is connected and bipartite, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = nx.path_graph(4)
>>> gc.connected_and_bipartite(G)
True
graphcalc.graphs.core.basics.connected_and_chordal(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is both connected and chordal.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is connected and chordal, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph

>>> G = complete_graph(4)
>>> gc.connected_and_chordal(G)
True
graphcalc.graphs.core.basics.connected_and_claw_free(G: Graph | SimpleGraph) → bool[source]

Checks if a graph is claw-free. A claw is a tree with three leaves adjacent to a single vertex. A graph is connected if there is a path between every pair of vertices.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is claw-free, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> gc.connected_and_claw_free(G)
True
graphcalc.graphs.core.basics.connected_and_cograph(G: Graph | SimpleGraph) → bool[source]

Determine whether a graph is connacter and a cograph (P4-free).

A cograph is any graph that contains no induced path on four vertices (P4). Equivalently, the class is generated from K1 by repeatedly taking disjoint unions and joins; or, recursively: a graph is a cograph iff it has at most one vertex, or it is disconnected and each connected component is a cograph, or its complement is disconnected and each complement-component induces a cograph.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – An undirected graph (not necessarily connected).

Returns:

True if the graph is connected and a cograph (P4-free), False otherwise.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph, complete_graph, cycle_graph

>>> # P4 is not a cograph
>>> gc.connected_and_cograph(path_graph(4))
False

>>> # Complete graphs are cographs
>>> gc.connected_and_cograph(complete_graph(5))
True

>>> # C4 is P4-free, hence a cograph
>>> gc.connected_and_cograph(cycle_graph(4))
True
graphcalc.graphs.core.basics.connected_and_cubic(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is both connected and cubic.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is connected and cubic, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import petersen_graph

>>> G = petersen_graph()
>>> gc.connected_and_cubic(G)
True
graphcalc.graphs.core.basics.connected_and_eulerian(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is both connected and Eulerian.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is connected and Eulerian, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph

>>> G = cycle_graph(4)
>>> gc.connected_and_eulerian(G)
True
graphcalc.graphs.core.basics.connected_and_planar(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is both connected and planar.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is connected and planar, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph

>>> G = cycle_graph(4)
>>> gc.connected_and_planar(G)
True
graphcalc.graphs.core.basics.connected_and_regular(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is both connected and regular.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is connected and regular, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph

>>> G = cycle_graph(4)
>>> gc.connected_and_regular(G)
True
graphcalc.graphs.core.basics.connected_and_subcubic(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is both connected and subcubic.

A graph is subcubic if the degree of every vertex is at most 3. A graph is connected if there is a path between every pair of vertices.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is connected and subcubic, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph, path_graph, star_graph

>>> G = cycle_graph(4)  # Degree of all nodes is 2, connected
>>> gc.connected_and_subcubic(G)
True

>>> H = path_graph(5)  # Maximum degree is 2, connected
>>> gc.connected_and_subcubic(H)
True

>>> I = star_graph(4)  # Maximum degree is 4, not subcubic
>>> gc.connected_and_subcubic(I)
False

>>> J = gc.SimpleGraph()
>>> J.add_edges_from([(1, 2), (3, 4)])  # Disconnected graph
>>> connected_and_subcubic(J)
False
graphcalc.graphs.core.basics.connected_and_triangle_free(G: Graph | SimpleGraph) → bool[source]

Returns True if G is connected and triangle-free, and False otherwise.

A graph is triangle-free if it contains no induced subgraph isomorphic to the complete graph on 3 vertices.

Parameters:

G (NetworkX graph) – An undirected graph.

Returns:

True if G is connected and triangle-free, False otherwise.

Return type:

boolean

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph

>>> G = complete_graph(4)
>>> gc.connected_and_triangle_free(G)
False
graphcalc.graphs.core.basics.cubic(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is cubic.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is cubic, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import petersen_graph

>>> G = petersen_graph()
>>> gc.cubic(G)
True
graphcalc.graphs.core.basics.diameter(G: Graph | SimpleGraph) → int[source]

Returns the diameter of the graph.

The diameter is the maximum shortest path length between any pair of nodes.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

The diameter of the graph.

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> gc.diameter(G)
3
graphcalc.graphs.core.basics.eulerian(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is Eulerian.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is Eulerian, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph

>>> G = cycle_graph(4)
>>> gc.eulerian(G)
True
graphcalc.graphs.core.basics.is_C4_free(G)[source]

Test whether a graph is C4-free (contains no 4-cycle as a subgraph).

This function returns True iff \(G\) contains no copy of the 4-cycle \(C_4\) as a (not-necessarily-induced) subgraph.

Characterization used

An undirected simple graph contains a (not necessarily induced) 4-cycle iff there exist distinct vertices \(u \neq v\) having at least two distinct common neighbors. Indeed, if \(x\) and \(y\) are distinct common neighbors of \(u\) and \(v\), then the edges

\[ux,\; xv,\; vy,\; yu\]

form a 4-cycle subgraph \(u-x-v-y-u\).

If additional edges among these four vertices exist (e.g. \(uv\) or \(xy\)), they appear as chords; the 4-cycle is still present as a subgraph.

param G:

Intended for finite simple undirected graphs. The test is based on common-neighbor intersections computed via G.neighbors(u) and assumes undirected adjacency.

If you pass a directed graph, neighbors are interpreted according to NetworkX’s directed neighbor semantics (successors), which typically does not match the undirected notion of a 4-cycle; convert first via G.to_undirected() if desired.

type G:

networkx.Graph-like

returns:

True iff \(G\) contains no (not-necessarily-induced) \(C_4\) subgraph.

rtype:

bool

Notes

  • This checks for \(C_4\) as a subgraph, not as an induced subgraph. In particular, graphs that contain a 4-cycle with one or both diagonals are not C4-free.

  • Graphs with fewer than 4 vertices are vacuously C4-free.

Complexity

Let \(n=|V(G)|\) and \(m=|E(G)|\). Building neighbor sets takes \(O(n+m)\) time. The code then checks all \(\binom{n}{2}\) unordered vertex pairs and computes set intersections. In the worst case (dense graphs) the runtime is \(O(n^3)\), and it is typically faster on sparse graphs.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> gc.is_C4_free(nx.cycle_graph(4))
False
>>> gc.is_C4_free(nx.complete_graph(4))  # contains many C4 subgraphs (with chords)
False
>>> gc.is_C4_free(nx.path_graph(6))
True
graphcalc.graphs.core.basics.is_induced_C4_free(G)[source]

Test whether a graph is induced-C4-free (contains no induced 4-cycle).

This function returns True iff \(G\) contains no induced subgraph isomorphic to \(C_4\). Equivalently, there do not exist four vertices whose induced subgraph is exactly a 4-cycle.

Characterization used

An undirected simple graph contains an induced \(C_4\) iff there exist distinct vertices \(u \neq v\) (the opposite vertices of the cycle) such that:

  1. \(u\) and \(v\) are nonadjacent,

  2. \(u\) and \(v\) have two distinct common neighbors \(x\) and \(y\), and

  3. \(x\) and \(y\) are nonadjacent.

Then the induced subgraph on \(\{u,x,v,y\}\) has edges \(ux, xv, vy, yu\) and no chords, hence it is exactly \(C_4\).

param G:

Intended for finite simple undirected graphs. The test uses G.has_edge and common-neighbor intersections from G.neighbors.

If you pass a directed graph, adjacency and neighbor semantics follow NetworkX’s directed conventions and typically do not match the undirected induced-cycle notion; convert first via G.to_undirected() if that matches your intent.

type G:

networkx.Graph-like

returns:

True iff \(G\) contains no induced \(C_4\).

rtype:

bool

Notes

  • This property is strictly weaker than being C4-free as a subgraph: a graph may contain 4-cycles with chords (hence not be C4-free) yet still be induced-C4-free. For example, \(K_4\) contains many 4-cycles as subgraphs but has no induced \(C_4\).

  • Graphs with fewer than 4 vertices are vacuously induced-C4-free.

Complexity

Building neighbor sets takes \(O(n+m)\). The outer loop considers all unordered pairs \(\{u,v\}\) (i.e. \(O(n^2)\) pairs). For each nonadjacent pair, it inspects pairs within the common-neighbor set; in the worst case this can be \(O(n^4)\) for dense graphs, though it is typically much faster on sparse graphs.

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> gc.is_induced_C4_free(nx.cycle_graph(4))
False
>>> gc.is_induced_C4_free(nx.complete_graph(4))  # has C4 subgraphs but no induced C4
True
>>> gc.is_induced_C4_free(nx.path_graph(6))
True
graphcalc.graphs.core.basics.isolate_free(G: Graph | SimpleGraph) → bool[source]

Determine whether a graph is isolate-free (no degree-0 vertices).

A graph is isolate-free if every vertex has degree at least 1.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – An undirected graph.

Returns:

True if minimum degree δ(G) ≥ 1 (or G is empty), False otherwise.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> import networkx as nx
>>> H = nx.path_graph(4)
>>> gc.isolate_free(H)
True
>>> H.add_node(100)  # add an isolated vertex
>>> gc.isolate_free(H)
False
graphcalc.graphs.core.basics.nontrivial(G: Graph | SimpleGraph) → bool[source]

Determine whether a graph is nontrivial.

A graph is nontrivial if it has at least two vertices, i.e., \(|V(G)| \ge 2\).

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if \(|V(G)| \ge 2\), and False otherwise.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> import networkx as nx
>>> gc.nontrivial(nx.path_graph(1))
False
>>> gc.nontrivial(nx.path_graph(2))
True
graphcalc.graphs.core.basics.order(G: Graph | SimpleGraph) → int[source]

Returns the order of a graph, which is the number of vertices.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

The order of the graph.

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> gc.order(G)
4
graphcalc.graphs.core.basics.planar(G: Graph | SimpleGraph) → bool[source]

Determine whether a graph is planar.

A graph is planar if it can be drawn in the plane without any edges crossing. This function uses the Boyer–Myrvold planarity test implemented in NetworkX.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – An undirected graph.

Returns:

True if the graph is planar, False otherwise.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph, complete_graph

>>> G = cycle_graph(5)
>>> gc.planar(G)
True

>>> H = complete_graph(5)
>>> gc.planar(H)
False
graphcalc.graphs.core.basics.radius(G: Graph | SimpleGraph) → int[source]

Returns the radius of the graph.

The radius is the minimum eccentricity among all vertices.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

The radius of the graph.

Return type:

int

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> gc.radius(G)
2
graphcalc.graphs.core.basics.regular(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is regular.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is regular, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph

>>> G = cycle_graph(4)
>>> gc.regular(G)
True
graphcalc.graphs.core.basics.size(G: Graph | SimpleGraph) → int[source]

Returns the size of a graph, which is the number of edges.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

The size of the graph.

Return type:

int

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> gc.size(G)
3
graphcalc.graphs.core.basics.subcubic(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is subcubic.

A graph is subcubic if the degree of every vertex is at most 3.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is subcubic, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import cycle_graph

>>> G = nx.cycle_graph(4)  # Degree of all nodes is 2
>>> gc.subcubic(G)
True
graphcalc.graphs.core.basics.tree(G: Graph | SimpleGraph) → bool[source]

Checks if the graph is a tree.

Parameters:

G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

Returns:

True if the graph is a tree, otherwise False.

Return type:

bool

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = nx.path_graph(4)
>>> gc.tree(G)
True
graphcalc.graphs.core.basics.triangle_free(G: Graph | SimpleGraph) → bool[source]

Returns True if G is triangle-free, and False otherwise.

A graph is triangle-free if it contains no induced subgraph isomorphic to the complete graph on 3 vertices.

Parameters:

G (NetworkX graph) – An undirected graph.

Returns:

True if G is triangle-free, False otherwise.

Return type:

boolean

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import complete_graph, star_graph

>>> G = complete_graph(4)
>>> gc.triangle_free(G)
False

>>> H = star_graph(6)
>>> gc.triangle_free(H)
True
graphcalc.graphs.core.neighborhoods.closed_neighborhood(G: Graph | SimpleGraph, v: Hashable) → Set[Hashable][source]

Returns the closed neighborhood of a vertex in a graph.

The closed neighborhood of a vertex v consists of v and all vertices directly connected to v by an edge.

Parameters:

  • G (nx.Graph) – The input graph.

  • v (int) – The vertex whose closed neighborhood is to be computed.

Returns:

A set of vertices including v and its neighbors.

Return type:

set

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> gc.closed_neighborhood(G, 1)
{0, 1, 2}
graphcalc.graphs.core.neighborhoods.neighborhood(G: Graph | SimpleGraph, v: Hashable) → Set[Hashable][source]

Returns the open neighborhood of a vertex in a graph.

The neighborhood of a vertex v consists of all vertices directly connected to v by an edge.

Parameters:

  • G (networkx.Graph or graphcalc.SimpleGraph) – The input graph.

  • v (hashable) – The vertex whose neighborhood is to be computed.

Returns:

A set of vertices adjacent to v.

Return type:

set

Raises:

ValueError – If the vertex v is not in the graph.

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)
>>> gc.neighborhood(G, 1)
{0, 2}
graphcalc.graphs.core.neighborhoods.set_closed_neighbors(G: Graph | SimpleGraph, S: Set[Hashable] | List[Hashable]) → Set[Hashable][source]

Returns the set of closed neighbors of a set of vertices in a graph.

The closed neighbors of a set of vertices S are all vertices in S along with all vertices adjacent to at least one vertex in S.

Parameters:

  • G (nx.Graph) – The input graph.

  • S (set) – A set of vertices whose closed neighbors are to be computed.

Returns:

A set of vertices in S and their neighbors.

Return type:

set

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = nx.path_graph(4)
>>> gc.set_closed_neighbors(G, {1, 2})
{0, 1, 2, 3}
graphcalc.graphs.core.neighborhoods.set_neighbors(G: Graph | SimpleGraph, S: Set[Hashable] | List[Hashable]) → Set[Hashable][source]

Returns the set of neighbors of a set of vertices in a graph.

The neighbors of a set of vertices S are all vertices adjacent to at least one vertex in S.

Parameters:

  • G (nx.Graph) – The input graph.

  • S (set) – A set of vertices whose neighbors are to be computed.

Returns:

A set of vertices adjacent to at least one vertex in S.

Return type:

set

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.generators import path_graph

>>> G = path_graph(4)
>>> gc.set_neighbors(G, {1, 2})
{0, 1, 2, 3}