Package graphadt :: Module representations :: Class Representation
[hide private]
[frames] | no frames]

Class Representation

source code

object --+
         |
        Representation
Known Subclasses:

This abstract class specifies the interface for the representation of the state within a graph.

The state of a graph is defined to be the vertices contained within it, as well as the arcs between those vertices. Vertices are always numbered consecutively, starting from zero. Deleting a vertex causes all higher numbered vertices to be renumbered.

Arcs are two-ary relations upon the set of vertices, and are directed. Arcs retain their meaning during deletion, i.e. they must be renumbered along with the vertices. An arc incident or outgoing from a deleted vertex is also deleted.

Edges are not explicitly modelled by this representation. However, by convention, the user may choose to represent an edge by a pair of symmetric arcs together represents an edge.

This class is meant to be used internally within the pyGraphADT package only. If you want to model a graph, used a subclass of the Graph type in graphadt.graphtypes.

Nested Classes [hide private]
  __metaclass__
Metaclass for defining Abstract Base Classes (ABCs).
Instance Methods [hide private]
 
read(self, stream, defaultConstructor)
Sets the state of this representation to the data contained in some stream s.
source code
 
empty(self)
Removes all vertices from this graph.
source code
 
addVertices(self, n)
Creates records for n new vertices
source code
 
removeVertex(self, i)
This method deletes the record of vertex labelled i, and all arcs connected to it.
source code
 
addArc(self, i, j)
Records that in this state there is an arc from vertex with label i to vertex with label j
source code
 
removeArc(self, i, j)
Removes a directional connection from vertex i to vertex j, from the state of this representation if it exists.
source code
boolean
isArc(self, i, j)
Returns True if and only if there is an arc connecting i to j.
source code
number
inDegree(self, i)
Returns the number of other vertices which are connected to i
source code
number Raises: ValueError if no such label i exists.
degree(self, i)
Returns the number of vertices to which vertex i connects
source code
list
neighbours(self, i)
Returns an iterable collection of all the vertices to which the vertex with index i connects
source code
number
size(self)
Returns the number of arcs in this graph, as an integer.
source code
number
selfEdges(self)
Returns the number of arcs in this representation from any vertex to itself, as an integer.
source code
number
order(self)
Returns the number of vertices in this graph.
source code
string
__str__(self)
Returns a string representation of this object's state.
source code

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

Class Variables [hide private]
  __abstractmethods__ = frozenset(['__str__', 'addArc', 'addVert...
  _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]

read(self, stream, defaultConstructor)

source code 

Sets the state of this representation to the data contained in some stream s.

This method lets this representation set its state from a stream. The parameter defaultConstructor should be the method to call to connect two Vertices in this graph.

Parameters:
  • stream (filestream supporting readlines()) - the stream must support the 'readlines()' method.
  • defaultConstructor (unbound function) - a method which can be called upon this object which specifies how connections are to be made.
Decorators:
  • @abstractmethod

empty(self)

source code 

Removes all vertices from this graph.

Decorators:
  • @abstractmethod

addVertices(self, n)

source code 

Creates records for n new vertices

Parameters:
  • n (number) - label of a vertex in this representation
Decorators:
  • @abstractmethod

removeVertex(self, i)

source code 

This method deletes the record of vertex labelled i, and all arcs connected to it. All the vertices labelled higher than this vertex are relabelled.

Parameters:
  • i (number) - a label of a vertex in this representation
Decorators:
  • @abstractmethod
Raises:
  • ValueError - if no such label i exists

addArc(self, i, j)

source code 

Records that in this state there is an arc from vertex with label i to vertex with label j

Parameters:
  • i (number) - a label of a vertex in this representation
  • j (number) - a label of a vertex in this representation
Decorators:
  • @abstractmethod
Raises:
  • ValueError - if no such labels exist

removeArc(self, i, j)

source code 

Removes a directional connection from vertex i to vertex j, from the state of this representation if it exists. If such a connection does not exist, no error is raised.

Parameters:
  • i (number) - a label of a vertex in this representation
  • j (number) - a label of a vertex in this representation
Decorators:
  • @abstractmethod
Raises:
  • ValueError - if no such labels exist

isArc(self, i, j)

source code 

Returns True if and only if there is an arc connecting i to j.

Parameters:
  • i (number) - a label of a vertex in this representation
  • j (number) - a label of a vertex in this representation
Returns: boolean
True if there is an arc from vertex with label i to vertex with label j in this state. False otherwise
Decorators:
  • @abstractmethod
Raises:
  • ValueError - if no such labels exist

inDegree(self, i)

source code 

Returns the number of other vertices which are connected to i

Parameters:
  • i (number) - a label of a vertex in this representation
Returns: number
the number of arcs incident on i, as integer.
Decorators:
  • @abstractmethod
Raises:
  • ValueError - if no such labels exist

degree(self, i)

source code 

Returns the number of vertices to which vertex i connects

Parameters:
  • i (number) - a label of a vertex in this representation
Returns: number Raises: ValueError if no such label i exists.
the number of arcs outgoing from i, as integer.
Decorators:
  • @abstractmethod

neighbours(self, i)

source code 

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

Parameters:
  • i (number) - a label of a vertex in this representation
Returns: list
all the vertices j, such that there is an arc (i, j). J must be sorted, and safe for modification.
Decorators:
  • @abstractmethod
Raises:
  • ValueError - if no such labels exist

size(self)

source code 

Returns the number of arcs in this graph, as an integer.

Returns: number
the number of arcs in this representation
Decorators:
  • @abstractmethod

selfEdges(self)

source code 

Returns the number of arcs in this representation from any vertex to itself, as an integer.

Returns: number
the number of self loops in this representation

order(self)

source code 

Returns the number of vertices in this graph.

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

__str__(self)
(Informal representation operator)

source code 

Returns a string representation of this object's state. It should always be the case that self.read() and str(self) should be compatible: the output of str should be valid input for self.read()

Returns: string
a string representation of this object's state
Decorators:
  • @abstractmethod
Overrides: object.__str__

Class Variable Details [hide private]

__abstractmethods__

Value:
frozenset(['__str__',
           'addArc',
           'addVertices',
           'degree',
           'empty',
           'inDegree',
           'isArc',
           'neighbours',
...