np_drawutil.py

该软件根据网络数据生成NetFlow记录。NetFlow可用于网络规划、负载均衡、安全监控等

###############################################################################
#                                                                             #
#   Copyright 2005 University of Cambridge Computer Laboratory.               #
#                                                                             #
#   This file is part of Nprobe.                                              #
#                                                                             #
#   Nprobe is free software; you can redistribute it and/or modify            #
#   it under the terms of the GNU General Public License as published by      #
#   the Free Software Foundation; either version 2 of the License, or         #
#   (at your option) any later version.                                       #
#                                                                             #
#   Nprobe is distributed in the hope that it will be useful,                 #
#   but WITHOUT ANY WARRANTY; without even the implied warranty of            #
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             #
#   GNU General Public License for more details.                              #
#                                                                             #
#   You should have received a copy of the GNU General Public License         #
#   along with Nprobe; if not, write to the Free Software                     #
#   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA #
#                                                                             #
###############################################################################


##############################################################################
##############################################################################
#
# Graph drawing utilities, etc
#
##############################################################################
##############################################################################

#
# Exceptions
#

class Nodraw: ## Raised by endpoints

    pass

##############################################################################

class NotInRange:
    pass
 

##############################################################################
##############################################################################



#
# Courtesy of Sedgewick
#


def ccw(x0, y0, x1, y1, x2, y2):

    # longs - o'wise sometimes o'flow
    dx1 = long(x1-x0)
    dy1 = long(y1-y0)
    dx2 = long(x2-x0)
    dy2 = long(y2-y0)

    if dx1*dy2 > dy1*dx2:
	return 1
    if dx1*dy2 < dy1*dx2:
	return -1
    if dx1*dx2 < 0 or dy1*dy2 < 0:
	return -1
    if dx1*dx1 + dy1*dy1 < dx2*dx2 + dy2*dy2:
	return 1

    return 0

##############################################################################

#
# Do two lines intersect?
# Courtesy of Sedgewick
#

def intersect(x1, y1, x2, y2, x3, y3, x4, y4):

    return ((ccw(x1, y1, x2, y2, x3, y3)*ccw(x1, y1, x2, y2, x4, y4) <= 0) and (ccw(x3, y3, x4, y4, x1, y1)*ccw(x3, y3, x4, y4, x2, y2) <=0))

##############################################################################

def inside(x, y, bounds):

    return (bounds[0] <= x <= bounds[1] and bounds[2] <= y <= bounds[3]) 

##############################################################################

#
# Interpolate the x coord of a line crossing a horizontal
#


def interpx_l(x1, y1, x2, y2, cut):

    if x1 == x2:
	return x1

    a = long(y1-cut)
    b = long(x2-x1)
    c = long(y1-y2)
    x = int((a*b)/c) + x1

    return x 
	
###############################################################################


def interpy_l(x1, y1, x2, y2, cut):

    #print '(%d,%d), (%d,%d) %d' % (x1, y1, x2, y2, cut)

    if y2 == y1:
	return y1

    if x2 == x1:
	raise Nodraw

    a = long(x2-cut)
    b = long(y1-y2)
    c = long(x2-x1)
    if c:
	y = int((a*b)/c) + y2
    else:
	y = y2

    return y  
	
##############################################################################

#
# Extent of coincidence of two lines
# 

def coincident(a1, a2, b1, b2):

    e = []

    if b1 <= a1 <= b2:
	e.append(a1)
    elif abs(a1 - b1) > abs(a1 - b2):
	e.append(b2)
    else:
	e.append(b1)

    if b1 <= a2 <= b2:
	e.append(a2)
    elif abs(a2 - b1) > abs(a2 - b2):
	e.append(b2)
    else:
	e.append(b1)

    return (e[0], e[1])
	
##############################################################################

#
# Return the points delimiting the part of a line which appears within a 
#  horizontal rectangle given by bounds
# 

