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
|
__metaclass__
Metaclass for defining Abstract Base Classes (ABCs).
|
|
__init__(self,
representation)
Constructs an instance of this graph, and sets the hidden
representation to the parameter. |
source code
|
|
|
|
|
|
|
|
|
|
|
|
boolean
|
isEdge(self,
i,
j)
Returns True if and only if there exists and edge between i and j |
source code
|
|
number
|
|
number
|
|
number
|
|
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
|
|
Inherited from object :
__delattr__ ,
__format__ ,
__getattribute__ ,
__hash__ ,
__new__ ,
__reduce__ ,
__reduce_ex__ ,
__setattr__ ,
__sizeof__ ,
__str__ ,
__subclasshook__
|
|
|
|
read(cls,
stream)
Constructs a graph to be equivalent to some stream data. |
source code
|
|
|
__abstractmethods__ = frozenset([ ' defaultConnector ' , ' inDegree ...
|
|
_abc_cache = set([ ])
|
|
_abc_negative_cache = set([ ])
|
|
_abc_negative_cache_version = 10
|
|
_abc_registry = set([ ])
|
Inherited from object :
__class__
|
__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__
|
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:
|
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:
|
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
|
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.
|
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.
|
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.
|
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.
|
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.
|
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:
- Raises:
ValueError - if i is not a valid vertex label in this graph.
|
Returns the number of vertices within this graph.
- Returns: number
- the number of vertices in this graph.
|
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:
|
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.
|
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.
|
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__
|
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
|
__abstractmethods__
- Value:
frozenset([ ' defaultConnector ' , ' inDegree ' , ' size ' ])
|
|