Source code for libpgm.graphskeleton

# Copyright (c) 2012, CyberPoint International, LLC
# All rights reserved.
# 
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
#     * Redistributions of source code must retain the above copyright
#       notice, this list of conditions and the following disclaimer.
#     * Redistributions in binary form must reproduce the above copyright
#       notice, this list of conditions and the following disclaimer in the
#       documentation and/or other materials provided with the distribution.
#     * Neither the name of the CyberPoint International, LLC nor the
#       names of its contributors may be used to endorse or promote products
#       derived from this software without specific prior written permission.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL CYBERPOINT INTERNATIONAL, LLC BE LIABLE FOR ANY
# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
'''
This module provides tools for creating and using graph skeletons for Bayesian networks. A graph skeleton in this case is a vertex set and a directed edge set, with no further information about the specific nodes. 

'''
from dictionary import Dictionary

import sys

[docs]class GraphSkeleton(Dictionary): ''' This class represents a graph skeleton, meaning a vertex set and a directed edge set. It contains the attributes *V* and *E*, and the methods *load*, *getparents*, *getchildren*, and *toporder*. ''' def __init__(self): self.V = None '''A list of names of vertices.''' self.E = None '''A list of [origin, destination] pairs of vertices that constitute edges.''' self.alldata = None '''(Inherited from dictionary) A variable that stores a key-indexable dictionary once it is loaded from a file.'''
[docs] def load(self, path): ''' Load the graph skeleton from a text file located at *path*. Text file must be a plaintext .txt file with a JSON-style representation of a dict. Dict must contain the top-level keys "V" and "E" with the following formats:: { 'V': ['<vertex_name_1>', ... , '<vertex_name_n'], 'E': [['vertex_of_origin', 'vertex_of_destination'], ... ] } Arguments: 1. *path* -- The path to the file containing input data (e.g., "mydictionary.txt"). Attributes modified: 1. *V* -- The set of vertices. 2. *E* -- The set of edges. ''' self.dictload(path) self.V = self.alldata["V"] self.E = self.alldata["E"] # free unused memory del self.alldata
[docs] def getparents(self, vertex): ''' Return the parents of *vertex* in the graph skeleton. Arguments: 1. *vertex* -- The name of the vertex whose parents the function finds. Returns: A list containing the names of the parents of the vertex. ''' assert (vertex in self.V), "The graph skeleton does not contain this vertex." parents = [] for pair in self.E: if (pair[1] == vertex): parents.append(pair[0]) return parents
[docs] def getchildren(self, vertex): ''' Return the children of *vertex* in the graph skeleton. Arguments: 1. *vertex* -- The name of the vertex whose children the function finds. Returns: A list containing the names of the children of the vertex. ''' assert (vertex in self.V), "The graph skeleton does not contain this vertex." children = [] for pair in self.E: if (pair[0] == vertex): children.append(pair[1]) return children
[docs] def toporder(self): ''' Modify the vertices of the graph skeleton such that they are in topological order. A topological order is an order of vertices such that if there is an edge from *u* to *v*, *u* appears before *v* in the ordering. It works only for directed ayclic graphs. Attributes modified: 1. *V* -- The names of the vertices are put in topological order. The function also checks for cycles in the graph, and returns an error if one is found. ''' Ecopy = [x[:] for x in self.E] roots = [] toporder = [] for vertex in self.V: # find roots if (self.getparents(vertex) == []): roots.append(vertex) while roots != []: n = roots.pop() toporder.append(n) for edge in reversed(Ecopy): if edge[0] == n: m = edge[1] Ecopy.remove(edge) yesparent = False for e in Ecopy: if e[1] == m: yesparent = True break if yesparent == False: roots.append(m) assert (not Ecopy), ("Graph contains a cycle", Ecopy) self.V = toporder