L-graph-system 0.1.1

A package to work with L-graphs

This is an universal l-graph system. It shall be my pleasure if you use it in your projects.

Contents

This project includes 3 main modules, each containing it's named class. The main module is lgraph.py, which provides us with an access to LGraph class and save and load operations.

LGraph

The main class. To make a proper L-graph, you should make an object of it.

Properties

vertexes:{vertex_name:String :: vertex:Vertex}

arcs:{arc_key:String :: arc:Arc}

start_vertexes:set(vertex_name:String)

finish_vertexes:set(vertex_name)

brackets:((open:String,close:String),(open2:String, close2:String))

Methods

add_arc(start_vertex:String, finish_vertex:String, label:String, bracket_label:String, key='':String) This method allows us to add a new arc to the graph with corresponding values. If one of the vertexes does not exist in the graph, it will create a new one.

add_vertex(vertex_name:String) This method creates a new vertex in the graph

remove(arc_name:String) This method removes selected arc from the graph and it's components

remove(vertex_name:String) This method removes selected vertex and all arcs it was bind to

set_start(vertex_name:String) Adds the selected vertex to the starting vertexes

set_finish(vertex_name:String) Adds the selected vertex to the finish vertexes

remove_start(arc_name:String) Removes the selected vertex from starting vertexes

remove_finish(vertex_name:String) Removes the selected vertex from finish vertexes

set_brackets(brackets:((),())) Allows to use another set of brackets. Must be special type.

solve(string:String,vertex_path=False,arc_path=False) Returns True or False whether string belongs to the language of the L-graph, or not. If vertex_vath is set to True, returns correct label path as list or empty list if string does not belog to the language. Arc_path does the same thing with path of arcs instead of vertexes.

cycles():list(list(vertex_name:String)) Searches for cylces in the graph. Returns a list of lists, each containing vertexes from the corresponding cycle.

arc_cycles():list(list(arc_key:String)) Does the same thing as cycles(), but returns arcs.

generate_from_grammar(in_grammar:list(grammar_rule:String)) Must be used with empty L-graph. Builds L-graph which represents language, equivalent to the language of the grammar.

type_def():String Returns 'regular', 'context-free' or 'recursively_enumerable' depending on L-graph class.

is_regular():Boolean True if L-graph is regular

is_context_free():Boolean True if L-graph is context-free

core(paired_number, neutral_number):list(list(vertex_name:String)) Returns list of successful paths with restricted number of cycles.

merge(another_graph:LGraph) Restructurises the graph to represent 2 L-graphs in 1.

dead_ends():list(vertex_names:String) Returns a set of vertexes, from which no finish vertexes can be reached.

unattainable():list(vertex_names:String) Returns a set of vertexes, which can not be reached from start vertexes.

remove_unusable() Removes all vertexes present in dead ends and unattainable sets.

reduction() Restructurises L-graph to be more compact.

Vertex

class of graph vertexes

Properties

name:String

out_arcs:set()

in_arcs:set()

Methods:

rename(new_name:String)

Arc

class of graph arcs

Properties

key:String

label:String

brackets:String

start:Vertex

end:Vertex

next_arcs:set(String)

Methods:

remove_arc()

set_label(new_label:String)

set_brackets(new_brackets:String)