Home       Trees       Indices       Help   
fuzzpy
Package fuzz :: Module graph :: Class Graph
[hide private]
[frames] | no frames]

Class Graph

source code

object --+
         |
        Graph
Known Subclasses:

Crisp graph class (used for alpha cuts and crisp methods).

Nested Classes [hide private]
  _setcls
set() -> new empty set object set(iterable) -> new set object
Instance Methods [hide private]
 
__init__(self, viter=None, eiter=None, directed=True)
Construct a crisp graph from optional iterables.		 source code
str
__repr__(self)
Return the canonical representation of a graph.		 source code
str
__str__(self)
Return the string representation of a graph.		 source code
 
add_vertex(self, vertex)
Add a vertex to the graph.		 source code
 
remove_vertex(self, vertex)
Remove a vertex and all edges connected to it from the graph.		 source code
 
add_edge(self, edge)
Add an edge to the graph.		 source code
 
remove_edge(self, tail, head)
Remove an edge from the graph by tail and head.		 source code
set
vertices(self)
Return a set of vertices in the graph.		 source code
set
edges(self, tail=None, head=None)
Return a set of edges with tail and/or head optionally specified.		 source code
float
weight(self, tail, head)
Return the weight of an edge.		 source code
list
edges_by_weight(self, tail=None, head=None)
Return a list of edges, sorted in ascending order by weight, with tail and/or head optionally specified.		 source code
 
connect(self, tail, head)
Connect a pair of vertices with a new edge.		 source code
 
disconnect(self, tail, head)
Disconnect a pair of vertices by removing the edge between them.		 source code
bool
__eq__(self, other)
Compare two graphs for equality.		 source code
bool
__ne__(self, other)
Compare two graphs for inequality.		 source code
bool
issubgraph(self, other)
Report whether another graph contains this graph.		 source code
bool
issupergraph(self, other)
Report whether this graph contains another graph.		 source code
bool
__le__(self, other)
Report whether another graph contains this graph.		 source code
bool
__ge__(self, other)
Report whether this graph contains another graph.		 source code
bool
__lt__(self, other)
Report whether another graph strictly contains this graph.		 source code
 
