Package graphadt :: Module graphtypes :: Class Graph
[hide private]
[frames] | no frames]

Class Graph

source code

object --+
         |
        Graph
Known Subclasses:

This is the basic definition of a graph. A graph, defined by this class is to be a collection of consecutively-numbered vertices starting from zero, and a collection of 2-ary relations between these vertices, representing arcs or edges.

Graphs are implemented as wrappers of encapsulated Representation objects. This means that graph object code for Adjacency Lists and Adjacency Matrix representations can be identical.

Constructors: -__init__(self, representation) -> default constructor -copy(cls, g) -> copy constructor -read(cls, stream) -> file reader constructor

Mutators: -addVertices(n) -addEdge(i, j) -removeVertex(i) -removeEdge(i, j)

Accessors: -isEdge(i, j) -degree(i) -inDegree(i) -order() -size() -neighbours(i)

Utility: -__repr__() -- print a string representation of this graph

28/01/10: Graph is now an abstract class. This will not work in python 2.5

Nested Classes [hide private]
  __metaclass__
Metaclass for defining Abstract Base Classes (ABCs).
Instance Methods [hide private]
 
__init__(self, representation)
Constructs an instance of this graph, and sets the hidden representation to the parameter.
source code
 
defaultConnector(self, i, j)
Joins i and j using the default connector type for this graph.
source code
 
addVertices(self, n)
Adds n vertices to this graph.
source code
 
removeVertex(self, i)
Removes vertex with label i from this graph.
source code
 
addEdge(self, i, j)
Creates an edge between i and j
source code
 
removeEdge(self, i, j)
Removes any edge or arcs between i and j
source code
boolean
isEdge(self, i, j)
Returns True if and only if there exists and edge between i and j
source code
number
degree(self, i)
Returns the outdegree of vertex i.
source code
number
inDegree(self, i)
Returns the indegree of vertex i.
source code
number
order(self)
Returns the number of vertices within this graph.
source code
number
size(self)
Returns the number of edges of an undirected graph or the number of arcs in an directed graph.
source code
list
neighbours(self, i)
Returns an iterable collection of all the vertices to which the vertex with index i connects
source code
list
neighbors(self, i)
Returns an iterable collection of all the vertices to which the vertex with index i connects
source code
string
__repr__(self)
Equivalent of Java's toString
source code

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __setattr__, __sizeof__, __str__, __subclasshook__

Class Methods [hide private]
 
copy(cls, g)
Creates an instance of cls, which is a copy of g.
source code
 
