weighted subgraph isomorphism

Question

I've been searching this all over the internet for about two or three consecutive days, but no luck so far.

I know that there are lots of libraries and implementation for subgraph isomorphism in the wild, but they all work for unweighted graphs. For instance, two of the most prevalent algorithms are VF2 and Uleman's algorithm. Here, my question is: Are there any methods that given a graph (G) and a query graph (g), can one find whether g is a subgraph (and isomorphic) to G or not? (Please note that the following is the edge list representation of the graphs.)

G
1 2 c
1 3 d
1 4 c
2 3 a
...
g
1 3 d
2 3 a

In this case, g is a subgraph and is isomorphic to G, but if we have something like this:

g
1 3 t
2 3 a

Now g is no longer a subgraph of G and is not isomorphic.

UPDATE: Both graphs are undirected.

Answer 1

g={(1 2 a)} is not isomorphic to G, since the weight of this edge in G is "c" not "a".

This is weird. Simply put, graphs G, G' (actually, any algebraic structures) are isomorphic if there exists some function f from {G<->G'} so that for any relation R(g1, g2) (g1, g2 in G), R'(f(g1), f(g2)) also holds for G' and vice versa. So any graph G' gained from G by renaming (permutation) of vertexes is isomorphic to G.

As it seems, you are instead interested in figuring out whether for any marked edge of g there exists edge connecting the same vertexes and bearing the same mark in G. Most simple way to do this is duplicating edges of G and sorting them by component. Then for each edge of query g it will take O(log(|G|)) to check whether G has the same edge (and it has the same mark). Thus, total time is O(|G|*log(|G|)) to prepare graph G and O(|g|*log(|G|)) to process each subsequent query.

Upd: By "sorting edges of G by component" I meant the following: build an array (or binary tree) of edges, sorted by first vertex then by second vertex. To search for an edge easily, it should be duplicated. For example, edge (1, 2, c) should be present as (1, 2, c) and (2, 1, c). So that, in array form, G from example above becomes

(1, 2, c)
(1, 3, d)
(1, 4, c)
(2, 1, c)
(2, 3, a)
(3, 1, d)
(3, 2, a)
(4, 1, c)

On the afterthought, it may be better to write both edges of G and g with vertex with lesser number first - this way, no duplication is needed.