geosolver.graph
index
/home/rick/Programming/Python/GeoSolver/geosolver/graph.py

Graph data structures and algorithms. 
After Guido van Rossums essay on graphs in python
(http://www.python.org/doc/essays/graphs.html).
and Julien Burdy's sourceforge python graph project.  
(http://sourceforge.net/projects/pygraphlib/)
 
A graph is typically represented as G=(V,E) where
V are vertices and E are edges. 
All vertices in a graph are uniquely, i.e. have unique id's. 
Edges are directed edges and are identified by an ordered 
pair of vertices (v1,v2). All edges are unique, i.e. are unique ordered pairs. 
Associated with each edge is a value.
 
A graph is implemented as a dictionary of which the keys are vertices.  
Associated with each vertex is (again) a dictionairy of which the keys are 
the vertices to which there is an edge. Associated with each edge is a value. 
(A graph is implemented as a dictionairy of dictionairies). 
 
The add_* and rem_* methods ensure that the graph contains no edges
to vertices that are not in main dictionary (anymore). 
 
The reverse of the graph is also sored and kept up to date, for fast
determination of incoming edges and other algorithms.
 
Also dictionaries are kept mapping vertices to fan-in and fanout numbers, and
mapping numbers to vertices with that fan-in/out number. This allows us to 
quickly find sources, sinks, etc.
 
Copyright Rick van der Meiden - 2003, 2004, 2005

 
Modules
       
random

 
Classes
       
geosolver.notify.Notifier
Graph
FanGraph

 
class FanGraph(Graph)
    A graph with updated fan-in and fan-out numbers
 
 
Method resolution order:
FanGraph
Graph
geosolver.notify.Notifier

Methods defined here:
__init__(self, graph=None)
add_edge(self, v1, v2, value=1)
Add edge from v1 to v2 with optional value.
add_vertex(self, v)
Add vertex to graph if not already.
fanin(self, v)
return fan-in number (number of in-going edges)
fanin_numbers(self)
the set of fan-in numbers, 
i.e. the union of the fan-in numbers of all veretices
fanout(self, v)
return fan-out number (number of out-going edges)
fanout_numbers(self)
the set of fan-out numbers, 
i.e. the union of the fan-out numbers of all veretices
infan(self, number)
return a list of vertices with given fan-in number
leafs(self)
return a list of vertices with zero fan-out
outfan(self, number)
return a list of vertices with given fan-out number
rem_edge(self, v1, v2)
Remove edge.
rem_vertex(self, v)
Remove vertex and incident edges.
roots(self)
return a list of vertices with zero fan-in
singular(self, number)
return a list of vertices with no fan-in and no fan-out
subgraph(self, vertices)
Derive subgraph containing specified vertices and enclosed edges.

Methods inherited from Graph:
__str__(self)
Create a string representation, using str() for each element
add_bi(self, v1, v2, value=1)
Add edges bi-directinally with optional value.
add_graph(self, graph)
Add all vertices and edges of given graph, and set edge values from given graph too.
adjacent_edges(self, vertex)
return list of outgoing and outgoing edges
adjacent_vertices(self, v)
list of adjacent (ingoing or outgoing) vertices
connected(self, v)
return vertices X connected to v by following edges ajdajecnt to v or X
(v is not in the result)
connected_ingoing(self, v)
return vertices X connected to v by following only ingoing edges to v or X (v is not in the result)
connected_outgoing(self, v)
return vertices X connected from v by following only outgoing edges from v or X 
(v is not in the result)
connected_subsets(self)
returns a set of (undirectionally) connected subsets of vertices
copy(self)
edges(self)
List edges
get(self, v1, v2)
Get value of edge (v1,v2).
has_bi(self, v1, v2)
True if both edges (v1,v2) and (v2,v1) are in this graph.
has_edge(self, v1, v2)
True if there is a directed edge (v1,v2) in this graph.
has_one(self, v1, v2)
True if either edge (v1,v2) or (v2,v1) is in this graph.
has_vertex(self, v)
True if v a vertex of this graph.
ingoing_edges(self, vertex)
return list of incoming edges
ingoing_vertices(self, vertex)
return list of vertices from which edge goes to given vertex
mincut(self)
Returns a minimum cut of the graph. 
Implements the Stoer/Wagner algorithm. The graph is interpreted 
as a undirected graph, by adding the weights of co-edges. 
Returns (value, edges, g1, g2) 
where value is the weight of the cut, 
edges is the set of cut edges, 
g1 and g2 are disjoint sets of vertices.
outgoing_edges(self, vertex)
return list of outgoing edges
outgoing_vertices(self, vertex)
return list of vertices to which edge goes from given vertex
path(self, start, end)
return an arbitrary path (list of vertices) from start to end. 
If start equal to end, then return a cycle. 
If no path, then return empty list.
rem_bi(self, v1, v2)
Remove edges bi-directionally.
reverse(self)
return a reverse graph
set(self, v1, v2, value)
Set value of edge (v1,v2) and add edge if it doesn't exist
set_bi(self, v1, v2, value)
Set value of edges (v1,v2) and (v2,v1).
vertices(self)
List vertices

Methods inherited from geosolver.notify.Notifier:
add_listener(self, listener)
add a listener to the list (and self to listers' list)
rem_listener(self, listener)
remove a listener from the list (and self from listers' list)
send_notify(self, message)
send a message to all listeners

 
class Graph(geosolver.notify.Notifier)
    A weighted directed graph
 
  Methods defined here:
__init__(self, graph=None)
__str__(self)
Create a string representation, using str() for each element
add_bi(self, v1, v2, value=1)
Add edges bi-directinally with optional value.
add_edge(self, v1, v2, value=1)
Add edge from v1 to v2 with optional value.
add_graph(self, graph)
Add all vertices and edges of given graph, and set edge values from given graph too.
add_vertex(self, v)
Add vertex to graph if not already.
adjacent_edges(self, vertex)
return list of outgoing and outgoing edges
adjacent_vertices(self, v)
list of adjacent (ingoing or outgoing) vertices
connected(self, v)
return vertices X connected to v by following edges ajdajecnt to v or X
(v is not in the result)
connected_ingoing(self, v)
return vertices X connected to v by following only ingoing edges to v or X (v is not in the result)
connected_outgoing(self, v)
return vertices X connected from v by following only outgoing edges from v or X 
(v is not in the result)
connected_subsets(self)
returns a set of (undirectionally) connected subsets of vertices
copy(self)
edges(self)
List edges
get(self, v1, v2)
Get value of edge (v1,v2).
has_bi(self, v1, v2)
True if both edges (v1,v2) and (v2,v1) are in this graph.
has_edge(self, v1, v2)
True if there is a directed edge (v1,v2) in this graph.
has_one(self, v1, v2)
True if either edge (v1,v2) or (v2,v1) is in this graph.
has_vertex(self, v)
True if v a vertex of this graph.
ingoing_edges(self, vertex)
return list of incoming edges
ingoing_vertices(self, vertex)
return list of vertices from which edge goes to given vertex
mincut(self)
Returns a minimum cut of the graph. 
Implements the Stoer/Wagner algorithm. The graph is interpreted 
as a undirected graph, by adding the weights of co-edges. 
Returns (value, edges, g1, g2) 
where value is the weight of the cut, 
edges is the set of cut edges, 
g1 and g2 are disjoint sets of vertices.
outgoing_edges(self, vertex)
return list of outgoing edges
outgoing_vertices(self, vertex)
return list of vertices to which edge goes from given vertex
path(self, start, end)
return an arbitrary path (list of vertices) from start to end. 
If start equal to end, then return a cycle. 
If no path, then return empty list.
rem_bi(self, v1, v2)
Remove edges bi-directionally.
rem_edge(self, v1, v2)
Remove edge.
rem_vertex(self, v)
Remove vertex and incident edges.
reverse(self)
return a reverse graph
set(self, v1, v2, value)
Set value of edge (v1,v2) and add edge if it doesn't exist
set_bi(self, v1, v2, value)
Set value of edges (v1,v2) and (v2,v1).
subgraph(self, vertices)
Derive subgraph containing specified vertices and enclosed edges.
vertices(self)
List vertices

Methods inherited from geosolver.notify.Notifier:
add_listener(self, listener)
add a listener to the list (and self to listers' list)
rem_listener(self, listener)
remove a listener from the list (and self from listers' list)
send_notify(self, message)
send a message to all listeners

 
Functions
       
complete_graph(nvertices, monocycles=False, basename='v')
random_graph(vertices, edges, bidirectional=False, basename='v')
generate a random graph with given number of
vertices and edges