# 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