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

Class AdjacencyLists

source code

    object --+    
             |    
Representation --+
                 |
                AdjacencyLists

AdjacencyLists extends and realises the abstract class Representation.

AdjacencyLists stores the state of vertices and arcs as a list of lists. The arc (i,j) is represented by the list at element i containing the value j.

Nested Classes [hide private]

Inherited from Representation: __metaclass__

Instance Methods [hide private]
 
__init__(self)
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
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 Raises: ValueError if no such label i exists.
degree(self, i)
Returns the number of vertices to which vertex i connects
source code
number
inDegree(self, i)
Returns the number of other vertices which are connected to i
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
order(self)
Returns the number of vertices in this graph.
source code
number
size(self)
Returns the number of arcs in this graph, as an integer.
source code
string
__str__(self)
Returns a string representation of this object's state.
source code
 
read(self, stream, defaultConnector)
Sets the state of this representation to the data contained in some stream s.
source code

Inherited from Representation: selfEdges

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

Class Variables [hide private]
  __abstractmethods__ = frozenset([])
Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

__init__(self)
(Constructor)

source code 

x.__init__(...) initializes x; see x.__class__.__doc__ for signature

Overrides: object.__init__
(inherited documentation)

empty(self)

source code 

Removes all vertices from this graph.

Overrides: Representation.empty
(inherited documentation)

addVertices(self, n)

source code 

Creates records for n new vertices

Parameters:
  • n - label of a vertex in this representation
Overrides: Representation.addVertices
(inherited documentation)

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 - a label of a vertex in this representation
Raises:
  • ValueError - if no such label i exists
Overrides: Representation.removeVertex
(inherited documentation)

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 - a label of a vertex in this representation
  • j - a label of a vertex in this representation
Raises:
  • ValueError - if no such labels exist
Overrides: Representation.addArc
(inherited documentation)

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 - a label of a vertex in this representation
  • j - a label of a vertex in this representation
Raises:
  • ValueError - if no such labels exist
Overrides: Representation.removeArc
(inherited documentation)

isArc(self, i, j)

source code 

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

Parameters:
  • i - a label of a vertex in this representation
  • j - 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
Raises:
  • ValueError - if no such labels exist
Overrides: Representation.isArc
(inherited documentation)

degree(self, i)

source code 

Returns the number of vertices to which vertex i connects

Parameters:
  • i - 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.
Overrides: Representation.degree
(inherited documentation)

inDegree(self, i)

source code 

Returns the number of other vertices which are connected to i

Parameters:
  • i - a label of a vertex in this representation
Returns: number
the number of arcs incident on i, as integer.
Raises:
  • ValueError - if no such labels exist
Overrides: Representation.inDegree
(inherited documentation)

neighbours(self, i)

source code 

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

Parameters:
  • i - 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.
Raises:
  • ValueError - if no such labels exist
Overrides: Representation.neighbours
(inherited documentation)

order(self)

source code 

Returns the number of vertices in this graph.

Returns: number
the number of vertices in this graph
Overrides: Representation.order
(inherited documentation)

size(self)

source code 

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

Returns: number
the number of arcs in this representation
Overrides: Representation.size
(inherited documentation)

__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
Overrides: object.__str__
(inherited documentation)

read(self, stream, defaultConnector)

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 - the stream must support the 'readlines()' method.
  • defaultConstructor - a method which can be called upon this object which specifies how connections are to be made.
Overrides: Representation.read
(inherited documentation)