module graph.graph_distance
#
Short summary#
module mlstatpy.graph.graph_distance
First approach for a edit distance between two graphs.
Classes#
class |
truncated documentation |
---|---|
Defines an edge of a graph. |
|
Defines a graph to compute a distance between two graphs. |
|
Defines a vertex of a graph. |
Properties#
property |
truncated documentation |
---|---|
returns the label |
|
returns the label |
Static Methods#
staticmethod |
truncated documentation |
---|---|
|
|
loads a graph from a file |
Methods#
method |
truncated documentation |
---|---|
returns a vertex or an edge if no vertex with the given index was found |
|
constructor |
|
constructor |
|
usual |
|
usual |
|
usual |
|
usual |
|
usual |
|
usual |
|
|
|
|
|
usual |
|
|
|
|
|
Computes an alignment between two graphs. |
|
|
|
Tries to align two paths from two graphs. |
|
|
|
returns default matching functions between two vertices and two edges |
|
|
|
returns True |
|
returns False |
|
returns False |
|
returns True |
|
|
|
|
Documentation#
First approach for a edit distance between two graphs.
See Distance between two graphs.
- class mlstatpy.graph.graph_distance.Edge(from_, to, label, weight)#
Bases :
_Edge
Defines an edge of a graph.
- Paramètres:
from – (int)
to – (int)
label – (str)
weight – (float)
'00'
means the beginning of a graph,'11'
the end.- property Label#
returns the label
- __init__(from_, to, label, weight)#
- Paramètres:
from – (int)
to – (int)
label – (str)
weight – (float)
'00'
means the beginning of a graph,'11'
the end.
- __repr__()#
usual
- __str__()#
usual
- is_edge()#
returns True
- is_vertex()#
returns False
- class mlstatpy.graph.graph_distance.GraphDistance(edge_list, vertex_label=None, add_loop=False, weight_vertex=1.0, weight_edge=1.0)#
Bases :
object
Defines a graph to compute a distance between two graphs.
Compute a distance between two graphs.
See Distance between two graphs.
<<<
import copy from mlstatpy.graph import GraphDistance # We define two graphs as list of edges. graph1 = [("a", "b"), ("b", "c"), ("b", "X"), ("X", "c"), ("c", "d"), ("d", "e"), ("0", "b")] graph2 = [("a", "b"), ("b", "c"), ("b", "X"), ("X", "c"), ("c", "t"), ("t", "d"), ("d", "e"), ("d", "g")] # We convert them into objects GraphDistance. graph1 = GraphDistance(graph1) graph2 = GraphDistance(graph2) distance, graph = graph1.distance_matching_graphs_paths(graph2, use_min=False) print("distance", distance) print("common paths:", graph)
>>>
distance 0.3318250377073907 common paths: 0 X a b c d e 00 11 g t a -> b [] b -> c [] b -> X [] X -> c [] c -> d [] d -> e [] 0 -> b [] 00 -> a [] 00 -> 0 [] e -> 11 [] c -> 2a.t [] 2a.t -> d [] d -> 2a.g [] 2a.g -> 11 []
constructor
- Paramètres:
edge_list – list of edges
add_loop – automatically add a loop on each vertex (an edge from a vertex to itself)
weight_vertex – weight for every vertex
weight_edge – weight for every edge
- __getitem__(index)#
returns a vertex or an edge if no vertex with the given index was found
- Paramètres:
index – id (index) to look for
- Renvoie:
Vertex or Edge
- __init__(edge_list, vertex_label=None, add_loop=False, weight_vertex=1.0, weight_edge=1.0)#
constructor
- Paramètres:
edge_list – list of edges
add_loop – automatically add a loop on each vertex (an edge from a vertex to itself)
weight_vertex – weight for every vertex
weight_edge – weight for every edge
- __repr__()#
usual
- __str__()#
usual
- _private__init__(add_loop, weight_vertex, weight_edge)#
- _private_string_path_matching(path, skipEdge=False)#
- compute_predecessor()#
usual
- distance_matching_graphs_paths(graph2, function_mach_vertices=None, function_match_edges=None, noClean=False, store=None, use_min=True, weight_vertex=1.0, weight_edge=1.0, verbose=0, fLOG=<built-in function print>)#
Computes an alignment between two graphs.
- Paramètres:
graph2 – the other graph
function_mach_vertices – function which gives a distance bewteen two vertices, if None, it take the output of
get_matching_functions
function_match_edges – function which gives a distance bewteen two edges, if None, it take the output of
get_matching_functions
noClean – if True, clean unmatched vertices and edges
store – if None, does nothing, if it is a dictionary, the function will store here various information about how th matching was operated
use_min –
edit_distance_path
weight_vertex – a weight for every vertex
weight_edge – a weight for every edge
verbose – display some progress with :epkg:`tqdm`
fLOG – logging functino
- Renvoie:
2 tuple (a distance, a graph containing the aligned paths between the two graphs)
- edit_distance_path(p1, p2, g1, g2, function_mach_vertices=None, function_match_edges=None, use_min=False, debug=False, cache=None)#
Tries to align two paths from two graphs.
- Paramètres:
p1 – path 1 (from g1)
p2 – path 2 (from g2)
g1 – graph 1
g2 – graph 2
function_mach_vertices – function which gives a distance bewteen two vertices, if None, it take the output of
get_matching_functions
function_match_edges – function which gives a distance bewteen two edges, if None, it take the output of
get_matching_functions
use_min –
the returned is based on a edit distance, if this parameter is True, the returned value will be:
if use_min : n = min (len(p1), len(p2)) d = d*1.0 / n if n > 0 else 0
debug – unused
cache – to cache the costs
- Renvoie:
2-uple: distance, aligned path
- get_matching_functions(function_mach_vertices, function_match_edges, cost=False)#
returns default matching functions between two vertices and two edges
- Paramètres:
function_mach_vertices – if not None, this function is returned, othewise, it returns a new fonction. See below.
function_match_edges – if not None, this function is returned, othewise, it returns a new fonction. See below.
cost – if True, the returned function should return a float, otherwise a boolean
- Renvoie:
a pair of functions
Example for * if cost is False:
lambda v1,v2,g1,g2,w1,w2 : v1.label == v2.label
Example for function_mach_vertices if cost is True:
def tempF1 (v1,v2,g1,g2,w1,w2) : if v1 is not None and not v1.is_vertex() : raise TypeError("should be a vertex") if v2 is not None and not v2.is_vertex() : raise TypeError("should be a vertex") if v1 is None and v2 is None : return 0 elif v1 is None or v2 is None : return v2.weight*w2 if v1 is None else v1.weight*w1 else : return 0 if v1.label == v2.label else 0.5*(v1.weight*w1 + v2.weight*w2)
Example for function_match_edges if cost is False:
lambda e1,e2,g1,g2,w1,w2 : e1.label == e2.label and (e1.from_ != e1.to or e2.from_ != e2.to) and (e1.from_ != self.labelBegin or e1.to != self.labelBegin) and (e1.from_ != self.labelEnd or e1.to != self.labelEnd)
Example if cost is True:
def tempF2 (e1,e2,g1,g2,w1,w2) : if e1 is not None and not e1.is_edge() : raise TypeError("should be an edge") if e2 is not None and not e2.is_edge() : raise TypeError("should be an edge") if e1 is None and e2 is None : return 0 elif e1 is None or e2 is None : return e2.weight*w2 if e1 is None else e1.weight*w1 elif e1.label != e2.label : return 0.5*(e1.weight*w1 + e2.weight*w2) else : lab1 = g1.vertices [e1.from_].label == g2.vertices [e2.from_].label lab2 = g1.vertices [e1.to].label == g2.vertices [e2.to].label if lab1 and lab2 : return 0 else : return e1.weight*w1 + e2.weight*w2
- static load_from_file(filename, add_loop)#
loads a graph from a file
- Paramètres:
filename – file name
add_loop –
__init__()
- class mlstatpy.graph.graph_distance.Vertex(nb, label, weight)#
Bases :
_Vertex
Defines a vertex of a graph.
constructor
- Paramètres:
nb – (int) index of the vertex
label – (str) label
@para weight (float)
- property Label#
returns the label
- __init__(nb, label, weight)#
constructor
- Paramètres:
nb – (int) index of the vertex
label – (str) label
@para weight (float)
- __repr__()#
usual
- __str__()#
usual
- is_edge()#
returns False
- is_vertex()#
returns True