--- a/scripts/graph/__init__.py Sun Nov 30 16:39:18 2008 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,1573 +0,0 @@
-# Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com>
-# Christian Muise <christian.muise@gmail.com>
-# Nathan Davis <davisn90210@gmail.com>
-# Zsolt Haraszti <zsolt@drawwell.net>
-#
-# Permission is hereby granted, free of charge, to any person
-# obtaining a copy of this software and associated documentation
-# files (the "Software"), to deal in the Software without
-# restriction, including without limitation the rights to use,
-# copy, modify, merge, publish, distribute, sublicense, and/or sell
-# copies of the Software, and to permit persons to whom the
-# Software is furnished to do so, subject to the following
-# conditions:
-
-# The above copyright notice and this permission notice shall be
-# included in all copies or substantial portions of the Software.
-
-# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
-# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
-# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
-# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
-# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
-# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
-# OTHER DEALINGS IN THE SOFTWARE.
-
-
-"""
-python-graph
-
-A library for working with graphs in Python.
-
-@version: 1.3.1
-"""
-
-
-# Imports
-import accessibility
-import generators
-import minmax
-import searching
-import sorting
-import readwrite
-import traversal
-
-
-# Graph class --------------------------------------------------------------------------------------
-
-class graph (object):
- """
- Graph class.
-
- Graphs are built of nodes and edges.
-
- @sort: __init__, __getitem__, __iter__, __len__, __str__, add_edge, add_edge_attribute,
- add_graph, add_node, add_node_attribute, add_nodes, add_spanning_tree, complete, del_edge,
- del_node, edges, get_edge_attributes, get_edge_label, get_edge_weight, get_node_attributes,
- has_edge, has_node, inverse, neighbors, nodes, order, set_edge_label, set_edge_weight,
- traversal, generate, read, write, accessibility, breadth_first_search, connected_components,
- cut_edges, cut_nodes, depth_first_search, minimal_spanning_tree, shortest_path
- """
-
-
- def __init__(self):
- """
- Initialize a graph.
- """
- self.node_neighbors = {} # Pairing: Node -> Neighbors
- self.edge_properties = {} # Pairing: Edge -> (Label, Weight)
- self.node_attr = {} # Pairing: Node -> Attributes
- self.edge_attr = {} # Pairing: Edge -> Attributes
-
-
- def __str__(self):
- """
- Return a string representing the graph when requested by str() (or print).
-
- @rtype: string
- @return: String representing the graph.
- """
- return "<graph object " + str(self.nodes()) + " " + str(self.edges()) + ">"
-
-
- def __len__(self):
- """
- Return the order of the graph when requested by len().
-
- @rtype: number
- @return: Size of the graph.
- """
- return len(self.node_neighbors)
-
-
- def __iter__(self):
- """
- Return a iterator passing through all nodes in the graph.
-
- @rtype: iterator
- @return: Iterator passing through all nodes in the graph.
- """
- for each in self.node_neighbors.iterkeys():
- yield each
-
-
- def __getitem__(self, node):
- """
- Return a iterator passing through all neighbors of the given node.
-
- @rtype: iterator
- @return: Iterator passing through all neighbors of the given node.
- """
- for each in self.node_neighbors[node]:
- yield each
-
-
- def read(self, string, fmt='xml'):
- """
- Read a graph from a string. Nodes and edges specified in the input will be added to the
- current graph.
-
- @type string: string
- @param string: Input string specifying a graph.
-
- @type fmt: string
- @param fmt: Input format. Possible formats are:
- 1. 'xml' - XML (default)
- """
- if (fmt == 'xml'):
- readwrite.read_xml(self, string)
-
-
- def write(self, fmt='xml'):
- """
- Write the graph to a string. Depending of the output format, this string can be used by
- read() to rebuild the graph.
-
- @type fmt: string
- @param fmt: Output format. Possible formats are:
- 1. 'xml' - XML (default)
- 2. 'dot' - DOT Language (for GraphViz)
- 3. 'dotwt' - DOT Language with weight information
-
- @rtype: string
- @return: String specifying the graph.
- """
- if (fmt == 'xml'):
- return readwrite.write_xml(self)
- elif (fmt == 'dot'):
- return readwrite.write_dot_graph(self, False)
- elif (fmt == 'dotwt'):
- return readwrite.write_dot_graph(self, True)
-
-
- def generate(self, num_nodes, num_edges, weight_range=(1, 1)):
- """
- Add nodes and random edges to the graph.
-
- @type num_nodes: number
- @param num_nodes: Number of nodes.
-
- @type num_edges: number
- @param num_edges: Number of edges.
-
- @type weight_range: tuple
- @param weight_range: tuple of two integers as lower and upper limits on randomly generated
- weights (uniform distribution).
- """
- generators.generate(self, num_nodes, num_edges, weight_range)
-
-
- def nodes(self):
- """
- Return node list.
-
- @rtype: list
- @return: Node list.
- """
- return self.node_neighbors.keys()
-
-
- def neighbors(self, node):
- """
- Return all nodes that are directly accessible from given node.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: list
- @return: List of nodes directly accessible from given node.
- """
- return self.node_neighbors[node]
-
-
- def edges(self):
- """
- Return all edges in the graph.
-
- @rtype: list
- @return: List of all edges in the graph.
- """
- return self.edge_properties.keys()
-
-
- def has_node(self, node):
- """
- Return whether the requested node exists.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: boolean
- @return: Truth-value for node existence.
- """
- return self.node_neighbors.has_key(node)
-
-
- def add_node(self, node, attrs=[]):
- """
- Add given node to the graph.
-
- @attention: While nodes can be of any type, it's strongly recommended to use only numbers
- and single-line strings as node identifiers if you intend to use write().
-
- @type node: node
- @param node: Node identifier.
-
- @type attrs: list
- @param attrs: List of node attributes specified as (attribute, value) tuples.
- """
- if (not node in self.node_neighbors):
- self.node_neighbors[node] = []
- self.node_attr[node] = attrs
-
-
- def add_nodes(self, nodelist):
- """
- Add given nodes to the graph.
-
- @attention: While nodes can be of any type, it's strongly recommended to use only numbers
- and single-line strings as node identifiers if you intend to use write().
-
- @type nodelist: list
- @param nodelist: List of nodes to be added to the graph.
- """
- for each in nodelist:
- self.add_node(each)
-
-
- def add_edge(self, u, v, wt=1, label='', attrs=[]):
- """
- Add an edge (u,v) to the graph connecting nodes u and v.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type wt: number
- @param wt: Edge weight.
-
- @type label: string
- @param label: Edge label.
-
- @type attrs: list
- @param attrs: List of node attributes specified as (attribute, value) tuples.
- """
- if (v not in self.node_neighbors[u] and u not in self.node_neighbors[v]):
- self.node_neighbors[u].append(v)
- self.node_neighbors[v].append(u)
- self.edge_properties[(u, v)] = [label, wt]
- self.edge_properties[(v, u)] = [label, wt]
- self.edge_attr[(u, v)] = attrs
- self.edge_attr[(v, u)] = attrs
-
-
- def del_node(self, node):
- """
- Remove a node from the graph.
-
- @type node: node
- @param node: Node identifier.
- """
- for each in list(self.neighbors(node)):
- self.del_edge(each, node)
- del(self.node_neighbors[node])
- del(self.node_attr[node])
-
-
- def del_edge(self, u, v):
- """
- Remove an edge (u, v) from the graph.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
- """
- self.node_neighbors[u].remove(v)
- self.node_neighbors[v].remove(u)
- del(self.edge_properties[(u,v)])
- del(self.edge_properties[(v,u)])
- del(self.edge_attr[(u,v)])
- del(self.edge_attr[(v,u)])
-
-
- def get_edge_weight(self, u, v):
- """
- Get the weight of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: number
- @return: Edge weight.
- """
- return self.edge_properties[(u, v)][1]
-
-
- def set_edge_weight(self, u, v, wt):
- """
- Set the weight of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type wt: number
- @param wt: Edge weight.
- """
- self.edge_properties[(u, v)][1] = wt
- self.edge_properties[(v, u)][1] = wt
-
-
- def get_edge_label(self, u, v):
- """
- Get the label of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: string
- @return: Edge label
- """
- return self.edge_properties[(u, v)][0]
-
-
- def set_edge_label(self, u, v, label):
- """
- Set the label of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type label: string
- @param label: Edge label.
- """
- self.edge_properties[(u, v)][0] = label
- self.edge_properties[(v, u)][0] = label
-
-
- def add_node_attribute(self, node, attr):
- """
- Add attribute to the given node.
-
- @type node: node
- @param node: Node identifier
-
- @type attr: tuple
- @param attr: Node attribute specified as a tuple in the form (attribute, value).
- """
- self.node_attr[node] = self.node_attr[node] + [attr]
-
-
- def get_node_attributes(self, node):
- """
- Return the attributes of the given node.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: list
- @return: List of attributes specified tuples in the form (attribute, value).
- """
- return self.node_attr[node]
-
-
- def add_edge_attribute(self, u, v, attr):
- """
- Add attribute to the given edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type attr: tuple
- @param attr: Node attribute specified as a tuple in the form (attribute, value).
- """
- self.edge_attr[(u,v)] = self.edge_attr[(u,v)] + [attr]
- self.edge_attr[(v,u)] = self.edge_attr[(v,u)] + [attr]
-
-
- def get_edge_attributes(self, u, v):
- """
- Return the attributes of the given edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: list
- @return: List of attributes specified tuples in the form (attribute, value).
- """
- return self.edge_attr[(u,v)]
-
-
- def has_edge(self, u, v):
- """
- Return whether an edge between nodes u and v exists.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: boolean
- @return: Truth-value for edge existence.
- """
- return self.edge_properties.has_key((u,v)) and self.edge_properties.has_key((v,u))
-
-
- def order(self, node):
- """
- Return the order of the given node.
-
- @rtype: number
- @return: Order of the given node.
- """
- return len(self.neighbors(node))
-
-
- def complete(self):
- """
- Make the graph a complete graph.
-
- @attention: This will modify the current graph.
- """
- for each in self.nodes():
- for other in self.nodes():
- if (each != other):
- self.add_edge(each, other)
-
-
- def inverse(self):
- """
- Return the inverse of the graph.
-
- @rtype: graph
- @return: Complement graph for the graph.
- """
- inv = graph()
- inv.add_nodes(self.nodes())
- inv.complete()
- for each in self.edges():
- if (inv.has_edge(each[0], each[1])):
- inv.del_edge(each[0], each[1])
- return inv
-
-
- def add_graph(self, graph):
- """
- Add other graph to the graph.
-
- @attention: Attributes and labels are not preserved.
-
- @type graph: graph
- @param graph: Graph
- """
- self.add_nodes(graph.nodes())
- for each_node in graph.nodes():
- for each_edge in graph.neighbors(each_node):
- self.add_edge(each_node, each_edge)
-
-
- def add_spanning_tree(self, st):
- """
- Add a spanning tree to the graph.
-
- @type st: dictionary
- @param st: Spanning tree.
- """
- self.add_nodes(st.keys())
- for each in st:
- if (st[each] is not None):
- self.add_edge(st[each], each)
-
-
- def traversal(self, node, order='pre'):
- """
- Graph traversal iterator.
-
- @type node: node
- @param node: Node.
-
- @type order: string
- @param order: traversal ordering. Possible values are:
- 2. 'pre' - Preordering (default)
- 1. 'post' - Postordering
-
- @rtype: iterator
- @return: Traversal iterator.
- """
- for each in traversal.traversal(self, node, order):
- yield each
-
-
- def depth_first_search(self, root=None):
- """
- Depht-first search.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @rtype: tuple
- @return: tupple containing a dictionary and two lists:
- 1. Generated spanning tree
- 2. Graph's preordering
- 3. Graph's postordering
- """
- return searching.depth_first_search(self, root)
-
-
- def breadth_first_search(self, root=None):
- """
- Breadth-first search.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @rtype: dictionary
- @return: A tuple containing a dictionary and a list.
- 1. Generated spanning tree
- 2. Graph's level-based ordering
- """
- return searching.breadth_first_search(self, root)
-
-
- def accessibility(self):
- """
- Accessibility matrix (transitive closure).
-
- @rtype: dictionary
- @return: Accessibility information for each node.
- """
- return accessibility.accessibility(self)
-
-
- def connected_components(self):
- """
- Connected components.
-
- @attention: Indentification of connected components is meaningful only for non-directed
- graphs.
-
- @rtype: dictionary
- @return: Pairing that associates each node to its connected component.
- """
- return accessibility.connected_components(self)
-
-
- def minimal_spanning_tree(self, root=None):
- """
- Minimal spanning tree.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @attention: Minimal spanning tree meaningful only for weighted graphs.
-
- @rtype: list
- @return: Generated spanning tree.
- """
- return minmax.minimal_spanning_tree(self, root)
-
-
- def shortest_path(self, source):
- """
- Return the shortest path distance between source node and all other nodes using Dijkstra's
- algorithm.
-
- @attention: All weights must be nonnegative.
-
- @type source: node
- @param source: Node from which to start the search.
-
- @rtype: tuple
- @return: A tuple containing two dictionaries, each keyed by target nodes.
- 1. Shortest path spanning tree
- 2. Shortest distance from given source to each target node
- Inaccessible target nodes do not appear in either dictionary.
- """
- return minmax.shortest_path(self, source)
-
-
- def cut_edges(self):
- """
- Return the cut-edges of the given graph.
-
- @rtype: list
- @return: List of cut-edges.
- """
- return accessibility.cut_edges(self)
-
-
- def cut_nodes(self):
- """
- Return the cut-nodes of the given graph.
-
- @rtype: list
- @return: List of cut-nodes.
- """
- return accessibility.cut_nodes(self)
-
-
-# Digraph class ------------------------------------------------------------------------------------
-
-class digraph (object):
- """
- Digraph class.
-
- Digraphs are built of nodes and directed edges.
-
- @sort: __init__, __getitem__, __iter__, __len__, __str__, add_edge, add_edge_attribute,
- add_graph, add_node, add_node_attribute, add_nodes, add_spanning_tree, complete, degree,
- del_edge, del_node, edges, get_edge_attributes, get_edge_label, get_edge_weight,
- get_node_attributes, has_edge, has_node, incidents, inverse, neighbors, nodes, order,
- set_edge_label, set_edge_weight, traversal, generate, read, write, accessibility,
- breadth_first_search, cut_edges, cut_nodes, depth_first_search, minimal_spanning_tree,
- mutual_accessibility, shortest_path, topological_sorting
- """
-
-
- def __init__(self):
- """
- Initialize a digraph.
- """
- self.node_neighbors = {} # Pairing: Node -> Neighbors
- self.edge_properties = {} # Pairing: Edge -> (Label, Weight)
- self.node_incidence = {} # Pairing: Node -> Incident nodes
- self.node_attr = {} # Pairing: Node -> Attributes
- self.edge_attr = {} # Pairing: Edge -> Attributes
-
-
- def __str__(self):
- """
- Return a string representing the digraph when requested by str() (or print).
-
- @rtype: string
- @return: String representing the graph.
- """
- return "<graph object " + str(self.nodes()) + " " + str(self.edges()) + ">"
-
-
- def __len__(self):
- """
- Return the order of the digraph when requested by len().
-
- @rtype: number
- @return: Size of the graph.
- """
- return len(self.node_neighbors)
-
-
- def __iter__(self):
- """
- Return a iterator passing through all nodes in the digraph.
-
- @rtype: iterator
- @return: Iterator passing through all nodes in the digraph.
- """
- for each in self.node_neighbors.iterkeys():
- yield each
-
-
- def __getitem__(self, node):
- """
- Return a iterator passing through all neighbors of the given node.
-
- @rtype: iterator
- @return: Iterator passing through all neighbors of the given node.
- """
- for each in self.node_neighbors[node]:
- yield each
-
-
- def read(self, string, fmt='xml'):
- """
- Read a graph from a string. Nodes and edges specified in the input will be added to the
- current graph.
-
- @type string: string
- @param string: Input string specifying a graph.
-
- @type fmt: string
- @param fmt: Input format. Possible formats are:
- 1. 'xml' - XML (default)
- """
- if (fmt == 'xml'):
- readwrite.read_xml(self, string)
-
-
- def write(self, fmt='xml'):
- """
- Write the graph to a string. Depending of the output format, this string can be used by
- read() to rebuild the graph.
-
- @type fmt: string
- @param fmt: Output format. Possible formats are:
- 1. 'xml' - XML (default)
- 2. 'dot' - DOT Language (for GraphViz)
- 3. 'dotwt' - DOT Language with weight information
-
- @rtype: string
- @return: String specifying the graph.
- """
- if (fmt == 'xml'):
- return readwrite.write_xml(self)
- elif (fmt == 'dot'):
- return readwrite.write_dot_digraph(self, False)
- elif (fmt == 'dotwt'):
- return readwrite.write_dot_digraph(self, True)
-
-
- def generate(self, num_nodes, num_edges, weight_range=(1, 1)):
- """
- Add nodes and random edges to the graph.
-
- @type num_nodes: number
- @param num_nodes: Number of nodes.
-
- @type num_edges: number
- @param num_edges: Number of edges.
-
- @type weight_range: tuple
- @param weight_range: tuple of two integers as lower and upper limits on randomly generated
- weights (uniform distribution).
- """
- generators.generate(self, num_nodes, num_edges, weight_range)
-
-
- def nodes(self):
- """
- Return node list.
-
- @rtype: list
- @return: Node list.
- """
- return self.node_neighbors.keys()
-
-
- def neighbors(self, node):
- """
- Return all nodes that are directly accessible from given node.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: list
- @return: List of nodes directly accessible from given node.
- """
- return self.node_neighbors[node]
-
-
- def incidents(self, node):
- """
- Return all nodes that are incident to the given node.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: list
- @return: List of nodes directly accessible from given node.
- """
- return self.node_incidence[node]
-
-
-
- def edges(self):
- """
- Return all edges in the graph.
-
- @rtype: list
- @return: List of all edges in the graph.
- """
- return self.edge_properties.keys()
-
-
- def has_node(self, node):
- """
- Return whether the requested node exists.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: boolean
- @return: Truth-value for node existence.
- """
- return self.node_neighbors.has_key(node)
-
-
- def add_node(self, node, attrs=[]):
- """
- Add given node to the graph.
-
- @attention: While nodes can be of any type, it's strongly recommended to use only numbers
- and single-line strings as node identifiers if you intend to use write().
-
- @type node: node
- @param node: Node identifier.
-
- @type attrs: list
- @param attrs: List of node attributes specified as (attribute, value) tuples.
- """
- if (node not in self.node_neighbors):
- self.node_neighbors[node] = []
- self.node_incidence[node] = []
- self.node_attr[node] = attrs
-
-
- def add_nodes(self, nodelist):
- """
- Add given nodes to the graph.
-
- @attention: While nodes can be of any type, it's strongly recommended to use only numbers
- and single-line strings as node identifiers if you intend to use write().
-
- @type nodelist: list
- @param nodelist: List of nodes to be added to the graph.
- """
- for each in nodelist:
- self.add_node(each)
-
-
- def add_edge(self, u, v, wt=1, label='', attrs=[]):
- """
- Add an directed edge (u,v) to the graph connecting nodes u to v.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type wt: number
- @param wt: Edge weight.
-
- @type label: string
- @param label: Edge label.
-
- @type attrs: list
- @param attrs: List of node attributes specified as (attribute, value) tuples.
- """
- if (v not in self.node_neighbors[u]):
- self.node_neighbors[u].append(v)
- self.node_incidence[v].append(u)
- self.edge_properties[(u, v)] = [label, wt]
- self.edge_attr[(u, v)] = attrs
-
-
- def del_node(self, node):
- """
- Remove a node from the graph.
-
- @type node: node
- @param node: Node identifier.
- """
- for each in list(self.incidents(node)):
- self.del_edge(each, node)
- for each in list(self.neighbors(node)):
- self.del_edge(node, each)
- del(self.node_neighbors[node])
- del(self.node_incidence[node])
- del(self.node_attr[node])
-
-
- def del_edge(self, u, v):
- """
- Remove an directed edge (u, v) from the graph.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
- """
- self.node_neighbors[u].remove(v)
- self.node_incidence[v].remove(u)
- del(self.edge_properties[(u,v)])
- del(self.edge_attr[(u,v)])
-
-
- def get_edge_weight(self, u, v):
- """
- Get the weight of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: number
- @return: Edge weight.
- """
- return self.edge_properties[(u, v)][1]
-
-
- def set_edge_weight(self, u, v, wt):
- """
- Set the weight of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type wt: number
- @param wt: Edge weight.
- """
- self.edge_properties[(u, v)][1] = wt
-
-
- def get_edge_label(self, u, v):
- """
- Get the label of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: string
- @return: Edge label
- """
- return self.edge_properties[(u, v)][0]
-
-
- def set_edge_label(self, u, v, label):
- """
- Set the label of an edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type label: string
- @param label: Edge label.
- """
- self.edge_properties[(u, v)][0] = label
-
-
- def add_node_attribute(self, node, attr):
- """
- Add attribute to the given node.
-
- @type node: node
- @param node: Node identifier
-
- @type attr: tuple
- @param attr: Node attribute specified as a tuple in the form (attribute, value).
- """
- self.node_attr[node] = self.node_attr[node] + [attr]
-
-
- def get_node_attributes(self, node):
- """
- Return the attributes of the given node.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: list
- @return: List of attributes specified tuples in the form (attribute, value).
- """
- return self.node_attr[node]
-
-
- def add_edge_attribute(self, u, v, attr):
- """
- Add attribute to the given edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @type attr: tuple
- @param attr: Node attribute specified as a tuple in the form (attribute, value).
- """
- self.edge_attr[(u,v)] = self.edge_attr[(u,v)] + [attr]
-
-
- def get_edge_attributes(self, u, v):
- """
- Return the attributes of the given edge.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: list
- @return: List of attributes specified tuples in the form (attribute, value).
- """
- return self.edge_attr[(u,v)]
-
-
- def has_edge(self, u, v):
- """
- Return whether an edge between nodes u and v exists.
-
- @type u: node
- @param u: One node.
-
- @type v: node
- @param v: Other node.
-
- @rtype: boolean
- @return: Truth-value for edge existence.
- """
- return self.edge_properties.has_key((u,v))
-
-
- def order(self, node):
- """
- Return the order of the given node.
-
- @rtype: number
- @return: Order of the given node.
- """
- return len(self.neighbors(node))
-
-
- def degree(self, node):
- """
- Return the degree of the given node.
-
- @rtype: number
- @return: Order of the given node.
- """
- return len(self.node_incidence[node])
-
-
- def complete(self):
- """
- Make the graph a complete graph.
-
- @attention: This will modify the current graph.
- """
- for each in self.nodes():
- for other in self.nodes():
- if (each != other):
- self.add_edge(each, other)
-
-
- def inverse(self):
- """
- Return the inverse of the graph.
-
- @rtype: graph
- @return: Complement graph for the graph.
- """
- inv = digraph()
- inv.add_nodes(self.nodes())
- inv.complete()
- for each in self.edges():
- inv.del_edge(each[0], each[1])
- return inv
-
-
- def add_graph(self, graph):
- """
- Add other graph to the graph.
-
- @attention: Attributes and labels are not preserved.
-
- @type graph: graph
- @param graph: Graph
- """
- self.add_nodes(graph.nodes())
- for each_node in graph.nodes():
- for each_edge in graph.neighbors(each_node):
- self.add_edge(each_node, each_edge)
-
-
- def add_spanning_tree(self, st):
- """
- Add a spanning tree to the graph.
-
- @type st: dictionary
- @param st: Spanning tree.
- """
- self.add_nodes(st.keys())
- for each in st:
- if (st[each] is not None):
- self.add_edge(st[each], each)
-
-
- def traversal(self, node, order='pre'):
- """
- Graph traversal iterator.
-
- @type node: node
- @param node: Node.
-
- @type order: string
- @param order: traversal ordering. Possible values are:
- 2. 'pre' - Preordering (default)
- 1. 'post' - Postordering
-
- @rtype: iterator
- @return: Traversal iterator.
- """
- for each in traversal.traversal(self, node, order):
- yield each
-
-
- def depth_first_search(self, root=None):
- """
- Depht-first search.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @rtype: tuple
- @return: tupple containing a dictionary and two lists:
- 1. Generated spanning tree
- 2. Graph's preordering
- 3. Graph's postordering
- """
- return searching.depth_first_search(self, root)
-
-
- def accessibility(self):
- """
- Accessibility matrix (transitive closure).
-
- @rtype: dictionary
- @return: Accessibility information for each node.
- """
- return accessibility.accessibility(self)
-
-
- def breadth_first_search(self, root=None):
- """
- Breadth-first search.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @rtype: dictionary
- @return: A tuple containing a dictionary and a list.
- 1. Generated spanning tree
- 2. Graph's level-based ordering
- """
- return searching.breadth_first_search(self, root)
-
-
- def mutual_accessibility(self):
- """
- Mutual-accessibility matrix (strongly connected components).
-
- @rtype: list
- @return: Mutual-accessibility information for each node.
- """
- return accessibility.mutual_accessibility(self)
-
-
- def topological_sorting(self):
- """
- Topological sorting.
-
- @attention: Topological sorting is meaningful only for directed acyclic graphs.
-
- @rtype: list
- @return: Topological sorting for the graph.
- """
- return sorting.topological_sorting(self)
-
-
- def minimal_spanning_tree(self, root=None):
- """
- Minimal spanning tree.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @attention: Minimal spanning tree meaningful only for weighted graphs.
-
- @rtype: list
- @return: Generated spanning tree.
- """
- return minmax.minimal_spanning_tree(self, root)
-
-
- def shortest_path(self, source):
- """
- Return the shortest path distance between source node and all other nodes using Dijkstra's
- algorithm.
-
- @attention: All weights must be nonnegative.
-
- @type source: node
- @param source: Node from which to start the search.
-
- @rtype: tuple
- @return: A tuple containing two dictionaries, each keyed by target nodes.
- 1. Shortest path spanning tree
- 2. Shortest distance from given source to each target node
- Inaccessible target nodes do not appear in either dictionary.
- """
- return minmax.shortest_path(self, source)
-
-
- def cut_edges(self):
- """
- Return the cut-edges of the given graph.
-
- @rtype: list
- @return: List of cut-edges.
- """
- return accessibility.cut_edges(self)
-
-
- def cut_nodes(self):
- """
- Return the cut-nodes of the given graph.
-
- @rtype: list
- @return: List of cut-nodes.
- """
- return accessibility.cut_nodes(self)
-
-
-# Hypergraph class ---------------------------------------------------------------------------------
-
-class hypergraph (object):
- """
- Hypergraph class.
-
- Hypergraphs are a generalization of graphs where an edge (called hyperedge) can connect more
- than two nodes.
-
- @sort: __init__, __len__, __str__, add_hyperedge, add_hyperedges, add_node, add_nodes, has_node,
- hyperedges, link, links, nodes, unlink, read, write, accessibility, connected_components,
- cut_hyperedges, cut_nodes
- """
-
-
- def __init__(self):
- """
- Initialize a hypergraph.
- """
- self.node_links = {} # Pairing: Node -> Hyperedge
- self.edge_links = {} # Pairing: Hyperedge -> Node
- self.graph = graph() # Ordinary graph
-
-
- def __str__(self):
- """
- Return a string representing the hypergraph when requested by str() (or print).
-
- @rtype: string
- @return: String representing the hypergraph.
- """
- return "<hypergraph object " + str(self.nodes()) + " " + str(self.edge_links) + ">"
-
-
- def __len__(self):
- """
- Return the size of the hypergraph when requested by len().
-
- @rtype: number
- @return: Size of the hypergraph.
- """
- return len(self.node_links)
-
-
- def read(self, string, fmt='xml'):
- """
- Read a hypergraph from a string. Nodes and hyperedges specified in the input will be added
- to the current graph.
-
- @type string: string
- @param string: Input string specifying a graph.
-
- @type fmt: string
- @param fmt: Input format. Possible formats are:
- 1. 'xml' - XML (default)
- """
- if (fmt == 'xml'):
- readwrite.read_xml_hypergraph(self, string)
-
-
- def write(self, fmt='xml'):
- """
- Write the hypergraph to a string. Depending of the output format, this string can be used by
- read() to rebuild the graph.
-
- @type fmt: string
- @param fmt: Output format. Possible formats are:
- 1. 'xml' - XML (default)
- 2. 'dot' - DOT Language (for GraphViz)
- 3. 'dotclr' - DOT Language, coloured
-
- @rtype: string
- @return: String specifying the graph.
- """
- if (fmt == 'xml'):
- return readwrite.write_xml_hypergraph(self)
- elif (fmt == 'dot'):
- return readwrite.write_dot_hypergraph(self)
- elif (fmt == 'dotclr'):
- return readwrite.write_dot_hypergraph(self, coloured=True)
-
-
- def nodes(self):
- """
- Return node list.
-
- @rtype: list
- @return: Node list.
- """
- return self.node_links.keys()
-
-
- def hyperedges(self):
- """
- Return hyperedge list.
-
- @rtype: list
- @return: List of hyperedges linked to the given node.
- """
- return self.edge_links.keys()
-
-
- def links(self, obj):
- """
- Return all objects linked to the given one.
-
- If given a node, linked hyperedges will be returned. If given a hyperedge, linked nodes will
- be returned.
-
- @type obj: node or hyperedge
- @param obj: Object identifier.
-
- @rtype: list
- @return: List of objects linked to the given one.
- """
- if (obj in self.node_links):
- return self.node_links[obj]
- else:
- return self.edge_links[obj]
-
-
- def has_node(self, node):
- """
- Return whether the requested node exists.
-
- @type node: node
- @param node: Node identifier
-
- @rtype: boolean
- @return: Truth-value for node existence.
- """
- return self.node_links.has_key(node)
-
-
- def add_node(self, node):
- """
- Add given node to the hypergraph.
-
- @attention: While nodes can be of any type, it's strongly recommended to use only numbers
- and single-line strings as node identifiers if you intend to use write().
-
- @type node: node
- @param node: Node identifier.
- """
- if (not node in self.node_links):
- self.node_links[node] = []
- self.graph.add_node((node,'n'))
-
-
- def add_nodes(self, nodelist):
- """
- Add given nodes to the hypergraph.
-
- @attention: While nodes can be of any type, it's strongly recommended to use only numbers
- and single-line strings as node identifiers if you intend to use write().
-
- @type nodelist: list
- @param nodelist: List of nodes to be added to the graph.
- """
- for each in nodelist:
- self.add_node(each)
-
-
- def add_hyperedge(self, hyperedge):
- """
- Add given hyperedge to the hypergraph.
-
- @attention: While hyperedge-nodes can be of any type, it's strongly recommended to use only
- numbers and single-line strings as node identifiers if you intend to use write().
-
- @type hyperedge: hyperedge
- @param hyperedge: Hyperedge identifier.
- """
- if (not hyperedge in self.edge_links):
- self.edge_links[hyperedge] = []
- self.graph.add_node((hyperedge,'h'))
-
-
- def add_hyperedges(self, edgelist):
- """
- Add given hyperedges to the hypergraph.
-
- @attention: While hyperedge-nodes can be of any type, it's strongly recommended to use only
- numbers and single-line strings as node identifiers if you intend to use write().
-
- @type edgelist: list
- @param edgelist: List of hyperedge-nodes to be added to the graph.
- """
- for each in edgelist:
- self.add_hyperedge(each)
-
-
- def link(self, node, hyperedge):
- """
- Link given node and hyperedge.
-
- @type node: node
- @param node: Node.
-
- @type hyperedge: node
- @param hyperedge: Hyperedge.
- """
- if (hyperedge not in self.node_links[node]):
- self.node_links[node].append(hyperedge)
- self.edge_links[hyperedge].append(node)
- self.graph.add_edge((node,'n'), (hyperedge,'h'))
-
-
- def unlink(self, node, hyperedge):
- """
- Unlink given node and hyperedge.
-
- @type node: node
- @param node: Node.
-
- @type hyperedge: hyperedge
- @param hyperedge: Hyperedge.
- """
- self.node_links[node].remove(hyperedge)
- self.edge_links[hyperedge].remove(node)
-
-
- def accessibility(self):
- """
- Accessibility matrix (transitive closure).
-
- @rtype: dictionary
- @return: Accessibility information for each node.
- """
- access_ = accessibility.accessibility(self.graph)
- access = {}
-
- for each in access_.keys():
- if (each[1] == 'n'):
- access[each[0]] = []
- for other in access_[each]:
- if (other[1] == 'n'):
- access[each[0]].append(other[0])
-
- return access
-
-
- def connected_components(self):
- """
- Connected components.
-
- @rtype: dictionary
- @return: Pairing that associates each node to its connected component.
- """
- components_ = accessibility.connected_components(self.graph)
- components = {}
-
- for each in components_.keys():
- if (each[1] == 'n'):
- components[each[0]] = components_[each]
-
- return components
-
-
- def cut_nodes(self):
- """
- Return the cut-nodes of the given hypergraph.
-
- @rtype: list
- @return: List of cut-nodes.
- """
- cut_nodes_ = accessibility.cut_nodes(self.graph)
- cut_nodes = []
-
- for each in cut_nodes_:
- if (each[1] == 'n'):
- cut_nodes.append(each[0])
-
- return cut_nodes
-
-
- def cut_hyperedges(self):
- """
- Return the cut-hyperedges of the given hypergraph.
-
- @rtype: list
- @return: List of cut-nodes.
- """
- cut_nodes_ = accessibility.cut_nodes(self.graph)
- cut_nodes = []
-
- for each in cut_nodes_:
- if (each[1] == 'h'):
- cut_nodes.append(each[0])
-
- return cut_nodes
-
- def rank(self):
- """
- Return the rank of the given hypergraph.
-
- @rtype: int
- @return: Rank of graph.
- """
- max_rank = 0
-
- for each in hyperedges:
- if len(each) > max_rank:
- max_rank = len(each)
-
- return max_rank