mlstatpy.graph.graph_distance

class mlstatpy.graph.graph_distance.Edge(from_, to, label, weight)

Defines an edge of a graph.

property Label

returns the label

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)

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 []

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)

Computes an alignment between two graphs.

Paramètres:

• graph2 – the other graph

• function_mach_vertices – function which gives a distance between 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 the matching was operated

• use_min – @see me edit_distance_path

• weight_vertex – a weight for every vertex

• weight_edge – a weight for every edge

• verbose – display some progress with tqdm

Renvoie:

2 tuple (a distance, a graph containing the aligned paths between the two graphs)

See Distance between 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 filename file name @param add_loop @see me __init__

class mlstatpy.graph.graph_distance.Vertex(nb, label, weight)

Defines a vertex of a graph.

property Label

returns the label

is_edge()

returns False

is_vertex()

returns True