CODEWITHSUNDEEP
algorithmgraphbrute-forcesubgraph
Cristo
Cristo

Reputation: 21

How to obtain all the subgraphs from a graph?

How to obtain all the subgraphs of a fixed size from a graph, in pseudocode? (brute force)

Without external libraries if possible. Thanks!

Upvotes: 1

Views: 2456

Answers (3)

mayur_narkhede
mayur_narkhede

Reputation: 1

If you are using in terms of boost subgraph i have a follwing solution to iterate all subgraphs and prepare its vector.

// declare the list types
vector<SubGraph*> m_vecSubgraphContainer;
vector<SubGraph*> m_vecBFSOrderedSubgraphs; 

// construct container of subgraph lists in the vector
m_vecSubgraphContainer.push_back(&gInputGraph);

m_vecBFSOrderedSubgraphs.push_back(&gInputGraph);
iterateChildrenGraphs(m_vecBFSOrderedSubgraphs);

// iterating the subgraphs
for(vector<SubGraph*>::iterator itrSubgraph = m_vecSubgraphContainer.begin();
    itrSubgraph != m_vecSubgraphContainer.end();
    ++itrSubgraph)
{
    // for empty graph add dummy node to that graph
    int iNumVertices = num_vertices(**itrSubgraph);
    if(iNumVertices == 0)
    {
        VertexDescriptor vVertex = m_boostGraphWrapper.addVertex(**itrSubgraph, Enum::InvisibleNode);
        // This dummy node will set the size of cluster
        // set height = 80 nd width = 80;
        int iDummyNodeHeight = 80;
        int iDummyNodeWidth = 80;
        m_boostGraphWrapper.setVertexHeight(vVertex,**itrSubgraph, iDummyNodeHeight);
        m_boostGraphWrapper.setVertexWidth(vVertex, **itrSubgraph, iDummyNodeWidth);
    }
}

void CircularLayoutGenerator::iterateChildrenGraphs(vector<SubGraph *> &subgraphQueue)
{
/*
    we have used queue because it will contains reference of subgraphs.
    adding all the subgraphs in queue to iterate one by one in circular way.
*/

// define local queue which will contains the childrens of main graph
vector<SubGraph*> SubgraphSequence;

try
{
    // To iterate input queue which will contain graph reference
    for( vector<SubGraph*>::iterator itrSubgraphQueue = subgraphQueue.begin();
         itrSubgraphQueue != subgraphQueue.end();
         itrSubgraphQueue++)
    {
        // Finding the children upto deep level
        SubGraph::children_iterator itrSubgraph, itrSubgraphEnd;
        for (boost::tie(itrSubgraph, itrSubgraphEnd) = (**itrSubgraphQueue).children();
             itrSubgraph != itrSubgraphEnd;
             ++itrSubgraph)
        {
            // Add children in the global queue container
            m_vecSubgraphContainer.push_back(&(*itrSubgraph));

            // Add children in the local queue conatainer
            SubgraphSequence.push_back(&(*itrSubgraph));
        }
    }
}

// To iterarte the local queue again if ant children is present
if(!SubgraphSequence.empty())
{
    // Recursive call to iterate children
    iterateChildrenGraphs(SubgraphSequence);
}
}

Upvotes: 0

pau.estalella
pau.estalella

Reputation: 2243

More or less that would be something along these lines:

GenerateSubgraphs(Graph G):
    powerV = powerset(G.V)
    powerE = powerset(G.E)
    subgraphs = {}
    foreach V in powerV:
        foreach E in powerE:
            accept = true
            foreach edge in E:
                if edge.u not in V or edge.v not in V:
                    accept = false
            if accept:
                subgraphs.insert((V, E))
    return subgraphs

EDIT: Fixed indentation of 'edges.insert' line

EDIT: Removed duplicated graphs

Upvotes: 4

avpx
avpx

Reputation: 1922

Since a graph is only edges and vertices, find all possible subsets of the vertices and construct all possible subsets of the edges on them.

Upvotes: 1

Related Questions