Main Overview

# Class `Graph`

Class `Graph`: Graph (in the sense of graph theory)
A Graph consists of nodes and edges. An edge (class Edge) connects two nodes.
Edges optionally may have a weight.

Although a pure Graph does not carry geometrical data, mathGUIde allows to attach positions to nodes corresponding to a Graph representation in the Graph window.

Overview:

## Constructor

Graph ()

## Class methods (static methods)

Method | Meaning
complete (n, r=130, margin=20) | Complete Graph of order n, displayed on a circle with radius r.
completeBipartite (n1, n2) | Complete bipartite Graph with partition sizes n1 and n2.
example1 () |
fromShortRepr (s) | Makes the Graph from the short representation s
petersen (r=150, margin=20) | The Peterson Graph

## Operators

Operator | Meaning
str(x) |

## Object Methods

Method | Meaning
addEdges (*edges) |
addNodes (*nodes) |
adjacent (node1, node2) | Determines wether node1 and node2 are adjacent (bool return value) in G.
adjacentNodes (node) | Returns a sorted list of all nodes of G adjacent to node.
cancelHighlight () | Resets all highlighted edges to normal state.
complement () | Returns the graph with the same vertices as G, such that two vertices are adjacent if and only if they are not adjacent in G.
componentsCount () | The number connectivity components of the Graph G
connectedNodes (node) | Returns a list of all nodes of G which are connected with node (including node).
copy () | independent copy ("clone") of G
degree (node) | Returns the degree of node (count of adjacent nodes)
display (n=0) | Displays the Graph G in the n-th Graph tab.
edge (node1, node2) | The connecting edge between the two nodes
highlightMinimalSpanTree (trace=False) | Highlightes a minimal spanning tree using the Kruskal algorithm.
highlightShortestPath (startNode, goalNode) | Highlightes a shortest path (if existent) from startNode to goalNode using the Dijkstra algorithm.
incidentEdges (node) |
isConnected () | Returns a truth value indicating wether the Graph G is connected
isTree () | Returns a truth value indicating wether the Graph G is a tree
isomorphic (H) | Determines wether G and H are isomorphic Graphs.
order () | Order (number of vertices) of the Graph G.
reduceToHighlightedEdges () | Removes all not highlighted edges from the Graph G.
shortRepr () | short representation of Graph G as string

# Constructor

### Graph

Constructor

Usage: `Graph()`

# Class methods (static methods)

### complete

Graph.complete(n, r=130, margin=20)

Usage: `Graph.complete(n, r=130, margin=20)`

Description:
Complete Graph of order n, displayed on a circle with radius r.

### completeBipartite

Graph.completeBipartite(n1,n2)

Usage: `Graph.completeBipartite(n1, n2)`

Description:
Complete bipartite Graph with partition sizes n1 and n2.

### example1

Graph.example1()

Usage: `Graph.example1()`

### fromShortRepr

Graph.fromShortRepr(s)

Usage: `Graph.fromShortRepr(s)`

Description:
Makes the Graph from the short representation s

### petersen

Graph.petersen()

Usage: `Graph.petersen(r=150, margin=20)`

Description:
The Peterson Graph
It serves as an example and counterexample for many problems in graph theory.

# Operators

### str(x)

Object representation as string

Usage: `str(x)`

Description:

# Object Methods

### addEdges

Usage: `self.addEdges(*edges)`

### addNodes

Usage: `self.addNodes(*nodes)`

### adjacent

G.adjacentNodes(node1, node2)

Usage: `self.adjacent(node1, node2)`

Description:
Determines wether node1 and node2 are adjacent (bool return value) in G.

### adjacentNodes

G.adjacentNodes(node)

Usage: `self.adjacentNodes(node)`

Description:
Returns a sorted list of all nodes of G adjacent to node.

### cancelHighlight

G.cancelHighlight()

Usage: `self.cancelHighlight()`

Description:
Resets all highlighted edges to normal state.

### complement

G.complement()

Usage: `self.complement()`

Description:
Returns the graph with the same vertices as G, such that two vertices are adjacent if and only if they are not adjacent in G.

### componentsCount

G.componentsCount()

Usage: `self.componentsCount()`

Description:
The number connectivity components of the Graph G

### connectedNodes

G.componentsCount()

Usage: `self.connectedNodes(node)`

Description:
Returns a list of all nodes of G which are connected with node (including node).

### copy

G.copy()

Usage: `self.copy()`

Description:
independent copy ("clone") of G

### degree

G.degree(node)

Usage: `self.degree(node)`

Description:
Returns the degree of node (count of adjacent nodes)

### display

G.display(n=0)

Usage: `self.display(n=0)`

Description:
Displays the Graph G in the n-th Graph tab.
if n == 0, the Graph is displayed in the active Graph window.

### edge

G.edge(node1, node2)

Usage: `self.edge(node1, node2)`

Description:
The connecting edge between the two nodes
If node1 and node2 are adjacent, the connecting edge is returned, otherwise `None`.

### highlightMinimalSpanTree

G.minimalSpanTree(trace=False)

Usage: `g.highlightMinimalSpanTree(trace=False)`

Description:
Highlightes a minimal spanning tree using the Kruskal algorithm.
If `trace` is `True`, all steps are printed.

### highlightShortestPath

G.highlightShortestPath(startNode, goalNode)

Usage: `self.highlightShortestPath(startNode, goalNode)`

Description:
Highlightes a shortest path (if existent) from startNode to goalNode using the Dijkstra algorithm.
Returns the length of the path (or inf if there is no connection).
Use the method `display` in order to make the highlighting visible.

### incidentEdges

Usage: `self.incidentEdges(node)`

### isConnected

G.isConnected()

Usage: `self.isConnected()`

Description:
Returns a truth value indicating wether the Graph G is connected

### isTree

G.isTree()

Usage: `self.isTree()`

Description:
Returns a truth value indicating wether the Graph G is a tree

### isomorphic

G.isomorphic(H)

Usage: `.isomorphic(H)`

Description:
Determines wether G and H are isomorphic Graphs.

### order

G.order()

Usage: `self.order()`

Description:
Order (number of vertices) of the Graph G.

### reduceToHighlightedEdges

G.reduceToHighlightedEdges()

Usage: `self.reduceToHighlightedEdges()`

Description:
Removes all not highlighted edges from the Graph G.
The highlighting of the remaining edges is turned off.

### shortRepr

G.shortRepr()

Usage: `self.shortRepr()`

Description:
short representation of Graph G as string