scripts/graph/__init__.py
changeset 599 32a30f609530
parent 594 06c2228e39cb
equal deleted inserted replaced
598:c1f9435bb645 599:32a30f609530
       
     1 # Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com>
       
     2 #                         Christian Muise <christian.muise@gmail.com>
       
     3 #                         Nathan Davis <davisn90210@gmail.com>
       
     4 #                         Zsolt Haraszti <zsolt@drawwell.net>
       
     5 #
       
     6 # Permission is hereby granted, free of charge, to any person
       
     7 # obtaining a copy of this software and associated documentation
       
     8 # files (the "Software"), to deal in the Software without
       
     9 # restriction, including without limitation the rights to use,
       
    10 # copy, modify, merge, publish, distribute, sublicense, and/or sell
       
    11 # copies of the Software, and to permit persons to whom the
       
    12 # Software is furnished to do so, subject to the following
       
    13 # conditions:
       
    14 
       
    15 # The above copyright notice and this permission notice shall be
       
    16 # included in all copies or substantial portions of the Software.
       
    17 
       
    18 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
       
    19 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
       
    20 # OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
       
    21 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
       
    22 # HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
       
    23 # WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
       
    24 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
       
    25 # OTHER DEALINGS IN THE SOFTWARE.
       
    26 
       
    27 
       
    28 """
       
    29 python-graph
       
    30 
       
    31 A library for working with graphs in Python.
       
    32 
       
    33 @version: 1.3.1
       
    34 """
       
    35 
       
    36 
       
    37 # Imports
       
    38 import accessibility
       
    39 import generators
       
    40 import minmax
       
    41 import searching
       
    42 import sorting
       
    43 import readwrite
       
    44 import traversal
       
    45 
       
    46 
       
    47 # Graph class --------------------------------------------------------------------------------------
       
    48 
       
    49 class graph (object):
       
    50 	"""
       
    51 	Graph class.
       
    52 	
       
    53 	Graphs are built of nodes and edges.
       
    54 
       
    55 	@sort:  __init__, __getitem__, __iter__, __len__, __str__, add_edge, add_edge_attribute,
       
    56 	add_graph, add_node, add_node_attribute, add_nodes, add_spanning_tree, complete, del_edge,
       
    57 	del_node, edges, get_edge_attributes, get_edge_label, get_edge_weight, get_node_attributes,
       
    58 	has_edge, has_node, inverse, neighbors, nodes, order, set_edge_label, set_edge_weight,
       
    59 	traversal, generate, read, write, accessibility, breadth_first_search, connected_components,
       
    60 	cut_edges, cut_nodes, depth_first_search, minimal_spanning_tree, shortest_path
       
    61 	"""
       
    62 
       
    63 
       
    64 	def __init__(self):
       
    65 		"""
       
    66 		Initialize a graph.
       
    67 		"""
       
    68 		self.node_neighbors = {}		# Pairing: Node -> Neighbors
       
    69 		self.edge_properties = {}		# Pairing: Edge -> (Label, Weight)
       
    70 		self.node_attr = {}				# Pairing: Node -> Attributes
       
    71 		self.edge_attr = {}				# Pairing: Edge -> Attributes
       
    72 
       
    73 
       
    74 	def __str__(self):
       
    75 		"""
       
    76 		Return a string representing the graph when requested by str() (or print).
       
    77 
       
    78 		@rtype:  string
       
    79 		@return: String representing the graph.
       
    80 		"""
       
    81 		return "<graph object " + str(self.nodes()) + " " + str(self.edges()) + ">"
       
    82 
       
    83 
       
    84 	def __len__(self):
       
    85 		"""
       
    86 		Return the order of the graph when requested by len().
       
    87 
       
    88 		@rtype:  number
       
    89 		@return: Size of the graph.
       
    90 		"""
       
    91 		return len(self.node_neighbors)
       
    92 
       
    93 
       
    94 	def __iter__(self):
       
    95 		"""
       
    96 		Return a iterator passing through all nodes in the graph.
       
    97 		
       
    98 		@rtype:  iterator
       
    99 		@return: Iterator passing through all nodes in the graph.
       
   100 		"""
       
   101 		for each in self.node_neighbors.iterkeys():
       
   102 			yield each
       
   103 
       
   104 
       
   105 	def __getitem__(self, node):
       
   106 		"""
       
   107 		Return a iterator passing through all neighbors of the given node.
       
   108 		
       
   109 		@rtype:  iterator
       
   110 		@return: Iterator passing through all neighbors of the given node.
       
   111 		"""
       
   112 		for each in self.node_neighbors[node]:
       
   113 			yield each
       
   114 
       
   115 
       
   116 	def read(self, string, fmt='xml'):
       
   117 		"""
       
   118 		Read a graph from a string. Nodes and edges specified in the input will be added to the
       
   119 		current graph.
       
   120 		
       
   121 		@type  string: string
       
   122 		@param string: Input string specifying a graph.
       
   123 
       
   124 		@type  fmt: string
       
   125 		@param fmt: Input format. Possible formats are:
       
   126 			1. 'xml' - XML (default)
       
   127 		"""
       
   128 		if (fmt == 'xml'):
       
   129 			readwrite.read_xml(self, string)
       
   130 
       
   131 
       
   132 	def write(self, fmt='xml'):
       
   133 		"""
       
   134 		Write the graph to a string. Depending of the output format, this string can be used by
       
   135 		read() to rebuild the graph.
       
   136 		
       
   137 		@type  fmt: string
       
   138 		@param fmt: Output format. Possible formats are:
       
   139 			1. 'xml' - XML (default)
       
   140 			2. 'dot' - DOT Language (for GraphViz)
       
   141 			3. 'dotwt' - DOT Language with weight information
       
   142 
       
   143 		@rtype:  string
       
   144 		@return: String specifying the graph.
       
   145 		"""
       
   146 		if (fmt == 'xml'):
       
   147 			return readwrite.write_xml(self)
       
   148 		elif (fmt == 'dot'):
       
   149 			return readwrite.write_dot_graph(self, False)
       
   150 		elif (fmt == 'dotwt'):
       
   151 			return readwrite.write_dot_graph(self, True)
       
   152 
       
   153 
       
   154 	def generate(self, num_nodes, num_edges, weight_range=(1, 1)):
       
   155 		"""
       
   156 		Add nodes and random edges to the graph.
       
   157 		
       
   158 		@type  num_nodes: number
       
   159 		@param num_nodes: Number of nodes.
       
   160 		
       
   161 		@type  num_edges: number
       
   162 		@param num_edges: Number of edges.
       
   163 
       
   164 		@type  weight_range: tuple
       
   165 		@param weight_range: tuple of two integers as lower and upper limits on randomly generated
       
   166 		weights (uniform distribution).
       
   167 		"""
       
   168 		generators.generate(self, num_nodes, num_edges, weight_range)
       
   169 
       
   170 
       
   171 	def nodes(self):
       
   172 		"""
       
   173 		Return node list.
       
   174 
       
   175 		@rtype:  list
       
   176 		@return: Node list.
       
   177 		"""
       
   178 		return self.node_neighbors.keys()
       
   179 
       
   180 
       
   181 	def neighbors(self, node):
       
   182 		"""
       
   183 		Return all nodes that are directly accessible from given node.
       
   184 
       
   185 		@type  node: node
       
   186 		@param node: Node identifier
       
   187 
       
   188 		@rtype:  list
       
   189 		@return: List of nodes directly accessible from given node.
       
   190 		"""
       
   191 		return self.node_neighbors[node]
       
   192 	
       
   193 	
       
   194 	def edges(self):
       
   195 		"""
       
   196 		Return all edges in the graph.
       
   197 		
       
   198 		@rtype:  list
       
   199 		@return: List of all edges in the graph.
       
   200 		"""
       
   201 		return self.edge_properties.keys()
       
   202 
       
   203 
       
   204 	def has_node(self, node):
       
   205 		"""
       
   206 		Return whether the requested node exists.
       
   207 
       
   208 		@type  node: node
       
   209 		@param node: Node identifier
       
   210 
       
   211 		@rtype:  boolean
       
   212 		@return: Truth-value for node existence.
       
   213 		"""
       
   214 		return self.node_neighbors.has_key(node)
       
   215 
       
   216 
       
   217 	def add_node(self, node, attrs=[]):
       
   218 		"""
       
   219 		Add given node to the graph.
       
   220 		
       
   221 		@attention: While nodes can be of any type, it's strongly recommended to use only numbers
       
   222 		and single-line strings as node identifiers if you intend to use write().
       
   223 
       
   224 		@type  node: node
       
   225 		@param node: Node identifier.
       
   226 		
       
   227 		@type  attrs: list
       
   228 		@param attrs: List of node attributes specified as (attribute, value) tuples.
       
   229 		"""
       
   230 		if (not node in self.node_neighbors):
       
   231 			self.node_neighbors[node] = []
       
   232 			self.node_attr[node] = attrs
       
   233 
       
   234 
       
   235 	def add_nodes(self, nodelist):
       
   236 		"""
       
   237 		Add given nodes to the graph.
       
   238 		
       
   239 		@attention: While nodes can be of any type, it's strongly recommended to use only numbers
       
   240 		and single-line strings as node identifiers if you intend to use write().
       
   241 
       
   242 		@type  nodelist: list
       
   243 		@param nodelist: List of nodes to be added to the graph.
       
   244 		"""
       
   245 		for each in nodelist:
       
   246 			self.add_node(each)
       
   247 
       
   248 
       
   249 	def add_edge(self, u, v, wt=1, label='', attrs=[]):
       
   250 		"""
       
   251 		Add an edge (u,v) to the graph connecting nodes u and v.
       
   252 
       
   253 		@type  u: node
       
   254 		@param u: One node.
       
   255 
       
   256 		@type  v: node
       
   257 		@param v: Other node.
       
   258 		
       
   259 		@type  wt: number
       
   260 		@param wt: Edge weight.
       
   261 		
       
   262 		@type  label: string
       
   263 		@param label: Edge label.
       
   264 		
       
   265 		@type  attrs: list
       
   266 		@param attrs: List of node attributes specified as (attribute, value) tuples.
       
   267 		"""
       
   268 		if (v not in self.node_neighbors[u] and u not in self.node_neighbors[v]):
       
   269 			self.node_neighbors[u].append(v)
       
   270 			self.node_neighbors[v].append(u)
       
   271 			self.edge_properties[(u, v)] = [label, wt]
       
   272 			self.edge_properties[(v, u)] = [label, wt]
       
   273 			self.edge_attr[(u, v)] = attrs
       
   274 			self.edge_attr[(v, u)] = attrs
       
   275 
       
   276 
       
   277 	def del_node(self, node):
       
   278 		"""
       
   279 		Remove a node from the graph.
       
   280 		
       
   281 		@type  node: node
       
   282 		@param node: Node identifier.
       
   283 		"""
       
   284 		for each in list(self.neighbors(node)):
       
   285 			self.del_edge(each, node)
       
   286 		del(self.node_neighbors[node])
       
   287 		del(self.node_attr[node])
       
   288 
       
   289 
       
   290 	def del_edge(self, u, v):
       
   291 		"""
       
   292 		Remove an edge (u, v) from the graph.
       
   293 
       
   294 		@type  u: node
       
   295 		@param u: One node.
       
   296 
       
   297 		@type  v: node
       
   298 		@param v: Other node.
       
   299 		"""
       
   300 		self.node_neighbors[u].remove(v)
       
   301 		self.node_neighbors[v].remove(u)
       
   302 		del(self.edge_properties[(u,v)])
       
   303 		del(self.edge_properties[(v,u)])
       
   304 		del(self.edge_attr[(u,v)])
       
   305 		del(self.edge_attr[(v,u)])
       
   306 
       
   307 
       
   308 	def get_edge_weight(self, u, v):
       
   309 		"""
       
   310 		Get the weight of an edge.
       
   311 
       
   312 		@type  u: node
       
   313 		@param u: One node.
       
   314 
       
   315 		@type  v: node
       
   316 		@param v: Other node.
       
   317 		
       
   318 		@rtype:  number
       
   319 		@return: Edge weight.
       
   320 		"""
       
   321 		return self.edge_properties[(u, v)][1]
       
   322 
       
   323 
       
   324 	def set_edge_weight(self, u, v, wt):
       
   325 		"""
       
   326 		Set the weight of an edge.
       
   327 
       
   328 		@type  u: node
       
   329 		@param u: One node.
       
   330 
       
   331 		@type  v: node
       
   332 		@param v: Other node.
       
   333 
       
   334 		@type  wt: number
       
   335 		@param wt: Edge weight.
       
   336 		"""
       
   337 		self.edge_properties[(u, v)][1] = wt
       
   338 		self.edge_properties[(v, u)][1] = wt
       
   339 
       
   340 
       
   341 	def get_edge_label(self, u, v):
       
   342 		"""
       
   343 		Get the label of an edge.
       
   344 
       
   345 		@type  u: node
       
   346 		@param u: One node.
       
   347 
       
   348 		@type  v: node
       
   349 		@param v: Other node.
       
   350 		
       
   351 		@rtype:  string
       
   352 		@return: Edge label
       
   353 		"""
       
   354 		return self.edge_properties[(u, v)][0]
       
   355 
       
   356 
       
   357 	def set_edge_label(self, u, v, label):
       
   358 		"""
       
   359 		Set the label of an edge.
       
   360 
       
   361 		@type  u: node
       
   362 		@param u: One node.
       
   363 
       
   364 		@type  v: node
       
   365 		@param v: Other node.
       
   366 
       
   367 		@type  label: string
       
   368 		@param label: Edge label.
       
   369 		"""
       
   370 		self.edge_properties[(u, v)][0] = label
       
   371 		self.edge_properties[(v, u)][0] = label
       
   372 	
       
   373 	
       
   374 	def add_node_attribute(self, node, attr):
       
   375 		"""
       
   376 		Add attribute to the given node.
       
   377 
       
   378 		@type  node: node
       
   379 		@param node: Node identifier
       
   380 
       
   381 		@type  attr: tuple
       
   382 		@param attr: Node attribute specified as a tuple in the form (attribute, value).
       
   383 		"""
       
   384 		self.node_attr[node] = self.node_attr[node] + [attr]
       
   385 
       
   386 
       
   387 	def get_node_attributes(self, node):
       
   388 		"""
       
   389 		Return the attributes of the given node.
       
   390 
       
   391 		@type  node: node
       
   392 		@param node: Node identifier
       
   393 
       
   394 		@rtype:  list
       
   395 		@return: List of attributes specified tuples in the form (attribute, value).
       
   396 		"""
       
   397 		return self.node_attr[node]
       
   398 
       
   399 
       
   400 	def add_edge_attribute(self, u, v, attr):
       
   401 		"""
       
   402 		Add attribute to the given edge.
       
   403 
       
   404 		@type  u: node
       
   405 		@param u: One node.
       
   406 
       
   407 		@type  v: node
       
   408 		@param v: Other node.
       
   409 
       
   410 		@type  attr: tuple
       
   411 		@param attr: Node attribute specified as a tuple in the form (attribute, value).
       
   412 		"""
       
   413 		self.edge_attr[(u,v)] = self.edge_attr[(u,v)] + [attr]
       
   414 		self.edge_attr[(v,u)] = self.edge_attr[(v,u)] + [attr]
       
   415 
       
   416 
       
   417 	def get_edge_attributes(self, u, v):
       
   418 		"""
       
   419 		Return the attributes of the given edge.
       
   420 
       
   421 		@type  u: node
       
   422 		@param u: One node.
       
   423 
       
   424 		@type  v: node
       
   425 		@param v: Other node.
       
   426 
       
   427 		@rtype:  list
       
   428 		@return: List of attributes specified tuples in the form (attribute, value).
       
   429 		"""
       
   430 		return self.edge_attr[(u,v)]
       
   431 
       
   432 
       
   433 	def has_edge(self, u, v):
       
   434 		"""
       
   435 		Return whether an edge between nodes u and v exists.
       
   436 
       
   437 		@type  u: node
       
   438 		@param u: One node.
       
   439 
       
   440 		@type  v: node
       
   441 		@param v: Other node.
       
   442 
       
   443 		@rtype:  boolean
       
   444 		@return: Truth-value for edge existence.
       
   445 		"""
       
   446 		return self.edge_properties.has_key((u,v)) and self.edge_properties.has_key((v,u))
       
   447 	
       
   448 	
       
   449 	def order(self, node):
       
   450 		"""
       
   451 		Return the order of the given node.
       
   452 		
       
   453 		@rtype:  number
       
   454 		@return: Order of the given node.
       
   455 		"""
       
   456 		return len(self.neighbors(node))
       
   457 
       
   458 
       
   459 	def complete(self):
       
   460 		"""
       
   461 		Make the graph a complete graph.
       
   462 		
       
   463 		@attention: This will modify the current graph.
       
   464 		"""
       
   465 		for each in self.nodes():
       
   466 			for other in self.nodes():
       
   467 				if (each != other):
       
   468 					self.add_edge(each, other)
       
   469 
       
   470 
       
   471 	def inverse(self):
       
   472 		"""
       
   473 		Return the inverse of the graph.
       
   474 		
       
   475 		@rtype:  graph
       
   476 		@return: Complement graph for the graph.
       
   477 		"""
       
   478 		inv = graph()
       
   479 		inv.add_nodes(self.nodes())
       
   480 		inv.complete()
       
   481 		for each in self.edges():
       
   482 			if (inv.has_edge(each[0], each[1])):
       
   483 				inv.del_edge(each[0], each[1])
       
   484 		return inv
       
   485 
       
   486 
       
   487 	def add_graph(self, graph):
       
   488 		"""
       
   489 		Add other graph to the graph.
       
   490 		
       
   491 		@attention: Attributes and labels are not preserved.
       
   492 		
       
   493 		@type  graph: graph
       
   494 		@param graph: Graph
       
   495 		"""
       
   496 		self.add_nodes(graph.nodes())
       
   497 		for each_node in graph.nodes():
       
   498 			for each_edge in graph.neighbors(each_node):
       
   499 				self.add_edge(each_node, each_edge)
       
   500 
       
   501 
       
   502 	def add_spanning_tree(self, st):
       
   503 		"""
       
   504 		Add a spanning tree to the graph.
       
   505 		
       
   506 		@type  st: dictionary
       
   507 		@param st: Spanning tree.
       
   508 		"""
       
   509 		self.add_nodes(st.keys())
       
   510 		for each in st:
       
   511 			if (st[each] is not None):
       
   512 				self.add_edge(st[each], each)
       
   513 
       
   514 
       
   515 	def traversal(self, node, order='pre'):
       
   516 		"""
       
   517 		Graph traversal iterator.
       
   518 
       
   519 		@type  node: node
       
   520 		@param node: Node.
       
   521 		
       
   522 		@type  order: string
       
   523 		@param order: traversal ordering. Possible values are:
       
   524 			2. 'pre' - Preordering (default)
       
   525 			1. 'post' - Postordering
       
   526 		
       
   527 		@rtype:  iterator
       
   528 		@return: Traversal iterator.
       
   529 		"""
       
   530 		for each in traversal.traversal(self, node, order):
       
   531 			yield each
       
   532 
       
   533 
       
   534 	def depth_first_search(self, root=None):
       
   535 		"""
       
   536 		Depht-first search.
       
   537 		
       
   538 		@type  root: node
       
   539 		@param root: Optional root node (will explore only root's connected component)
       
   540 
       
   541 		@rtype:  tuple
       
   542 		@return:  tupple containing a dictionary and two lists:
       
   543 			1. Generated spanning tree
       
   544 			2. Graph's preordering
       
   545 			3. Graph's postordering
       
   546 		"""
       
   547 		return searching.depth_first_search(self, root)
       
   548 
       
   549 
       
   550 	def breadth_first_search(self, root=None):
       
   551 		"""
       
   552 		Breadth-first search.
       
   553 
       
   554 		@type  root: node
       
   555 		@param root: Optional root node (will explore only root's connected component)
       
   556 
       
   557 		@rtype:  dictionary
       
   558 		@return: A tuple containing a dictionary and a list.
       
   559 			1. Generated spanning tree
       
   560 			2. Graph's level-based ordering
       
   561 		"""
       
   562 		return searching.breadth_first_search(self, root)
       
   563 
       
   564 
       
   565 	def accessibility(self):
       
   566 		"""
       
   567 		Accessibility matrix (transitive closure).
       
   568 
       
   569 		@rtype:  dictionary
       
   570 		@return: Accessibility information for each node.
       
   571 		"""
       
   572 		return accessibility.accessibility(self)
       
   573 
       
   574 
       
   575 	def connected_components(self):
       
   576 		"""
       
   577 		Connected components.
       
   578 
       
   579 		@attention: Indentification of connected components is meaningful only for non-directed
       
   580 		graphs.
       
   581 
       
   582 		@rtype:  dictionary
       
   583 		@return: Pairing that associates each node to its connected component.
       
   584 		"""
       
   585 		return accessibility.connected_components(self)
       
   586 
       
   587 
       
   588 	def minimal_spanning_tree(self, root=None):
       
   589 		"""
       
   590 		Minimal spanning tree.
       
   591 
       
   592 		@type  root: node
       
   593 		@param root: Optional root node (will explore only root's connected component)
       
   594 
       
   595 		@attention: Minimal spanning tree meaningful only for weighted graphs.
       
   596 
       
   597 		@rtype:  list
       
   598 		@return: Generated spanning tree.
       
   599 		"""
       
   600 		return minmax.minimal_spanning_tree(self, root)
       
   601 
       
   602 
       
   603 	def shortest_path(self, source):
       
   604 		"""
       
   605 		Return the shortest path distance between source node and all other nodes using Dijkstra's
       
   606 		algorithm.
       
   607 		
       
   608 		@attention: All weights must be nonnegative.
       
   609 
       
   610 		@type  source: node
       
   611 		@param source: Node from which to start the search.
       
   612 
       
   613 		@rtype:  tuple
       
   614 		@return: A tuple containing two dictionaries, each keyed by target nodes.
       
   615 			1. Shortest path spanning tree
       
   616 			2. Shortest distance from given source to each target node
       
   617 		Inaccessible target nodes do not appear in either dictionary.
       
   618 		"""
       
   619 		return minmax.shortest_path(self, source)
       
   620 	
       
   621 	
       
   622 	def cut_edges(self):
       
   623 		"""
       
   624 		Return the cut-edges of the given graph.
       
   625 		
       
   626 		@rtype:  list
       
   627 		@return: List of cut-edges.
       
   628 		"""
       
   629 		return accessibility.cut_edges(self)
       
   630 
       
   631 
       
   632 	def cut_nodes(self):
       
   633 		"""
       
   634 		Return the cut-nodes of the given graph.
       
   635 		
       
   636 		@rtype:  list
       
   637 		@return: List of cut-nodes.
       
   638 		"""
       
   639 		return accessibility.cut_nodes(self)
       
   640 
       
   641 
       
   642 # Digraph class ------------------------------------------------------------------------------------
       
   643 
       
   644 class digraph (object):
       
   645 	"""
       
   646 	Digraph class.
       
   647 	
       
   648 	Digraphs are built of nodes and directed edges.
       
   649 
       
   650 	@sort: __init__, __getitem__, __iter__, __len__, __str__, add_edge, add_edge_attribute,
       
   651 	add_graph, add_node, add_node_attribute, add_nodes, add_spanning_tree, complete, degree,
       
   652 	del_edge, del_node, edges, get_edge_attributes, get_edge_label, get_edge_weight,
       
   653 	get_node_attributes, has_edge, has_node, incidents, inverse, neighbors, nodes, order,
       
   654 	set_edge_label, set_edge_weight, traversal, generate, read, write, accessibility,
       
   655 	breadth_first_search, cut_edges, cut_nodes, depth_first_search, minimal_spanning_tree,
       
   656 	mutual_accessibility, shortest_path, topological_sorting
       
   657 	"""
       
   658 
       
   659 
       
   660 	def __init__(self):
       
   661 		"""
       
   662 		Initialize a digraph.
       
   663 		"""
       
   664 		self.node_neighbors = {}	# Pairing: Node -> Neighbors
       
   665 		self.edge_properties = {}	# Pairing: Edge -> (Label, Weight)
       
   666 		self.node_incidence = {}	# Pairing: Node -> Incident nodes
       
   667 		self.node_attr = {}			# Pairing: Node -> Attributes
       
   668 		self.edge_attr = {}			# Pairing: Edge -> Attributes
       
   669 
       
   670 
       
   671 	def __str__(self):
       
   672 		"""
       
   673 		Return a string representing the digraph when requested by str() (or print).
       
   674 
       
   675 		@rtype:  string
       
   676 		@return: String representing the graph.
       
   677 		"""
       
   678 		return "<graph object " + str(self.nodes()) + " " + str(self.edges()) + ">"
       
   679 
       
   680 
       
   681 	def __len__(self):
       
   682 		"""
       
   683 		Return the order of the digraph when requested by len().
       
   684 
       
   685 		@rtype:  number
       
   686 		@return: Size of the graph.
       
   687 		"""
       
   688 		return len(self.node_neighbors)
       
   689 
       
   690 
       
   691 	def __iter__(self):
       
   692 		"""
       
   693 		Return a iterator passing through all nodes in the digraph.
       
   694 		
       
   695 		@rtype:  iterator
       
   696 		@return: Iterator passing through all nodes in the digraph.
       
   697 		"""
       
   698 		for each in self.node_neighbors.iterkeys():
       
   699 			yield each
       
   700 
       
   701 
       
   702 	def __getitem__(self, node):
       
   703 		"""
       
   704 		Return a iterator passing through all neighbors of the given node.
       
   705 		
       
   706 		@rtype:  iterator
       
   707 		@return: Iterator passing through all neighbors of the given node.
       
   708 		"""
       
   709 		for each in self.node_neighbors[node]:
       
   710 			yield each
       
   711 
       
   712 
       
   713 	def read(self, string, fmt='xml'):
       
   714 		"""
       
   715 		Read a graph from a string. Nodes and edges specified in the input will be added to the
       
   716 		current graph.
       
   717 		
       
   718 		@type  string: string
       
   719 		@param string: Input string specifying a graph.
       
   720 
       
   721 		@type  fmt: string
       
   722 		@param fmt: Input format. Possible formats are:
       
   723 			1. 'xml' - XML (default)
       
   724 		"""
       
   725 		if (fmt == 'xml'):
       
   726 			readwrite.read_xml(self, string)
       
   727 
       
   728 
       
   729 	def write(self, fmt='xml'):
       
   730 		"""
       
   731 		Write the graph to a string. Depending of the output format, this string can be used by
       
   732 		read() to rebuild the graph.
       
   733 		
       
   734 		@type  fmt: string
       
   735 		@param fmt: Output format. Possible formats are:
       
   736 			1. 'xml' - XML (default)
       
   737 			2. 'dot' - DOT Language (for GraphViz)
       
   738 			3. 'dotwt' - DOT Language with weight information
       
   739 
       
   740 		@rtype:  string
       
   741 		@return: String specifying the graph.
       
   742 		"""
       
   743 		if (fmt == 'xml'):
       
   744 			return readwrite.write_xml(self)
       
   745 		elif (fmt == 'dot'):
       
   746 			return readwrite.write_dot_digraph(self, False)
       
   747 		elif (fmt == 'dotwt'):
       
   748 			return readwrite.write_dot_digraph(self, True)
       
   749 
       
   750 
       
   751 	def generate(self, num_nodes, num_edges, weight_range=(1, 1)):
       
   752 		"""
       
   753 		Add nodes and random edges to the graph.
       
   754 		
       
   755 		@type  num_nodes: number
       
   756 		@param num_nodes: Number of nodes.
       
   757 		
       
   758 		@type  num_edges: number
       
   759 		@param num_edges: Number of edges.
       
   760 
       
   761 		@type  weight_range: tuple
       
   762 		@param weight_range: tuple of two integers as lower and upper limits on randomly generated
       
   763 		weights (uniform distribution).
       
   764 		"""
       
   765 		generators.generate(self, num_nodes, num_edges, weight_range)
       
   766 
       
   767 
       
   768 	def nodes(self):
       
   769 		"""
       
   770 		Return node list.
       
   771 
       
   772 		@rtype:  list
       
   773 		@return: Node list.
       
   774 		"""
       
   775 		return self.node_neighbors.keys()
       
   776 
       
   777 
       
   778 	def neighbors(self, node):
       
   779 		"""
       
   780 		Return all nodes that are directly accessible from given node.
       
   781 
       
   782 		@type  node: node
       
   783 		@param node: Node identifier
       
   784 
       
   785 		@rtype:  list
       
   786 		@return: List of nodes directly accessible from given node.
       
   787 		"""
       
   788 		return self.node_neighbors[node]
       
   789 	
       
   790 	
       
   791 	def incidents(self, node):
       
   792 		"""
       
   793 		Return all nodes that are incident to the given node.
       
   794 		
       
   795 		@type  node: node
       
   796 		@param node: Node identifier
       
   797 
       
   798 		@rtype:  list
       
   799 		@return: List of nodes directly accessible from given node.	
       
   800 		"""
       
   801 		return self.node_incidence[node]
       
   802 		
       
   803 	
       
   804 	
       
   805 	def edges(self):
       
   806 		"""
       
   807 		Return all edges in the graph.
       
   808 		
       
   809 		@rtype:  list
       
   810 		@return: List of all edges in the graph.
       
   811 		"""
       
   812 		return self.edge_properties.keys()
       
   813 
       
   814 
       
   815 	def has_node(self, node):
       
   816 		"""
       
   817 		Return whether the requested node exists.
       
   818 
       
   819 		@type  node: node
       
   820 		@param node: Node identifier
       
   821 
       
   822 		@rtype:  boolean
       
   823 		@return: Truth-value for node existence.
       
   824 		"""
       
   825 		return self.node_neighbors.has_key(node)
       
   826 
       
   827 
       
   828 	def add_node(self, node, attrs=[]):
       
   829 		"""
       
   830 		Add given node to the graph.
       
   831 		
       
   832 		@attention: While nodes can be of any type, it's strongly recommended to use only numbers
       
   833 		and single-line strings as node identifiers if you intend to use write().
       
   834 
       
   835 		@type  node: node
       
   836 		@param node: Node identifier.
       
   837 		
       
   838 		@type  attrs: list
       
   839 		@param attrs: List of node attributes specified as (attribute, value) tuples.
       
   840 		"""
       
   841 		if (node not in self.node_neighbors):
       
   842 			self.node_neighbors[node] = []
       
   843 			self.node_incidence[node] = []
       
   844 			self.node_attr[node] = attrs
       
   845 
       
   846 
       
   847 	def add_nodes(self, nodelist):
       
   848 		"""
       
   849 		Add given nodes to the graph.
       
   850 		
       
   851 		@attention: While nodes can be of any type, it's strongly recommended to use only numbers
       
   852 		and single-line strings as node identifiers if you intend to use write().
       
   853 
       
   854 		@type  nodelist: list
       
   855 		@param nodelist: List of nodes to be added to the graph.
       
   856 		"""
       
   857 		for each in nodelist:
       
   858 			self.add_node(each)
       
   859 
       
   860 
       
   861 	def add_edge(self, u, v, wt=1, label='', attrs=[]):
       
   862 		"""
       
   863 		Add an directed edge (u,v) to the graph connecting nodes u to v.
       
   864 
       
   865 		@type  u: node
       
   866 		@param u: One node.
       
   867 
       
   868 		@type  v: node
       
   869 		@param v: Other node.
       
   870 		
       
   871 		@type  wt: number
       
   872 		@param wt: Edge weight.
       
   873 		
       
   874 		@type  label: string
       
   875 		@param label: Edge label.
       
   876 		
       
   877 		@type  attrs: list
       
   878 		@param attrs: List of node attributes specified as (attribute, value) tuples.
       
   879 		"""
       
   880 		if (v not in self.node_neighbors[u]):
       
   881 			self.node_neighbors[u].append(v)
       
   882 			self.node_incidence[v].append(u)
       
   883 			self.edge_properties[(u, v)] = [label, wt]
       
   884 			self.edge_attr[(u, v)] = attrs
       
   885 
       
   886 
       
   887 	def del_node(self, node):
       
   888 		"""
       
   889 		Remove a node from the graph.
       
   890 		
       
   891 		@type  node: node
       
   892 		@param node: Node identifier.
       
   893 		"""
       
   894 		for each in list(self.incidents(node)):
       
   895 			self.del_edge(each, node)
       
   896 		for each in list(self.neighbors(node)):
       
   897 			self.del_edge(node, each)
       
   898 		del(self.node_neighbors[node])
       
   899 		del(self.node_incidence[node])
       
   900 		del(self.node_attr[node])
       
   901 
       
   902 
       
   903 	def del_edge(self, u, v):
       
   904 		"""
       
   905 		Remove an directed edge (u, v) from the graph.
       
   906 
       
   907 		@type  u: node
       
   908 		@param u: One node.
       
   909 
       
   910 		@type  v: node
       
   911 		@param v: Other node.
       
   912 		"""
       
   913 		self.node_neighbors[u].remove(v)
       
   914 		self.node_incidence[v].remove(u)
       
   915 		del(self.edge_properties[(u,v)])
       
   916 		del(self.edge_attr[(u,v)])
       
   917 
       
   918 
       
   919 	def get_edge_weight(self, u, v):
       
   920 		"""
       
   921 		Get the weight of an edge.
       
   922 
       
   923 		@type  u: node
       
   924 		@param u: One node.
       
   925 
       
   926 		@type  v: node
       
   927 		@param v: Other node.
       
   928 		
       
   929 		@rtype:  number
       
   930 		@return: Edge weight.
       
   931 		"""
       
   932 		return self.edge_properties[(u, v)][1]
       
   933 
       
   934 
       
   935 	def set_edge_weight(self, u, v, wt):
       
   936 		"""
       
   937 		Set the weight of an edge.
       
   938 
       
   939 		@type  u: node
       
   940 		@param u: One node.
       
   941 
       
   942 		@type  v: node
       
   943 		@param v: Other node.
       
   944 
       
   945 		@type  wt: number
       
   946 		@param wt: Edge weight.
       
   947 		"""
       
   948 		self.edge_properties[(u, v)][1] = wt
       
   949 
       
   950 
       
   951 	def get_edge_label(self, u, v):
       
   952 		"""
       
   953 		Get the label of an edge.
       
   954 
       
   955 		@type  u: node
       
   956 		@param u: One node.
       
   957 
       
   958 		@type  v: node
       
   959 		@param v: Other node.
       
   960 		
       
   961 		@rtype:  string
       
   962 		@return: Edge label
       
   963 		"""
       
   964 		return self.edge_properties[(u, v)][0]
       
   965 
       
   966 
       
   967 	def set_edge_label(self, u, v, label):
       
   968 		"""
       
   969 		Set the label of an edge.
       
   970 
       
   971 		@type  u: node
       
   972 		@param u: One node.
       
   973 
       
   974 		@type  v: node
       
   975 		@param v: Other node.
       
   976 
       
   977 		@type  label: string
       
   978 		@param label: Edge label.
       
   979 		"""
       
   980 		self.edge_properties[(u, v)][0] = label
       
   981 	
       
   982 	
       
   983 	def add_node_attribute(self, node, attr):
       
   984 		"""
       
   985 		Add attribute to the given node.
       
   986 
       
   987 		@type  node: node
       
   988 		@param node: Node identifier
       
   989 
       
   990 		@type  attr: tuple
       
   991 		@param attr: Node attribute specified as a tuple in the form (attribute, value).
       
   992 		"""
       
   993 		self.node_attr[node] = self.node_attr[node] + [attr]
       
   994 
       
   995 
       
   996 	def get_node_attributes(self, node):
       
   997 		"""
       
   998 		Return the attributes of the given node.
       
   999 
       
  1000 		@type  node: node
       
  1001 		@param node: Node identifier
       
  1002 
       
  1003 		@rtype:  list
       
  1004 		@return: List of attributes specified tuples in the form (attribute, value).
       
  1005 		"""
       
  1006 		return self.node_attr[node]
       
  1007 
       
  1008 
       
  1009 	def add_edge_attribute(self, u, v, attr):
       
  1010 		"""
       
  1011 		Add attribute to the given edge.
       
  1012 
       
  1013 		@type  u: node
       
  1014 		@param u: One node.
       
  1015 
       
  1016 		@type  v: node
       
  1017 		@param v: Other node.
       
  1018 
       
  1019 		@type  attr: tuple
       
  1020 		@param attr: Node attribute specified as a tuple in the form (attribute, value).
       
  1021 		"""
       
  1022 		self.edge_attr[(u,v)] = self.edge_attr[(u,v)] + [attr]
       
  1023 
       
  1024 
       
  1025 	def get_edge_attributes(self, u, v):
       
  1026 		"""
       
  1027 		Return the attributes of the given edge.
       
  1028 
       
  1029 		@type  u: node
       
  1030 		@param u: One node.
       
  1031 
       
  1032 		@type  v: node
       
  1033 		@param v: Other node.
       
  1034 
       
  1035 		@rtype:  list
       
  1036 		@return: List of attributes specified tuples in the form (attribute, value).
       
  1037 		"""
       
  1038 		return self.edge_attr[(u,v)]
       
  1039 
       
  1040 
       
  1041 	def has_edge(self, u, v):
       
  1042 		"""
       
  1043 		Return whether an edge between nodes u and v exists.
       
  1044 
       
  1045 		@type  u: node
       
  1046 		@param u: One node.
       
  1047 
       
  1048 		@type  v: node
       
  1049 		@param v: Other node.
       
  1050 
       
  1051 		@rtype:  boolean
       
  1052 		@return: Truth-value for edge existence.
       
  1053 		"""
       
  1054 		return self.edge_properties.has_key((u,v))
       
  1055 
       
  1056 	
       
  1057 	def order(self, node):
       
  1058 		"""
       
  1059 		Return the order of the given node.
       
  1060 		
       
  1061 		@rtype:  number
       
  1062 		@return: Order of the given node.
       
  1063 		"""
       
  1064 		return len(self.neighbors(node))
       
  1065 
       
  1066 
       
  1067 	def degree(self, node):
       
  1068 		"""
       
  1069 		Return the degree of the given node.
       
  1070 		
       
  1071 		@rtype:  number
       
  1072 		@return: Order of the given node.
       
  1073 		"""
       
  1074 		return len(self.node_incidence[node])
       
  1075 
       
  1076 
       
  1077 	def complete(self):
       
  1078 		"""
       
  1079 		Make the graph a complete graph.
       
  1080 		
       
  1081 		@attention: This will modify the current graph.
       
  1082 		"""
       
  1083 		for each in self.nodes():
       
  1084 			for other in self.nodes():
       
  1085 				if (each != other):
       
  1086 					self.add_edge(each, other)
       
  1087 
       
  1088 
       
  1089 	def inverse(self):
       
  1090 		"""
       
  1091 		Return the inverse of the graph.
       
  1092 		
       
  1093 		@rtype:  graph
       
  1094 		@return: Complement graph for the graph.
       
  1095 		"""
       
  1096 		inv = digraph()
       
  1097 		inv.add_nodes(self.nodes())
       
  1098 		inv.complete()
       
  1099 		for each in self.edges():
       
  1100 			inv.del_edge(each[0], each[1])
       
  1101 		return inv
       
  1102 
       
  1103 
       
  1104 	def add_graph(self, graph):
       
  1105 		"""
       
  1106 		Add other graph to the graph.
       
  1107 		
       
  1108 		@attention: Attributes and labels are not preserved.
       
  1109 		
       
  1110 		@type  graph: graph
       
  1111 		@param graph: Graph
       
  1112 		"""
       
  1113 		self.add_nodes(graph.nodes())
       
  1114 		for each_node in graph.nodes():
       
  1115 			for each_edge in graph.neighbors(each_node):
       
  1116 				self.add_edge(each_node, each_edge)
       
  1117 
       
  1118 
       
  1119 	def add_spanning_tree(self, st):
       
  1120 		"""
       
  1121 		Add a spanning tree to the graph.
       
  1122 		
       
  1123 		@type  st: dictionary
       
  1124 		@param st: Spanning tree.
       
  1125 		"""
       
  1126 		self.add_nodes(st.keys())
       
  1127 		for each in st:
       
  1128 			if (st[each] is not None):
       
  1129 				self.add_edge(st[each], each)
       
  1130 
       
  1131 
       
  1132 	def traversal(self, node, order='pre'):
       
  1133 		"""
       
  1134 		Graph traversal iterator.
       
  1135 
       
  1136 		@type  node: node
       
  1137 		@param node: Node.
       
  1138 		
       
  1139 		@type  order: string
       
  1140 		@param order: traversal ordering. Possible values are:
       
  1141 			2. 'pre' - Preordering (default)
       
  1142 			1. 'post' - Postordering
       
  1143 		
       
  1144 		@rtype:  iterator
       
  1145 		@return: Traversal iterator.
       
  1146 		"""
       
  1147 		for each in traversal.traversal(self, node, order):
       
  1148 			yield each
       
  1149 
       
  1150 
       
  1151 	def depth_first_search(self, root=None):
       
  1152 		"""
       
  1153 		Depht-first search.
       
  1154 		
       
  1155 		@type  root: node
       
  1156 		@param root: Optional root node (will explore only root's connected component)
       
  1157 
       
  1158 		@rtype:  tuple
       
  1159 		@return:  tupple containing a dictionary and two lists:
       
  1160 			1. Generated spanning tree
       
  1161 			2. Graph's preordering
       
  1162 			3. Graph's postordering
       
  1163 		"""
       
  1164 		return searching.depth_first_search(self, root)
       
  1165 
       
  1166 
       
  1167 	def accessibility(self):
       
  1168 		"""
       
  1169 		Accessibility matrix (transitive closure).
       
  1170 
       
  1171 		@rtype:  dictionary
       
  1172 		@return: Accessibility information for each node.
       
  1173 		"""
       
  1174 		return accessibility.accessibility(self)
       
  1175 
       
  1176 
       
  1177 	def breadth_first_search(self, root=None):
       
  1178 		"""
       
  1179 		Breadth-first search.
       
  1180 
       
  1181 		@type  root: node
       
  1182 		@param root: Optional root node (will explore only root's connected component)
       
  1183 
       
  1184 		@rtype:  dictionary
       
  1185 		@return: A tuple containing a dictionary and a list.
       
  1186 			1. Generated spanning tree
       
  1187 			2. Graph's level-based ordering
       
  1188 		"""
       
  1189 		return searching.breadth_first_search(self, root)
       
  1190 
       
  1191 
       
  1192 	def mutual_accessibility(self):
       
  1193 		"""
       
  1194 		Mutual-accessibility matrix (strongly connected components).
       
  1195 
       
  1196 		@rtype:  list
       
  1197 		@return: Mutual-accessibility information for each node.
       
  1198 		"""
       
  1199 		return accessibility.mutual_accessibility(self)
       
  1200 
       
  1201 
       
  1202 	def topological_sorting(self):
       
  1203 		"""
       
  1204 		Topological sorting.
       
  1205 
       
  1206 		@attention: Topological sorting is meaningful only for directed acyclic graphs.
       
  1207 
       
  1208 		@rtype:  list
       
  1209 		@return: Topological sorting for the graph.
       
  1210 		"""
       
  1211 		return sorting.topological_sorting(self)
       
  1212 
       
  1213 
       
  1214 	def minimal_spanning_tree(self, root=None):
       
  1215 		"""
       
  1216 		Minimal spanning tree.
       
  1217 
       
  1218 		@type  root: node
       
  1219 		@param root: Optional root node (will explore only root's connected component)
       
  1220 
       
  1221 		@attention: Minimal spanning tree meaningful only for weighted graphs.
       
  1222 
       
  1223 		@rtype:  list
       
  1224 		@return: Generated spanning tree.
       
  1225 		"""
       
  1226 		return minmax.minimal_spanning_tree(self, root)
       
  1227 
       
  1228 
       
  1229 	def shortest_path(self, source):
       
  1230 		"""
       
  1231 		Return the shortest path distance between source node and all other nodes using Dijkstra's
       
  1232 		algorithm.
       
  1233 		
       
  1234 		@attention: All weights must be nonnegative.
       
  1235 
       
  1236 		@type  source: node
       
  1237 		@param source: Node from which to start the search.
       
  1238 
       
  1239 		@rtype:  tuple
       
  1240 		@return: A tuple containing two dictionaries, each keyed by target nodes.
       
  1241 			1. Shortest path spanning tree
       
  1242 			2. Shortest distance from given source to each target node
       
  1243 		Inaccessible target nodes do not appear in either dictionary.
       
  1244 		"""
       
  1245 		return minmax.shortest_path(self, source)
       
  1246 	
       
  1247 	
       
  1248 	def cut_edges(self):
       
  1249 		"""
       
  1250 		Return the cut-edges of the given graph.
       
  1251 		
       
  1252 		@rtype:  list
       
  1253 		@return: List of cut-edges.
       
  1254 		"""
       
  1255 		return accessibility.cut_edges(self)
       
  1256 
       
  1257 
       
  1258 	def cut_nodes(self):
       
  1259 		"""
       
  1260 		Return the cut-nodes of the given graph.
       
  1261 		
       
  1262 		@rtype:  list
       
  1263 		@return: List of cut-nodes.
       
  1264 		"""
       
  1265 		return accessibility.cut_nodes(self)
       
  1266 
       
  1267 
       
  1268 # Hypergraph class ---------------------------------------------------------------------------------
       
  1269 
       
  1270 class hypergraph (object):
       
  1271 	"""
       
  1272 	Hypergraph class.
       
  1273 	
       
  1274 	Hypergraphs are a generalization of graphs where an edge (called hyperedge) can connect more
       
  1275 	than two nodes.
       
  1276 	
       
  1277 	@sort: __init__, __len__, __str__, add_hyperedge, add_hyperedges, add_node,	add_nodes, has_node,
       
  1278 	hyperedges, link, links, nodes, unlink, read, write, accessibility,	connected_components,
       
  1279 	cut_hyperedges, cut_nodes
       
  1280 	"""
       
  1281 
       
  1282 
       
  1283 	def __init__(self):
       
  1284 		"""
       
  1285 		Initialize a hypergraph.
       
  1286 		"""
       
  1287 		self.node_links = {}	# Pairing: Node -> Hyperedge
       
  1288 		self.edge_links = {} 	# Pairing: Hyperedge -> Node
       
  1289 		self.graph = graph()	# Ordinary graph
       
  1290 
       
  1291 
       
  1292 	def __str__(self):
       
  1293 		"""
       
  1294 		Return a string representing the hypergraph when requested by str() (or print).
       
  1295 
       
  1296 		@rtype:  string
       
  1297 		@return: String representing the hypergraph.
       
  1298 		"""
       
  1299 		return "<hypergraph object " + str(self.nodes()) + " " + str(self.edge_links) + ">"
       
  1300 
       
  1301 
       
  1302 	def __len__(self):
       
  1303 		"""
       
  1304 		Return the size of the hypergraph when requested by len().
       
  1305 
       
  1306 		@rtype:  number
       
  1307 		@return: Size of the hypergraph.
       
  1308 		"""
       
  1309 		return len(self.node_links)
       
  1310 
       
  1311 
       
  1312 	def read(self, string, fmt='xml'):
       
  1313 		"""
       
  1314 		Read a hypergraph from a string. Nodes and hyperedges specified in the input will be added
       
  1315 		to the current graph.
       
  1316 		
       
  1317 		@type  string: string
       
  1318 		@param string: Input string specifying a graph.
       
  1319 
       
  1320 		@type  fmt: string
       
  1321 		@param fmt: Input format. Possible formats are:
       
  1322 			1. 'xml' - XML (default)
       
  1323 		"""
       
  1324 		if (fmt == 'xml'):
       
  1325 			readwrite.read_xml_hypergraph(self, string)
       
  1326 
       
  1327 
       
  1328 	def write(self, fmt='xml'):
       
  1329 		"""
       
  1330 		Write the hypergraph to a string. Depending of the output format, this string can be used by
       
  1331 		read() to rebuild the graph.
       
  1332 		
       
  1333 		@type  fmt: string
       
  1334 		@param fmt: Output format. Possible formats are:
       
  1335 			1. 'xml' - XML (default)
       
  1336 			2. 'dot' - DOT Language (for GraphViz)
       
  1337 			3. 'dotclr' - DOT Language, coloured
       
  1338 
       
  1339 		@rtype:  string
       
  1340 		@return: String specifying the graph.
       
  1341 		"""
       
  1342 		if (fmt == 'xml'):
       
  1343 			return readwrite.write_xml_hypergraph(self)
       
  1344 		elif (fmt == 'dot'):
       
  1345 			return readwrite.write_dot_hypergraph(self)
       
  1346 		elif (fmt == 'dotclr'):
       
  1347 			return readwrite.write_dot_hypergraph(self, coloured=True)
       
  1348 	
       
  1349 
       
  1350 	def nodes(self):
       
  1351 		"""
       
  1352 		Return node list.
       
  1353 		
       
  1354 		@rtype:  list
       
  1355 		@return: Node list.
       
  1356 		"""
       
  1357 		return self.node_links.keys()
       
  1358 
       
  1359 
       
  1360 	def hyperedges(self):
       
  1361 		"""
       
  1362 		Return hyperedge list.
       
  1363 
       
  1364 		@rtype:  list
       
  1365 		@return: List of hyperedges linked to the given node.
       
  1366 		"""
       
  1367 		return self.edge_links.keys()
       
  1368 
       
  1369 
       
  1370 	def links(self, obj):
       
  1371 		"""
       
  1372 		Return all objects linked to the given one.
       
  1373 		
       
  1374 		If given a node, linked hyperedges will be returned. If given a hyperedge, linked nodes will
       
  1375 		be returned.
       
  1376 		
       
  1377 		@type  obj: node or hyperedge
       
  1378 		@param obj: Object identifier.
       
  1379 		
       
  1380 		@rtype:  list
       
  1381 		@return: List of objects linked to the given one.
       
  1382 		"""
       
  1383 		if (obj in self.node_links):
       
  1384 			return self.node_links[obj]
       
  1385 		else:
       
  1386 			return self.edge_links[obj]
       
  1387 
       
  1388 
       
  1389 	def has_node(self, node):
       
  1390 		"""
       
  1391 		Return whether the requested node exists.
       
  1392 
       
  1393 		@type  node: node
       
  1394 		@param node: Node identifier
       
  1395 
       
  1396 		@rtype:  boolean
       
  1397 		@return: Truth-value for node existence.
       
  1398 		"""
       
  1399 		return self.node_links.has_key(node)
       
  1400 
       
  1401 
       
  1402 	def add_node(self, node):
       
  1403 		"""
       
  1404 		Add given node to the hypergraph.
       
  1405 		
       
  1406 		@attention: While nodes can be of any type, it's strongly recommended to use only numbers
       
  1407 		and single-line strings as node identifiers if you intend to use write().
       
  1408 
       
  1409 		@type  node: node
       
  1410 		@param node: Node identifier.
       
  1411 		"""
       
  1412 		if (not node in self.node_links):
       
  1413 			self.node_links[node] = []
       
  1414 			self.graph.add_node((node,'n'))
       
  1415 
       
  1416 
       
  1417 	def add_nodes(self, nodelist):
       
  1418 		"""
       
  1419 		Add given nodes to the hypergraph.
       
  1420 		
       
  1421 		@attention: While nodes can be of any type, it's strongly recommended to use only numbers
       
  1422 		and single-line strings as node identifiers if you intend to use write().
       
  1423 
       
  1424 		@type  nodelist: list
       
  1425 		@param nodelist: List of nodes to be added to the graph.
       
  1426 		"""
       
  1427 		for each in nodelist:
       
  1428 			self.add_node(each)
       
  1429 
       
  1430 
       
  1431 	def add_hyperedge(self, hyperedge):
       
  1432 		"""
       
  1433 		Add given hyperedge to the hypergraph.
       
  1434 
       
  1435 		@attention: While hyperedge-nodes can be of any type, it's strongly recommended to use only
       
  1436 		numbers and single-line strings as node identifiers if you intend to use write().
       
  1437 		
       
  1438 		@type  hyperedge: hyperedge
       
  1439 		@param hyperedge: Hyperedge identifier.
       
  1440 		"""
       
  1441 		if (not hyperedge in self.edge_links):
       
  1442 			self.edge_links[hyperedge] = []
       
  1443 			self.graph.add_node((hyperedge,'h'))
       
  1444 
       
  1445 
       
  1446 	def add_hyperedges(self, edgelist):
       
  1447 		"""
       
  1448 		Add given hyperedges to the hypergraph.
       
  1449 
       
  1450 		@attention: While hyperedge-nodes can be of any type, it's strongly recommended to use only
       
  1451 		numbers and single-line strings as node identifiers if you intend to use write().
       
  1452 		
       
  1453 		@type  edgelist: list
       
  1454 		@param edgelist: List of hyperedge-nodes to be added to the graph.
       
  1455 		"""
       
  1456 		for each in edgelist:
       
  1457 			self.add_hyperedge(each)
       
  1458 
       
  1459 
       
  1460 	def link(self, node, hyperedge):
       
  1461 		"""
       
  1462 		Link given node and hyperedge.
       
  1463 
       
  1464 		@type  node: node
       
  1465 		@param node: Node.
       
  1466 
       
  1467 		@type  hyperedge: node
       
  1468 		@param hyperedge: Hyperedge.
       
  1469 		"""
       
  1470 		if (hyperedge not in self.node_links[node]):
       
  1471 			self.node_links[node].append(hyperedge)
       
  1472 			self.edge_links[hyperedge].append(node)
       
  1473 			self.graph.add_edge((node,'n'), (hyperedge,'h'))
       
  1474 
       
  1475 
       
  1476 	def unlink(self, node, hyperedge):
       
  1477 		"""
       
  1478 		Unlink given node and hyperedge.
       
  1479 
       
  1480 		@type  node: node
       
  1481 		@param node: Node.
       
  1482 
       
  1483 		@type  hyperedge: hyperedge
       
  1484 		@param hyperedge: Hyperedge.
       
  1485 		"""
       
  1486 		self.node_links[node].remove(hyperedge)
       
  1487 		self.edge_links[hyperedge].remove(node)
       
  1488 
       
  1489 
       
  1490 	def accessibility(self):
       
  1491 		"""
       
  1492 		Accessibility matrix (transitive closure).
       
  1493 
       
  1494 		@rtype:  dictionary
       
  1495 		@return: Accessibility information for each node.
       
  1496 		"""
       
  1497 		access_ = accessibility.accessibility(self.graph)
       
  1498 		access = {}
       
  1499 		
       
  1500 		for each in access_.keys():
       
  1501 			if (each[1] == 'n'):
       
  1502 				access[each[0]] = []
       
  1503 				for other in access_[each]:
       
  1504 					if (other[1] == 'n'):
       
  1505 						access[each[0]].append(other[0])
       
  1506 		
       
  1507 		return access
       
  1508 
       
  1509 	
       
  1510 	def connected_components(self):
       
  1511 		"""
       
  1512 		Connected components.
       
  1513 
       
  1514 		@rtype:  dictionary
       
  1515 		@return: Pairing that associates each node to its connected component.
       
  1516 		"""
       
  1517 		components_ = accessibility.connected_components(self.graph)
       
  1518 		components = {}
       
  1519 		
       
  1520 		for each in components_.keys():
       
  1521 			if (each[1] == 'n'):
       
  1522 				components[each[0]] = components_[each]
       
  1523 		
       
  1524 		return components
       
  1525 
       
  1526 	
       
  1527 	def cut_nodes(self):
       
  1528 		"""
       
  1529 		Return the cut-nodes of the given hypergraph.
       
  1530 		
       
  1531 		@rtype:  list
       
  1532 		@return: List of cut-nodes.
       
  1533 		"""
       
  1534 		cut_nodes_ = accessibility.cut_nodes(self.graph)
       
  1535 		cut_nodes = []
       
  1536 		
       
  1537 		for each in cut_nodes_:
       
  1538 			if (each[1] == 'n'):
       
  1539 				cut_nodes.append(each[0])
       
  1540 		
       
  1541 		return cut_nodes
       
  1542 
       
  1543 
       
  1544 	def cut_hyperedges(self):
       
  1545 		"""
       
  1546 		Return the cut-hyperedges of the given hypergraph.
       
  1547 		
       
  1548 		@rtype:  list
       
  1549 		@return: List of cut-nodes.
       
  1550 		"""
       
  1551 		cut_nodes_ = accessibility.cut_nodes(self.graph)
       
  1552 		cut_nodes = []
       
  1553 		
       
  1554 		for each in cut_nodes_:
       
  1555 			if (each[1] == 'h'):
       
  1556 				cut_nodes.append(each[0])
       
  1557 		
       
  1558 		return cut_nodes
       
  1559 		
       
  1560 	def rank(self):
       
  1561 		"""
       
  1562 		Return the rank of the given hypergraph.
       
  1563 		
       
  1564 		@rtype:  int
       
  1565 		@return: Rank of graph.
       
  1566 		"""
       
  1567 		max_rank = 0
       
  1568 		
       
  1569 		for each in hyperedges:
       
  1570 			if len(each) > max_rank:
       
  1571 				max_rank = len(each)
       
  1572 				
       
  1573 		return max_rank