1

I need to write a program which must be able to find all subgraphs of a graph using an algorithm like depth first. The thing is I cannot understand how could I represent a set of nodes with relations like: 

A: A->B A->D A->F
B: B->A B->C 
C: C->B C->D
D: D->C D->A D->F
F: F->A F->D

in a tree so I can use that algorithm. Any sources or explanations are welcome.

Hooked
  • 84,485
  • 43
  • 192
  • 261
Bogdan M.
  • 2,161
  • 6
  • 31
  • 53
  • 2
    You can't represent this as a tree, because there are definitely cycles there. For example: A->D->C->B->A – Thomas Jungblut Apr 03 '13 at 12:32
  • How is your graph given in the first place? Which data structure is used? – UmNyobe Apr 03 '13 at 12:35
  • i have no rules regarding this, i i know i i need using this method to extract all subgraphs from a graph – Bogdan M. Apr 03 '13 at 12:49
  • Just out of curiosity: what kind of subgraphs are you looking for? Induced ones or just generally subgraphs? – G. Bach Apr 03 '13 at 14:03
  • 1
    It might be worth noting that finding all complete subgraphs ('cliques') is a known NP-complete problem: http://en.wikipedia.org/wiki/Clique_problem. You may also find answers in this highly related question http://stackoverflow.com/questions/2801138/find-all-complete-sub-graphs-within-a-graph – Hooked Apr 03 '13 at 14:05
  • ty @Hooked, for relevant comment! – Bogdan M. Apr 03 '13 at 14:17

1 Answers1

0

graph G"(V",E") is a sub-graph of graph G(V,E), if:

  1. V" is a sub-set of V

  2. E" must have all Edges from E, which connect 2 vertices that exist in V"

Storing all sub-graphs of any number of vertices Space Complexity:

TIME & SPACE = SUM { k * (|V|-k+1) } for k: 1..|V|

TIME & SPACE = 1/6 n (n+1) (n+2)

TIME & SPACE ~ O(|V|^3 + |V|^2 + |V| + ..)

In English, you will need huge amount of space, to keep all possible sub-graphs of G.

TIME & SPACE ~ SUM { (|V|-k+1) * SPACE(Gk) }
    for k: 1..|V|, SPACE(Gk): size of sub-graph with k nodes

The algorithm to obtain all possible sub-graphs is a brute-force algorithm ..

algorithm (in Java):

public class SubGraphs
{
    public static ArrayList<Graph> getAllSubsets (Graph g)
    {
        // i: 1,2,3 .. |V|
        for (int i=1; i<graph.V.size(); i++)
        {
            addSubsets(subsets, i);
        }
    }

    public static void addSubsets (ArrayList<Graph>, int i)
    {
        // generate all k-permutations from set V
        ArrayList<Node[]> perm = generateAllPerm(graph.V, graph.V.size()-i);

        // Ex: abc ~ 3:abc ; 2:ab,ac,bc ; 1:a,b,c
        for (Node[] p : perm)
        {
            subsets.add(removeVerticesFromGraph(graph, p));
        }
    }
}
Khaled.K
  • 5,828
  • 1
  • 33
  • 51