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)

MethodMeaning
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

OperatorMeaning
str(x)

Object Methods

MethodMeaning
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