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 defines an edge
GraphDistance Defines a graph to compute a distance 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__ constructor
__init__ constructor
__init__ constructor
__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)[source]

Bases : object

defines an edge

source on GitHub

constructor

Paramètres:
  • from – (int)
  • to – (int)
  • label – (str)
  • weight – (float)

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

source on GitHub

Label

returns the label

source on GitHub

__init__(from_, to, label, weight)[source]

constructor

Paramètres:
  • from – (int)
  • to – (int)
  • label – (str)
  • weight – (float)

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

source on GitHub

__repr__()[source]

usual

source on GitHub

__str__()[source]

usual

source on GitHub

is_edge()[source]

returns True

source on GitHub

is_vertex()[source]

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

Bases : object

Defines a graph to compute a distance 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)[source]

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

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__()[source]

usual

source on GitHub

__str__()[source]

usual

source on GitHub

_private__init__(add_loop, weight_vertex, weight_edge)[source]
_private_string_path_matching(path, skipEdge=False)[source]
compute_predecessor()[source]

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

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

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
Renvoie:

2-uple: distance, aligned path

source on GitHub

get_matching_functions(function_mach_vertices, function_match_edges, cost=False)[source]

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

loads a graph from a file

Paramètres:

source on GitHub

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

Bases : object

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

Label

returns the label

source on GitHub

__init__(nb, label, weight)[source]

constructor

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

@para weight (float)

source on GitHub

__repr__()[source]

usual

source on GitHub

__str__()[source]

usual

source on GitHub

is_edge()[source]

returns False

source on GitHub

is_vertex()[source]

returns True

source on GitHub