read(cls, stream)
Constructs a graph to be equivalent to some stream data.
source code
Class Variables [hide private]
  __abstractmethods__ = frozenset(['defaultConnector', 'inDegree...
  _abc_cache = set([])
  _abc_negative_cache = set([])
  _abc_negative_cache_version = 10
  _abc_registry = set([])
Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

__init__(self, representation)
(Constructor)

source code 

Constructs an instance of this graph, and sets the hidden representation to the parameter.

Parameters:
  • representation (graphADT.representations.Representation) - the state of the graph to be copied
Overrides: object.__init__

copy(cls, g)
Class Method

source code 

Creates an instance of cls, which is a copy of g.

The instance returned by this method is distinct from g, is of type cls, and is at least as connected as g.

g need not be of the same type as cls. In fact, copying a directed graph to an undirected graph is a standard way to create its underlying graph.

Parameters:
  • cls (class) - a concrete subclass of graph
  • g (graphadt.graphtypes.Graph

    Warning: A Graph itself is an abstract class, Graph.copy(g) is an invalid method call.

    ) - the graph to be copied

defaultConnector(self, i, j)

source code 

Joins i and j using the default connector type for this graph.

The default connector is the connector (Arc or Edge) used when constructing this graph from other representations, such as when reading from file streams or copying other graphs

This method is not intended for use in external code, it is for internal code which does not know whether to create arcs or edges.

Parameters:
  • i (integer) - The label of the vertex from which the connection will be made
  • j (integer) - The label of the vertex to which the connection will be made (order is only important if the defaultConnector is an arc)
Decorators:
  • @abstractmethod

addVertices(self, n)

source code 

Adds n vertices to this graph.

This method adds n unconnected vertices to this graph. The vertices are numbered consecutively, continuing from the highest numbered vertex already in the graph.

Parameters:
  • n (integer) - the number of vertices to add
Raises:
  • ValueError - if n is negative

removeVertex(self, i)

source code 

Removes vertex with label i from this graph.

This method removes the vertex with label i from this graph. All edges connected to it are also removed. All the vertices labelled higher than this vertex are relabelled.

Parameters:
  • i (integer) - the label of the vertex to remove
Raises:
  • ValueError - if i is not a valid vertex label in this graph.

addEdge(self, i, j)

source code 

Creates an edge between i and j

This method creates an edge between i and j. Edges are bi-directional, so the order of the parameters i and j does not matter. Self-loops, i.e. edges where i == j, are allowed.

Parameters:
  • i (integer) - The label of the vertex from which the connection will be made
  • j (integer) - The label of the vertex to which the connection will be made
Raises:
  • ValueError - if either of i or j is not a valid vertex label in this graph.

removeEdge(self, i, j)

source code 

Removes any edge or arcs between i and j

This method removes the edge between i and j. If such an edge does not exist, this method will remove the arc (i, j) or (j, i), if they exist.

Parameters:
  • i (integer) - The label of a vertex in this graph
  • j (integer) - The label of a vertex in this graph
Raises:
  • ValueError - if either of i or j is not a valid vertex label in this graph.

isEdge(self, i, j)

source code 

Returns True if and only if there exists and edge between i and j

Parameters:
  • i (integer) - The label of a vertex in this graph
  • j (integer) - The label of a vertex in this graph
Returns: boolean
True iff there is a biderectional edge between i and j
Raises:
  • ValueError - if either of i or j is not a valid vertex label in this graph.

degree(self, i)

source code 

Returns the outdegree of vertex i.

This method returns the outdegree of vertex i, which is the number of vertices directly connected by outgoing edges or arcs from i.

Parameters:
  • i (integer) - The label of a vertex in this graph
Returns: number
the outdegree of vertex with label i.
Raises:
  • ValueError - if i is not a valid vertex label in this graph.

inDegree(self, i)

source code 

Returns the indegree of vertex i.

This method returns the indegree of vertex i, which is the number of vertices which directly connect to i with incoming edges or arcs.

Parameters:
  • i (integer) - The label of a vertex in this graph
Returns: number
the indegree of vertex with label i.
Decorators:
  • @abstractmethod
Raises:
  • ValueError - if i is not a valid vertex label in this graph.

order(self)

source code 

Returns the number of vertices within this graph.

Returns: number
the number of vertices in this graph.

size(self)

source code 

Returns the number of edges of an undirected graph or the number of arcs in an directed graph.

Returns: number
the number of connectors in this graph
Decorators:
  • @abstractmethod

neighbours(self, i)

source code 

Returns an iterable collection of all the vertices to which the vertex with index i connects

This method returns an iterable collection of all the neighbours of vertex i. A vertex j is defined to be the neighbour of vertex i if there exists an edge between i and j, or if there exists an arc from i to j.

Parameters:
  • i (integer) - The label of a vertex in this graph
Returns: list
the labels of the neighbours of vertex i
Raises:
  • ValueError - if i is not a valid vertex label in this graph.

neighbors(self, i)

source code 

Returns an iterable collection of all the vertices to which the vertex with index i connects

This method returns an iterable collection of all the neighbours of vertex i. A vertex j is defined to be the neighbour of vertex i if there exists an edge between i and j, or if there exists an arc from i to j.

Parameters:
  • i (integer) - The label of a vertex in this graph
Returns: list
the labels of the neighbours of vertex i
Raises:
  • ValueError - if i is not a valid vertex label in this graph.

__repr__(self)
(Representation operator)

source code 

Equivalent of Java's toString

This method returns a string representation of this graph. The precise format of this representation depends on the type of representation encapsulated within this graph.

Returns: string
string representation of this graph
Overrides: object.__repr__

read(cls, stream)
Class Method

source code 

Constructs a graph to be equivalent to some stream data.

This method reads a stream of data from a file or similar source, and creates an instance of type concrete type cls, which is set up to be equivalent to the data.

Note that an instance of type cls must accept the format of data being read.

Parameters:
  • cls (class) - a concrete subclass of graph
  • stream - the data to be duplicated
Raises:
  • ValueError - if stream is of the wrong format

Class Variable Details [hide private]

__abstractmethods__

Value:
frozenset(['defaultConnector', 'inDegree', 'size'])