def endpoints(x0, y0, x1, y1, bounds):

    xl = bounds[0]
    xr = bounds[1]
    yt = bounds[2]
    yb = bounds[3]

    if x0 == xl == x1 or x0 == xr == x1:
	yy1, yy2 = coincident(y0, y1, yt, yb)
	return(x1, yy1, x1, yy2)

    elif y0 == yt == y1 or y0 == yb == y1:
	xx1, xx2 = coincident(x0, x1, xl, xr)
	return(xx1, y1, xx2, y1)

    elif inside(x0, y0, bounds):
	if inside(x1, y1, bounds):
	    return (x0, y0, x1, y1)
	if intersect(x0, y0, x1, y1, xl, yt, xl, yb):
	    return (x0, y0, xl, interpy_l(x0, y0, x1, y1, xl))
	elif intersect(x0, y0, x1, y1, xr, yt, xr, yb):
	    return (x0, y0, xr, interpy_l(x0, y0, x1, y1, xr))
	elif intersect(x0, y0, x1, y1, xr, yt, xl, yt):
	    return (x0, y0, interpx_l(x0, y0, x1, y1, yt), yt)
	elif intersect(x0, y0, x1, y1, xr, yb, xl, yb):
	    return (x0, y0, interpx_l(x0, y0, x1, y1, yb), yb)
    elif inside(x1, y1, bounds):
	if intersect(x0, y0, x1, y1, xl, yt, xl, yb):
	    return (x1, y1, xl, interpy_l(x0, y0, x1, y1, xl))
	elif intersect(x0, y0, x1, y1, xr, yt, xr, yb):
	    return (x1, y1, xr, interpy_l(x0, y0, x1, y1, xr))
	elif intersect(x0, y0, x1, y1, xr, yt, xl, yt):
	    return (x1, y1, interpx_l(x0, y0, x1, y1, yt), yt)
	elif intersect(x0, y0, x1, y1, xr, yb, xl, yb):
	    return (x1, y1, interpx_l(x0, y0, x1, y1, yb), yb)
    else:
	inters = []
	if intersect(x0, y0, x1, y1, xl, yt, xl, yb):
	    inters.append((xl, interpy_l(x0, y0, x1, y1, xl)))
	if intersect(x0, y0, x1, y1, xr, yt, xr, yb):
	    inters.append((xr, interpy_l(x0, y0, x1, y1, xr)))
	if intersect(x0, y0, x1, y1, xr, yt, xl, yt):
	    inters.append((interpx_l(x0, y0, x1, y1, yt), yt))
	if intersect(x0, y0, x1, y1, xr, yb, xl, yb):
	    inters.append((interpx_l(x0, y0, x1, y1, yb), yb))

	if len(inters):
	    return (inters[0][0], inters[0][1], inters[1][0], inters[1][1])
	else:
	    raise Nodraw


##############################################################################

P_BEFORE = 0
P_AFTER = 1

#
# In data list find point before/after the given independant variable value
#

def find_point(val, data, i1, i2, where):

    l = i1
    r = i2

    #print data

    if i1 == None:
	raise NotInRange

    if i1 == i2:
	# single point
	if val != data[i1][0]:
	    raise NotInRange
	else:
	    return i1

    while r > l:
	p = (l+r)/2
	#print 'l=%d r=%d p=%d' % (l, r, p)
	x = data[p][0]
	if val < x:
	    r = p
	else:
	    l = p
	if r - l == 1:
	    if data[r][0] < val or val < data[l][0]:
		raise NotInRange
	    if where == P_AFTER:
		if data[l][0] <= val <= data[r][0]:
		    if data[l][0] <= val < data[r][0]:
			return r
		    else:
			return min([i2, r+1])
	    elif where == P_BEFORE:
		if data[l][0] <= val <= data[r][0]:
		    if data[l][0] < val <= data[r][0]:
			return l
		    else:
			return max([l-1, i1])
		
############################################################################

#
# Conversions for data set field values
#

def field_l2str(fl):

    if not fl:
        return ''

    s = fl[0]
    for f in fl[1:]:
        s += ':%s' % (f)

    return s

def field_str2l(s):

    return [fl for fl in s.replace(' ', '').split(':')]

def fields_eq(l1, l2):

    if len(l1) != len(l2):
        return 0
         
    for i in range(len(l1)):
        if l1[i] != l2[i]:
            return 0
    return 1
		
############################################################################