module graph.graph_distance#

Inheritance diagram of mlstatpy.graph.graph_distance

Short summary#

module mlstatpy.graph.graph_distance

First approach for a edit distance between two graphs.

See Distance between two graphs.

source on GitHub

Classes#

class

truncated documentation

_Edge

_Vertex

Edge

Defines an edge of a graph.

GraphDistance

Defines a graph to compute a distance between two graphs.

Vertex

Defines a vertex of a graph.

Properties#

property

truncated documentation

Label

returns the label

Label

returns the label

Static Methods#

staticmethod

truncated documentation

get_list_of_vertices

load_from_file

loads a graph from a file

Methods#

method

truncated documentation

__getitem__

returns a vertex or an edge if no vertex with the given index was found

__init__

__init__

constructor

__init__

constructor

__init__

__init__

__repr__

usual

__repr__

usual

__repr__

usual

__str__

usual

__str__

usual

__str__

usual

_private__init__

_private_string_path_matching

clean_dead_ends

common_paths

compute_predecessor

usual

compute_successor

connect_root_and_leave

distance_matching_graphs_paths

Computes an alignment between two graphs.

draw_vertices_edges

edit_distance_path

Tries to align two paths from two graphs.

enumerate_all_paths

get_matching_functions

returns default matching functions between two vertices and two edges

get_order_vertices

is_edge

returns True

is_edge

returns False

is_vertex

returns False

is_vertex

returns True

private_count_left_right

private_kruskal_matrix

Documentation#

First approach for a edit distance between two graphs.

See Distance between two graphs.

source on GitHub

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

Bases : _Edge

Defines an edge of a graph.

source on GitHub

Paramètres:
  • from – (int)

  • to – (int)

  • label – (str)

  • weight – (float)

'00' means the beginning of a graph, '11' the end.

source on GitHub

property Label#

returns the label

source on GitHub

__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.

source on GitHub

__repr__()#

usual

source on GitHub

__str__()#

usual

source on GitHub

is_edge()#

returns True

source on GitHub

is_vertex()#

returns False

source on GitHub

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

source on GitHub

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

source on GitHub

__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

source on GitHub

__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

source on GitHub

__repr__()#

usual

source on GitHub

__str__()#

usual

source on GitHub

_private__init__(add_loop, weight_vertex, weight_edge)#
_private_string_path_matching(path, skipEdge=False)#
compute_predecessor()#

usual

source on GitHub

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_minedit_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)

See Distance between two graphs.

source on GitHub

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

source on GitHub

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

source on GitHub

static load_from_file(filename, add_loop)#

loads a graph from a file

Paramètres:

source on GitHub

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

Bases : _Vertex

Defines a vertex of a graph.

source on GitHub

constructor

Paramètres:
  • nb – (int) index of the vertex

  • label – (str) label

@para weight (float)

source on GitHub

property Label#

returns the label

source on GitHub

__init__(nb, label, weight)#

constructor

Paramètres:
  • nb – (int) index of the vertex

  • label – (str) label

@para weight (float)

source on GitHub

__repr__()#

usual

source on GitHub

__str__()#

usual

source on GitHub

is_edge()#

returns False

source on GitHub

is_vertex()#

returns True

source on GitHub

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

Bases : object

__init__(from_, to, label, weight)#
__slots__ = ('from_', 'to', 'label', 'weight', 'nb')#
class mlstatpy.graph.graph_distance._Vertex(nb, label, weight)#

Bases : object

__init__(nb, label, weight)#
__slots__ = ('nb', 'label', 'weight')#