Hi Tamas,
I tried the ways as you suggested. It works. However, the speed is a
bottleneck. So I come out a method to avoid checking motifs for my case.
The oncoming questions are: what is the most efficient way to find the
incident edges of the current edge?
Here is my solution:
CurrentEdgeId <- get.edge.ids( g_OriginGraph, motif_current ) #
motif_current is just an edge
IncidentEdges <- incident_edges( g_OriginGraph, motif_current )
IncidentEdgeIds <- unlist( IncidentEdges )
IncidentEdgeIds = IncidentEdgeIds[ IncidentEdgeIds != CurrentEdgeId ]
The above code can give the neighboring edges of the current edge. However,
it is much slower than directly indexing the edge list of the graph:
Edges <- as_edgelist( g_OriginGraph, FALSE )
Motifs_left <- rbind( Edges[Edges[,1] == motif_current[1],],
Edges[Edges[,2] == motif_current[1],] )
Motifs_right <- rbind( Edges[Edges[,1] == motif_current[2],],
Edges[Edges[,2] == motif_current[2],] )
NeighborMotifs <- rbind(Motifs_left, Motifs_right)
idx <- which( NeighborMotifs[,1] == motif_current[1] &
NeighborMotifs[,2] == motif_current[2] )
NeighborMotifs <- NeighborMotifs[-idx,]
So I am wondering if there is some other functions from igraph to get the
edges very fast.
Thanks a lot.
Cheers,
Phil
___________________________________________________________
Phil Hengjun Cui
Drexel University | Electrical and Computer Engineering
Philadelphia, USA
___________________________________________________________
On Thu, Aug 6, 2015 at 5:24 PM, Tamas Nepusz <[email protected]> wrote:
> On 08/04, Phil Cui wrote:
> > (1) it gives motifs including those are the same type as g1 and also
> those are
> > different types from g1 according to the result from
> > isomorphism_class;
> It could be the case that the issue is that you *expected* igraph to do
> an induced subgraph isomorphism search. For instance, consider the
> following
> pattern graph:
>
> A --> B --> C
>
> and the following target graph in which the pattern is being searched:
>
> a --> b --> c --> a
>
> igraph will happily return the mapping A=a, B=b, C=c as well as A=b, B=c,
> C=a
> and A=c, B=a, C=b because the edges A --> B and B --> C can be mapped to
> some
> edges of the target graph and the subgraph isomorphism algorithm does not
> aim
> to map _nonexistent_ connections of the pattern graph to _nonexistent_
> connections of the target graph. If you want to ensure that missing
> connections
> between a pair of vertices in the pattern graph are mapped to missing
> connections in the target graph, you need to use *induced* subgraph
> isomorphism search.
>
> subgraph_isomorphisms() in the R interface of igraph actually uses one of
> two
> algorithms behind the scenes: VF2 or LAD. The LAD algorithm supports
> induced
> subgraph isomorphisms, while VF2 does not, so if you want to search for
> induced subgraph isomorphisms, you need to call subgraph_isomorphisms with
> method="lad" and induced=T.
>
> > (2) there are many duplicated combinations of nodes which relates to
> > the same motif;
> It can probably happen if the motif is isomorphic to itself -- in such
> cases,
> multiple mappings may exist between the pattern and the target graph such
> that
> the same nodes of the target graph are mappend to the pattern but in
> different
> order.
>
> > (3) the result provided is based on the vertex name, but I prefer vertex
> id.
> > I tried unlist to get the ids, however, that will combine all
> > everything together.
> Just erase the vertex names temporarily before performing the search and
> add
> them back later. (There could be a better solution for the problem in the
> R interface but I'm not too familiar with R).
>
> All the best,
> T.
>
> _______________________________________________
> igraph-help mailing list
> [email protected]
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