__gt__(self, other)
Report whether this graph strictly contains another graph.		 source code
bool
adjacent(self, tail, head)
Report whether two vertices are adjacent (directly connected by an edge).		 source code
set
neighbors(self, vertex)
Return a set of vertices which are adjacent to the specified vertex.		 source code
bool
connected(self, tail, head)
Report whether two vertices are connected.		 source code
list
dijkstra(self, start)
Dijkstra's algorithm (shortest paths from start vertex to all other vertices).		 source code
list, float
shortest_path(self, start, end)
Find the shortest path from the start vertex to the end vertex using Dijkstra's algorithm.		 source code
dict of dict of double
floyd_warshall(self)
Floyd-Warshall algorithm (shortest path length between all pairs of vertices).		 source code
Graph
minimum_spanning_tree(self)
Minimum spanning tree (Kruskal's algorithm).		 source code
Graph
shortest_path_subgraph(self)
Shortest path subgraph, containing only strong edges (edges which form part of a shortest path between some pair of vertices).		 source code

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

Static Methods [hide private]
 
_binary_sanity_check(other)
Check that the other argument to a binary operation is also a graph, raising a TypeError otherwise.		 source code
Properties [hide private]
bool directed
Return whether this graph is directed.

Inherited from object: __class__

Method Details [hide private]

__init__(self, viter=None, eiter=None, directed=True)
(Constructor)

source code 

Construct a crisp graph from optional iterables.

Parameters:
  • viter (object) - The iterable for the vertex set (optional).
  • eiter (object) - The iterable for the edge set (optional).
  • directed (bool) - Defines the graph as directed or undirected.
Overrides: object.__init__

__repr__(self)
(Representation operator)

source code 

Return the canonical representation of a graph.

Returns: str
Canonical representation.
Overrides: object.__repr__

__str__(self)
(Informal representation operator)

source code 

Return the string representation of a graph.

Returns: str
String representation.
Overrides: object.__str__

add_vertex(self, vertex)

source code 

Add a vertex to the graph.

Parameters:
  • vertex (object) - The vertex to add.

remove_vertex(self, vertex)

source code 

Remove a vertex and all edges connected to it from the graph.

Parameters:
  • vertex (object) - The vertex to remove.

add_edge(self, edge)

source code 

Add an edge to the graph.

Parameters:

remove_edge(self, tail, head)

source code 

Remove an edge from the graph by tail and head.

Parameters:
  • tail (object) - The tail vertex of the edge.
  • head (object) - The head vertex of the edge.

edges(self, tail=None, head=None)

source code 

Return a set of edges with tail and/or head optionally specified.

Parameters:
  • tail (object) - The tail vertex constraint (optional).
  • head (object) - The head vertex constraint (optional).
Returns: set
The set of edges specified.

weight(self, tail, head)

source code 

Return the weight of an edge. Returns 1 for the base unweighted graph.

Parameters:
  • tail (object) - The tail vertex.
  • head (object) - The head vertex.
Returns: float
The weight of the edge from tail to head.

edges_by_weight(self, tail=None, head=None)

source code 

Return a list of edges, sorted in ascending order by weight, with tail and/or head optionally specified.

Parameters:
  • tail (object) - The tail vertex constraint (optional).
  • head (object) - The head vertex constraint (optional).
Returns: list
The list of edges sorted by weight.

connect(self, tail, head)

source code 

Connect a pair of vertices with a new edge. Convenience wrapper for add_edge().

Parameters:
  • tail (object) - The tail vertex.
  • head (object) - The head vertex.

disconnect(self, tail, head)

source code 

Disconnect a pair of vertices by removing the edge between them. Convenience wrapper for remove_edge().

Parameters:
  • tail (object) - The tail vertex.
  • head (object) - The head vertex.

__eq__(self, other)
(Equality operator)

source code 

Compare two graphs for equality. Does not recognize isomorphism (vertex identifiers must be the same).

Parameters:
  • other (Graph) - The other graph.
Returns: bool
True if equal, false otherwise.

__ne__(self, other)

source code 

Compare two graphs for inequality.

Parameters:
  • other (Graph) - The other graph.
Returns: bool
True if not equal, false otherwise.

issubgraph(self, other)

source code 

Report whether another graph contains this graph.

Parameters:
  • other (Graph) - The other graph.
Returns: bool
True if a subgraph, false otherwise.

issupergraph(self, other)

source code 

Report whether this graph contains another graph.

Parameters:
  • other (Graph) - The other graph.
Returns: bool
True if a supergraph, false otherwise.

__le__(self, other)
(Less-than-or-equals operator)

source code 

Report whether another graph contains this graph.

Parameters:
  • other (Graph) - The other graph.
Returns: bool
True if a subgraph, false otherwise.

__ge__(self, other)
(Greater-than-or-equals operator)

source code 

Report whether this graph contains another graph.

Parameters:
  • other (Graph) - The other graph.
Returns: bool
True if a supergraph, false otherwise.

__lt__(self, other)
(Less-than operator)

source code 

Report whether another graph strictly contains this graph.

Parameters:
  • other (Graph) - The other graph.
Returns: bool
True if a strict subgraph, false otherwise.

__gt__(self, other)
(Greater-than operator)

source code 

Report whether this graph strictly contains another graph.

Parameters:
  • other (Graph) - The other graph.
Returns:
True if a strict supergraph, false otherwise.

_binary_sanity_check(other)
Static Method

source code 

Check that the other argument to a binary operation is also a graph, raising a TypeError otherwise.

Parameters:
  • other (Graph) - The other argument.

adjacent(self, tail, head)

source code 

Report whether two vertices are adjacent (directly connected by an edge).

Parameters:
  • tail (object) - The tail vertex.
  • head (object) - The head vertex.
Returns: bool
True if adjacent, false otherwise.

neighbors(self, vertex)

source code 

Return a set of vertices which are adjacent to the specified vertex.

Parameters:
  • vertex (object) - The vertex.
Returns: set
The set of vertices adjacent to vertex.

connected(self, tail, head)

source code 

Report whether two vertices are connected. Uses a breadth-first search algorithm.

Parameters:
  • tail (object) - The tail vertex.
  • head (object) - The head vertex.
Returns: bool
True if adjacent, false otherwise.

dijkstra(self, start)

source code 

Dijkstra's algorithm (shortest paths from start vertex to all other vertices).

Parameters:
  • start (object) - The start vertex.
Returns: list
The 'previous" array of Dijkstra's algorithm.

shortest_path(self, start, end)

source code 

Find the shortest path from the start vertex to the end vertex using Dijkstra's algorithm.

Parameters:
  • start (object) - The start vertex.
  • end (object) - The end vertex.
Returns: list, float
Shortest path vertex list and total distance.

floyd_warshall(self)

source code 

Floyd-Warshall algorithm (shortest path length between all pairs of vertices).

Returns: dict of dict of double
A 2D dictionary of pairwise shortest path lengths.

minimum_spanning_tree(self)

source code 

Minimum spanning tree (Kruskal's algorithm).

Returns: Graph
The minimum spanning tree.

shortest_path_subgraph(self)

source code 

Shortest path subgraph, containing only strong edges (edges which form part of a shortest path between some pair of vertices).

Returns: Graph
The shortest path subgraph.

Property Details [hide private]

directed

Return whether this graph is directed. This should only be set by the constructor and is read-only afterward.

Get Method:
unreachable.directed(self) - Return whether this graph is directed.
Type:
bool

   Home       Trees       Indices       Help   
fuzzpy
Generated by Epydoc 3.0.1 on Fri Jan 21 14:08:04 2011 http://epydoc.sourceforge.net