network = cluster is create, connections, nodes, delete, copy, neighbors, unparse % Overview: A network is a set of nodes and a set of connections, % or "wires" between those nodes. node = record[node_id: string, links: array[int]] rep = array[node] tab = '\t' space = ' ' hash = '#' comment = '%' create = proc(net: stream) returns(cvt) signals(net_error(string, int)) % effects: Takes in a stream in the format describe below % and returns a network from that stream. If the given % stream is not in the appropriate formant, the procedure % signals net_error and returns an error message along with % the line number in the original file that caused the error. % % The stream must be in the following format % The nodes are listed first, each seperated by whitespace % (any number of space, tab or newline characters.) % Duplicate nodes are ignored. Then % a special hash character (#) is used at the beginning of % a line to seperate the nodes from the wires % (the rest of the line is ignored). % Each wire is described by two nodes, seperated % by a space, on a line by itself. A line beginning % with a percent sign is a comment. Blank lines are % ignored. All nodes listed in the % wires section must be listed in the nodes section first. % Lines that do not adhere to this structure % (aside from extra whitespaces) are ignored, a % message is sent to primary_output indicating the % line number, and evaluation of the network continues % with the next line. (Lines with extra whitespaces are % parsed as usual with the exception of a line who's first % non-whitespace is '%' in which case, the words are % treated as nodes.) Signal % net_error(string, int) when an unrecoverable error is found % in net. String is an explanation of the error and int is % the line number. % % modifies: net n : rep := rep$new() % parse nodes temp: array[string] := array[string]$new() size: int:= 0 line: int:= 0 newword: bool c: char := comment l: string while true do l := stream$getl(net) newword := true line := line + 1 if l[1] = hash then break end except when bounds: continue end if l[1] = comment then continue end for c in string$chars(l) do if c = space cor c = tab then newword := true continue end if newword then newword := false size := size + 1 array[string]$addh(temp, "") end temp[size] := string$append(temp[size], c) end end except when end_of_file: signal net_error("Missing hash mark", line) end duplicate : bool tmp: array[int] := array[int]$new() for count: int in int$from_to(1, size) do duplicate := false for search: int in int$from_to(1, count - 1) do duplicate := duplicate cor string$equal(temp[count], temp[search]) end if ~duplicate then rep$addh(n, node${node_id: temp[count], links: tmp}) else size := size - 1 end end for count: int in int$from_to(1, size) do node$set_links(n[count], array[int]$fill(1, size, 0)) end % parse wires while true do l := stream$getl(net) line:= line + 1 if l[1] = comment then continue end except when bounds: continue end temp5: array[string]:= array[string]$new() array[string]$addh(temp5, "") i: int:= 1 for c2: char in string$chars(l) do if c2 = tab cor c2 = space then if ~string$empty(temp5[i]) then i:=i + 1 array[string]$addh(temp5, "") end else temp5[i]:=string$concat(temp5[i], string$c2s(c2)) end end if string$empty(temp5[i]) then array[string]$remh(temp5) i:=i - 1 end if i > 2 then error("Wires section --> too many nodes", line) continue end if i < 2 then if i = 0 then continue end error("Wires section --> too few nodes", line) continue end node1: int := index(n, temp5[1]) except when no_node: error("Undefined node '" || temp5[1] || "' in wires section", line) continue end node2: int := index(n, temp5[2]) except when no_node: error("Undefined node '" || temp5[2] || "' in wires section", line) continue end lks: array[int] := node$get_links(n[node1]) lks[node2] := lks[node2]+1 lks := node$get_links(n[node2]) lks[node1] := lks[node1] + 1 end except when end_of_file: end return(n) end create connections = proc(net: cvt, node1, node2: string) returns(int) signals(no_node(string), same_node) % effects: Takes in two nodes and returns the number of % connections between them. Signals no_node(name of node) % if one or both of the nodes does not exist. Signals % same_node if node1 and node2 specify the same node. if string$equal(node1, node2) then signal same_node end n1: int := index(net, node1) except when no_node: signal no_node(node$get_node_id(net[n1])) end n2: int := index(net, node2) except when no_node: signal no_node(node$get_node_id(net[n2])) end cs: array[int] := node$get_links(net[n1]) return(cs[n2]) end connections index = proc(net: rep, name: string) returns(int) signals(no_node) % effects: returns the index of the node associated with "name" i: int := rep$low(net) top: int := rep$high(net) while i <= top do if string$equal(node$get_node_id(net[i]), name) then return(i) end i := i + 1 end signal no_node end index unparse = proc(net: cvt) returns(string) % effects: Unparses a network. Intended for use as a debugging tool % only. i: int :=1 top: int := rep$high(net) s: string:=("\n") while i <= top do current: array[int] := node$get_links(net[i]) s:= string$concat(s, "Node: " || node$get_node_id(net[i]) || "\n") for second: int in int$from_to (1, top) do s:= string$concat(s, node$get_node_id(net[second]) || " " || int$unparse(current[second]) || "\n") end i:=i + 1 s:= string$concat(s, "\n") end return(s) end unparse nodes = iter(net: cvt) yields(string) % effects: Yields all the nodes in net exactly once. for nd: node in rep$elements(net) do yield(node$get_node_id(nd)) end end nodes delete = proc(net: cvt, node1, node2: string) signals(no_node(string), no_connection) % effects: Removes the connection between node1 and node2 in % net. Signals no_node(string) if either of the nodes % are not in the network, where string is the name of the node % Signals no_connection if the nodes are not % connected. % modifieds: net if connections(up(net), node1, node2) = 0 then signal no_connection end resignal no_node n1: int := index(net, node1) n2: int := index(net, node2) l1: array[int] := node$get_links(net[n1]) l1[n2] := l1[n2] - 1 l2: array[int] := node$get_links(net[n2]) l2[n1] := l2[n1] - 1 return end delete copy = proc(net: cvt) returns(cvt) % effects: Returns a new network which is equivalent to net. return(rep$copy(net)) end copy neighbors = iter(net: cvt, name: string) yields(string) signals(no_node(string)) % effects: returns all the nodes in net connected to node % exactly once. for nd: string in nodes(up(net)) do if network$connections(up(net), name, nd) > 0 then yield(nd) end except when same_node: continue end end resignal no_node end neighbors error = proc(m: string, line: int) % effects: Prints error message "m" to error_output and indicates % the line number of the error. stream$putl(stream$error_output(), "Network error: " || m) stream$putl(stream$error_output(), " Line: " || int$unparse(line)) stream$putl(stream$error_output(), " Continuing parsing at line " || int$unparse(line + 1)) end error end network