Structural Properties¶
The following functions allow the user to check for certain structural graph properties.
-
jgrapht.properties.has_multipleedges(graph)[source]¶ Check if a graph has multiple-edges.
- Parameters
graph – the graph
- Returns
True if it has multiple-edges, False otherwise
-
jgrapht.properties.has_ore(graph)[source]¶ Check whether an undirected graph meets Ore’s condition to be Hamiltonian.
- Parameters
graph – The input graph
- Returns
True if the graph meets Ore’s condition, False otherwise
-
jgrapht.properties.has_selfloops(graph)[source]¶ Check if a graph has self-loops.
- Parameters
graph – the graph
- Returns
True if it has self-loops, False otherwise
-
jgrapht.properties.is_bipartite(graph)[source]¶ Check if a graph is bipartite.
- Parameters
graph – the graph
- Returns
True if the graph is bipartite, False otherwise
-
jgrapht.properties.is_chordal(graph)[source]¶ Check where the graph is chordal.
- Parameters
graph – the graph
- Returns
True if the graph is chordal, False otherwise
-
jgrapht.properties.is_complete(graph)[source]¶ Check if the graph is complete.
For undirected graphs, each pair of vertices must be connected by a single edge. For directed graphs, each pair of vertices must be connected by one pair of edges, one in each direction.
- Parameters
graph – the graph
- Returns
True if the graph is complete, False otherwise
-
jgrapht.properties.is_cubic(graph)[source]¶ Check whether a graph is cubic.
A graph is cubic if all vertices have degree equal to three.
- Parameters
graph – the graph
- Returns
True if the graph is cubic, False otherwise
-
jgrapht.properties.is_empty_graph(graph)[source]¶ Check whether the graph is empty. An empty graph with n nodes contains n isolates nodes but no edges.
- Parameters
graph – the graph
- Returns
True if the graph is empty, False otherwise.
-
jgrapht.properties.is_eulerian(graph)[source]¶ Check whether a graph is Eulerian.
An Eulerian graph is a graph containing an Eulerian cycle.
- Parameters
graph – the graph
- Returns
True if the graph is Eulerian, False otherwise
-
jgrapht.properties.is_forest(graph)[source]¶ Check if an undirected graph is a forest.
- Parameters
graph – the graph
- Returns
True if the graph is a forest, False otherwise
-
jgrapht.properties.is_k33_subdivision(graph)[source]¶ Check whether a graph is a \(K_{3,3}\) subdivision.
- Parameters
graph – the graph
- Returns
True if the graph is a \(K_{3,3}\) subdivision, False otherwise
-
jgrapht.properties.is_k5_subdivision(graph)[source]¶ Check whether a graph is a \(K_{5}\) subdivision.
- Parameters
graph – the graph
- Returns
True if the graph is a \(K_{5}\) subdivision, False otherwise
-
jgrapht.properties.is_kuratowski_subdivision(graph)[source]¶ Check whether a graph is a \(K_{3,3}\) or a \(K_5\) subdivision.
- Parameters
graph – the graph
- Returns
True if the graph is a \(K_{3,3}\) or a \(K_5\) subdivision, False otherwise
-
jgrapht.properties.is_overfull(graph)[source]¶ Check if the graph is overfull.
A graph is overfull if \(m > \Delta(G) \lfloor n/2 \rfloor\) where \(\Delta(G)\) is the maximum degree in the graph.
- Parameters
graph – the graph
- Returns
True if the graph is ovefull, False otherwise
-
jgrapht.properties.is_perfect(graph)[source]¶ Check whether a graph is perfect.
- Parameters
graph – the graph
- Returns
True if the graph is perfect, False otherwise
-
jgrapht.properties.is_planar(graph)[source]¶ Check whether a graph is planar.
- Parameters
graph – the graph
- Returns
True if the graph is planar, False otherwise
-
jgrapht.properties.is_simple(graph)[source]¶ Check if a graph is simple. A graph is simple if it has no self-loops and multiple edges.
- Parameters
graph – the graph
- Returns
True if simple, False otherwise
-
jgrapht.properties.is_split(graph)[source]¶ Test whether an undirected graph is a split graph.
- Parameters
graph – the graph
- Returns
True if the graph is a split graph, False otherwise
-
jgrapht.properties.is_strongly_connected(graph)[source]¶ Test whether a graph is strongly connected.
- Parameters
graph – the graph
- Returns
True if strongly-connected, False otherwise
-
jgrapht.properties.is_tree(graph)[source]¶ Check if an undirected graph is a tree.
- Parameters
graph – the graph
- Returns
True if the graph is a tree, False otherwise
-
jgrapht.properties.is_trianglefree(graph)[source]¶ Check whether an undirected graph is triangle free.
- Parameters
graph – the graph
- Returns
True if the graph is triangle free, False otherwise