Accedi per seguire   
Seguaci 0
scaloppa

Definire Se Un Grafo è Bipartito O Meno.

30 messaggi in questa discussione

Ciao ragazzi e anke ragazze. Mi chiamo Annalisa (chiamatemi pure Anna... :P ). Sono iscritta al terzo anno di informatica all'università e mi sono ritrovata ad affrontare il corso di algoritmi e strutture dati :locked: . Premetto che questo corso mi sta conciando x le feste :P piu o meno cosi inosmma...

Mi ritrovo a dovere fare un progettino...

Vi indico il testo...magari potreste aiutarmi...

Si consideri un grafo G = (V,E) non orientato. Si implementi l'algoritmo che dica se un grafo è bipartito o meno. Il programma dovrà leggere l'input da un file chiamato input.txt che contiene la matrice di adiacenza del grafo.

Per caso sapreste aiutarmi un pochino...?? :P

X favore...sono disperata...

L'esame è tra 9 giorni...

Bacio a tutti coloro che mi aiuteranno... :wub:

Spero di sentirvi presto...Ciao Anna :)

Esercizio_di_Java_da_consegnare.pdf

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

[ben]scaloppa[/ben] :P:P:)

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Ciao pollicina grazie del benvenuto...mi sono data un po da fare...anke se ancora ne ho parecchio...meno male...che anke qui...ci uniamo...x farci un po forza...

Ragazzi...mi rendo conto che il programma è difficile...se anke riuscite a darmi qualke suggerimento...su come impostarlo...o se trovate qualcosa sul web...vi prego AIUTATEMI...

Ciao ancora e grazie Pollicina...BAci Anna

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti
Ciao pollicina grazie del benvenuto...mi sono data un po da fare...anke se ancora ne ho parecchio...meno male...che anke qui...ci uniamo...x farci un po forza...

Ragazzi...mi rendo conto che il programma è difficile...se anke riuscite a darmi qualke suggerimento...su come impostarlo...o se trovate qualcosa sul web...vi prego AIUTATEMI...

Ciao ancora e grazie Pollicina...BAci Anna

Ciao Anna... Quanto ti capisco... Il 6 febbraio devo dare l'esame di Algoritmi e Strutture Dati!!! Non ho mai odiato la programmazione come in questi giorni...

Premesso, non ho la soluzione al tuo esercizio... Ma possiamo iniziare a studiarla assieme se vuoi :)

Partiamo dalla definizione di

Grafo Bipartito

Questo tipo di grafo ha la particolarità che l'insieme dei suoi vertici può essere diviso in 2 insiemi tali che ogni vertice del primo insieme è adiacente ESCLUSIVAMENTE a vertici del secondo insieme...

Adesso un'idea potrebbe essere quella di modificare l'algoritmo di visita del grafo...

Ora come ora mi viene in mente un approccio per un grafo connesso... Attraverso un algoritmo di visita con coda che colora i nodi in adiacenti di due colori diversi, e poi crea due insiemi di vertici distinti per colore... Se alla fine, lo stesso nodo si trova sia nell'insieme di vertici di un colore che in quello dell'altro, allora il grafo non è bipartito...

P.S. E' un'idea stralunata che mi è venuta in mente adesso... :P prendila solo come spunto di partenza...

E' possibile utilizzare due flag (white e black) per ogni vertice del grafo. L'algoritmo si può così fermare anche prima, appena un vertice viene marcato coi due colori (e quindi il grafo di partenza non è bipartito).

Se applichiamo questo algoritmo per ogni componente connessa del grafo, l'abbiamo reso funzionante sia per grafi connessi che per quelli sconnessi...

Fammi sapere che ne pensi o se sto sparando delle cavolate gigantesche :P

In bocca al lupo per l'esame!!!

P.P.S. Tra noi si nasconde un losco personaggio che ha preso 30 a quell'esame :locked: :locked: :locked:

Modificato da Prozac

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Ciao Anna, io quell'esame l'ho dato, dire che è stato un parto sarebbe un eufemismo, ad ogni modo mi sono scaricato il tuo file e, sebbene abbia una pseudosoluzione in mente (ma non ne sono sicuro) provo a darci uno sguardo stasera. Guarda ti capisco benissimo e capisco l'amico Prozac (:P), purtroppo i problemi di algoritmi sono fatti per chi ha guizzi particolarmente brillanti :P, non c'è mai una procedura univoca per risolverli ... AHIME' ...

:)

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti
Ciao Anna, io quell'esame l'ho dato, dire che è stato un parto sarebbe un eufemismo, ad ogni modo mi sono scaricato il tuo file e, sebbene abbia una pseudosoluzione in mente (ma non ne sono sicuro) provo a darci uno sguardo stasera. Guarda ti capisco benissimo e capisco l'amico Prozac ( :P ), purtroppo i problemi di algoritmi sono fatti per chi ha guizzi particolarmente brillanti :P , non c'è mai una procedura univoca per risolverli ... AHIME' ...

:)

Azz... io manco l'avevo visto l'allegato :wub:

Predator, non ti piace la mia idea?

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Prozac...Predator....siete troppo gentili vi state sbattendo un cifro x aiutarmi...grazie mille...

Allora l'idea mi sembra buona quella dei flag...se poi riusciamo anke a produrre insieme un codice java...sarebbe ottimo...perchè c'ho una paura boia di sbalgiare tutto...e non mi va di rafarlo sto esame...perché se lo sego...sono finita...

Raga...vero che ce la faccio...??

Sicuramente si grazie al vostro aiuto...

Baci baci baci

Anna. :)

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti
Prozac...Predator....siete troppo gentili vi state sbattendo un cifro x aiutarmi...grazie mille...

Allora l'idea mi sembra buona quella dei flag...se poi riusciamo anke a produrre insieme un codice java...sarebbe ottimo...perchè c'ho una paura boia di sbalgiare tutto...e non mi va di rafarlo sto esame...perché se lo sego...sono finita...

Raga...vero che ce la faccio...??

Sicuramente si grazie al vostro aiuto...

Baci baci baci

Anna. :)

Ehm, Anna... Io pure sono nella tua stessa condizione... Solo che l'esame ce l'ho il 6!!! Aiutooooooooo

Certo che lo passi!!!

Adesso non ci riesco a mettermi su con Java... Magari domani ci provo... :P

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Ehm, Anna... Io pure sono nella tua stessa condizione... Solo che l'esame ce l'ho il 6!!! Aiutooooooooo

Certo che lo passi!!!

Adesso non ci riesco a mettermi su con Java... Magari domani ci provo... :)

[ot]

in bocca al lupo a tutti e due allora :P

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

[ot]

in bocca al lupo a tutti e due allora :)

CREPI!!!

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

crepi .....

Stamattina mi do alla teoria...inizio a ripassarla...

Magari pome incomincio a buttare giu qualke cosa...

Vedo l'idea di una profondita bianco e nero mi piace...

Ma come si fa a prendere la matrice in input da un file??Quello non l'ho mai fatta...

Aiuto....quante cose sconosciute...

Baci Baci BAci

Vi voglio bene a tutti :)

Che matta che sono ... :P

Baci Anna

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Oki, ho elaborato una mia teoria per la risouzione (Prozac certo che mi piace la tua idea, solo che a me a primo acchito me ne era venuta in mente un'altra che ho sviluppato (a livello concettuale)), più che altro volevo dare anche un'alternativa, ma poi ognuno sceglie quello che vuole, d'altronde algoritmi insegna che la strada non è mai una (sarebbe bello vederne almeno una però :P ).

Ok provo a spiegare in poche parole cosa vorrei fare io:

IDEA:

- Cominciamo col notare che il grafo ha due buone caratteristiche, ossia è connesso e non orientato, il che ci semplifica di molto la procedura.

- Notiamo che la matrice di adiacenza ci dà già delle buone informazioni (anche perchè non so se abbiamo a disposizione il formato "a puntatori" del grafo")

- Dato che è connesso possiamo semplificare la matrice semplicemente prendendo la triangolare superiore o inferiore (ricordiamoci che il grafo è non orientato tale per cui se (u,v) appartiene a E anche (v,u) appartiene ad E), in tal senso ricordiamoci anche la definizione di triangolare

matrice1if.jpg

- Ora partendo dalla definizione di grafo bipartito possiamo dedurre che, scandendo la prima riga della matrice triangolare

----- Se troviamo uno 0 nella posizione (1,j) allora non ci sono collegamenti tra il primo nodo e il nodo j (dacchè se ne deduce che potrebbe appartenere alla eventuale componente del grafo bipartito che contiene il nodo 1)

----- Se troviamo un uno 1 (in (1,j)) sappiamo che è collegato con quel nodo e quindi eventualmente possiamo suppore appartenga alla seconda componente del grafo bipartito (V2 nel foglio).

Partendo da questo ragionamento si potrebbe pensare di scandire solo la prima riga e tenere traccia degli uno e degli 0 (magari copiando le posizioni su 2 array di supporto diversi) e andare poi a verificare se gli elementi siano o meno collegati tra di loro (magari ricorsivamente ma penso si possa procedere anche iterativamente :wub: ).

Faccio un esempio.

- la prima riga contiene 0 1 0 1 0

- l'array A (di supporto) conterrà a fine scansione i valori 2 e 4 (in C++ o java altrimenti in pseudocidice le posizioni diventano 3 e 5) corrispondenti agli 0 (escluso la posizione 0 che non ci interessa sapere che un nodo è collegato con se stesso :P )

- B sarà chiaramente complementare ad A (cioè dove non c'è un 0 ci sarà sicuramente un 1 ;) )

Ora sappiamo che 1 non è collegato con 3 e 5 e dobbiamo verificare che non siano collegati tra di loro (se lo sono non è un grafo bipartito) e poi verificare che 2 e 4 non siano collegati tra di loro.

Questa è grosso modo la mia idea, non mi sembra un granchè ma il ragionamento fila :P .

Per leggere da File in java devi crearti un Stream di ouput dal file stesso, le classi da usare sono grosso modo queste, ma dovrei provarlo un attimo: http://java.sun.com/docs/books/tutorial/es...ilestreams.html, magari stasera un po' di codice riesco a metterlo giù :(

:)

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Predator grande spiegazione.....ti meriti un bacino supplementare :P

Cmq...leggendo è un complicato...cioè mi risultava piu semplice da creare quello con i vertici bianchi e neri.

CMq...oggi mi metto a leggere x bene la tua soluzione (che sembra piu da figaccioni...) e domani incomincio a mettere giu un po di programma...

Se riuscite a produrre un po di codice...mi aiutereste un cassino... :)

Devo ammettere...che ho trovato dei grandissimi amici...siete tutti gentilissimi con me...

Spero davvero di non deludervi...

Grazie ancora e al prossimo messaggio... baci baci baci

Anna :P

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Ciao Anna...

Non ho fatto ne la versione in Java ne quella con matrice di adiacenza...

Visto che sto preparando l'esame pure io, ho preso spunto dal tuo esercizio per realizzarne uno simile che sfrutti le liste di adiacenza... L'ho scritto in C# (è molto simile a Java però)...

Questa è la funzione isBipartitic() (liberamente tradotto dall'italiano :P:P:wub: )

class Vertex
{
	public static int NOTHING = 0;//00
	public static int FIRST = 1;  //01
	public static int SECOND = 2; //10
	public static int BOTH = 3;   //11

	public List<Vertex> adj;

	public int flags = NOTHING;
	public Vertex predecessor = null;

	public int value = 0;

	public Vertex(int value)
	{
		this.value = value;
	}
}

class Graph
{
	Vertex[] v;

	public Graph(Vertex[] v)
	{
		this.v = v;
	}

	public bool isBiparitic()
	{
		//Potrebbe anche essere bipartito...
		bool ret = true;

		//Inizializzo tutti i vertici del grafo:
		foreach (Vertex u in v)
		{
			u.flags = Vertex.NOTHING;		//Non appartiene a nessuno dei 2 sottografi
			u.predecessor = null;				//Non ha predecessore
		}

		foreach (Vertex s in v)					 //Per ogni vertice trovo la strada a tutti i suoi adiacenti
		{													//Serve per poter gestire grafi non connessi. Vengono, 
			if (s.flags == Vertex.NOTHING)	//comunque, saltati i vertici già controllati.
			{												//Inizializzo il vertice di riferimento.
				s.flags = Vertex.FIRST;		   //Lo metto nel primo gruppo
				s.predecessor = null;			  //Non ha predecessori
				Queue<Vertex> q = new Queue<Vertex>();
				q.Enqueue(s);						//inserisco il vertice nella coda
				while (q.Count > 0)				 //Finchè avrò vertici da controllare, rimango in questo
				{										   //sottografo connesso.
					Vertex x = q.Peek();		  //Recupero dalla coda il vertice da controllare
					if (x.adj != null)
					{
						foreach (Vertex u in x.adj)	   //Per ognuno degli archi che partono da questo
						{										   //vertice
							if ((x != u) && (x.predecessor != u))   //Se l'arco non finisce ne in un cappio
							{													//ne nel suo predecessore 
								if (u.flags == Vertex.NOTHING)	//Se l'arco finisce in un vertice che non
																				//appartiene ad alcun gruppo
									u.flags = x.flags ^ Vertex.BOTH;  //Lo metto nel gruppo opposto:
																					//01^11 = 10  e 10^11 = 01
								else if (u.flags  == x.flags)			   //Altrimenti, se i nodi appartengono 
								{												   //già allo stesso gruppo
									u.flags = Vertex.BOTH;			  //metto i loro 2 flag a
									x.flags = Vertex.BOTH;			  //BOTH.
									ret = false;								//Ed il metodo mi ritorna false
								}
								if (u.flags < Vertex.BOTH)		  //Se il vertice dall'altra parte dell'arco non 
																	//appartiene allo stesso gruppo di quello che sto
								{								   //controllando, imposto quest'ultimo come 
									u.predecessor = x;	// predecessore e lo inserisco nella coda			 
																   //(dobbiamo vedere se ha degli archi ba*****i)!!!
									q.Enqueue(u);
								}
							}
						}
					}
					q.Dequeue();
				}
			}
		}

		return ret;
	}
}

Come puoi vedere dal codice, Il programma prevede 2 classi.

Una descrive i vertici (e contiene i flags) e la lista di adiacenza per ogni vertice

L'altra definisce il grafo che contiene esclusivamente il vettore dei vertici V...

Fammi sapere che ne pensi...

La complessità del metodo dovrebbe essere O(V+E) come tutte gli algoritmi di visita sui grafi...

:)

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

:) Grazie Prozac...inziio a darci un occhiatina...

Intanto vedo se va...e inizio a farci qulke modifica... :omaggi:

giusto x usare le matrici e il resto...grazie bacino supplementare a nke a te...

Domani mattina ci lavoro su e vi faccio sapere come va il programmino :-) :regole:

Speriamo bene :-)

Baci baci baci a tutti....siete troppo gentili...

CIao Anna :P

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Lo accetto volentieri il bacino Anna :P:P

Comunque il mio ragionamento ha un bug che ho risolto , nel pomeriggio ti posto una soluzione divertente al problema (divertente nel senso che sembra un giochino :P), se riesco te ne faccio un'implementazione Java :wub:

@Prozac: Complimenti per la soluzione :), veramente bella, sfruttando le liste di adiacenza togli molta complessità all'algoritmo, il punto è che non sapevo se l'esercizio lo permetteva <_<

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti
Lo accetto volentieri il bacino Anna :P:P

Comunque il mio ragionamento ha un bug che ho risolto , nel pomeriggio ti posto una soluzione divertente al problema (divertente nel senso che sembra un giochino :P ), se riesco te ne faccio un'implementazione Java :wub:

@Prozac: Complimenti per la soluzione :) , veramente bella, sfruttando le liste di adiacenza togli molta complessità all'algoritmo, il punto è che non sapevo se l'esercizio lo permetteva <_<

L'esercizio parlava di matrice d'adiacenza, ma io stavo studiando le implementazioni con liste e ne ho apporfittato per farmi un esercizio tutto mio...

Non penso ci siano troppe difficoltà nell'adattarlo per le matrici... Se ho tempo mi ci metto per bene ;)

P.S.

Il mio algoritmo dovrebbe funzionare sia con grafi connessi che non connessi, orientati e non orientati... Alla fine, l'oggetto di classe Graph contiene un array di vettori per ognuno dei quali è segnata l'appartenenza ad uno o all'altro sottografo... (oppure se appartiene ad entrambi i sottografi, anche se il dono dell'ubiquità non esiste...). In questo modo è semplice creare i due sottoinsiemi chiesti dall'esercizio:

if (grafo.isBiparitic())
{
List<Vertex> v1 = new List<Vertex>();
List<Vertex> v2 = new List<Vertex>();
foreach (Vertex u in grafo.v)
	{
			if (u.flags == Vertex.FIRST)
				v1.Add(u);
		   else
				v2.Add(u);
	}
}

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Salve a tutti, ho appena letto il quesito e la soluzione di Prozac, mi impegno a dargli un'occhiata stasera ed a postare "l'eventuale" correzione...

Per adesso, vi auguro un grosso in bocca al lupo a tutti e 2....

:)

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Ciao Ragazzi come state??Anke ragazze....mica esistete solo voi :P

Non ci crederete ma...HO INIZIATO A PRODURRE IL PROGRAMMA... :)

Ieri mi sono messa di impegno e ho iniziato a scrivere....

Ho utilizzato questo metodo.

Ho preparato un programma che sfruttando le matrici di adiacenza e inserendo io a mano archi e vertici mi costruisce il grafo e fa il controllo x buttare fuori la vista DFS. Ora sto ridefinendo il fatto che sia bipartito. Ma stamattina non ho tempo ci lavoro pome e se riesco ve lo posto prima di sera. Ho utilizzato il metodo di colorare i vertici in 2 modi differenti (che poi sono 3 :-p perché il colore iniziale è cmq importante :wub: ).

Poi al massimo mi date una mano x metterci la lettura dal file esterno ok? :leggi:

UN bacio a tutti....

Ciao Anna :P

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Guarda per la lettura da file avevo fatto questo, anche se ti "sputa fuori" una matrice di booleani, modificandolo leggermente dovresti riuscire a leggere solamente invece di utilizzare strutture dati in più.

Per quanto riguarda l'algoritmo l'avevo anche scritto, ma aveva un problemino che dovrei risolvere, comunque se vuoi fare l'altra strada liberissima :P, il costo dell'algoritmo viene lo stesso perchè per tramutare da matrice di adiacenza a grafo la complessità è O(v^2)

MatrixFileReader.java

package it.unitn.science.Algoritmi;

import java.io.*;

/**
* <p>Title: BipartiteGraph</p>
*
* <p>Description: Controllo di un grafo bipartito</p>
*
* <p>Copyright: Copyright (c) 2006</p>
*
* @author Predator
* @version 1.0
*/
public class MatrixFileReader {
private File f;

/**
 * Costruttore della classe e wrapping del file in un buffer di inupt
 * @param f File Il file di testo da leggere
 * @throws FileNotFoundException Lancia un'eccezione se il file non esite o non è stato trovato
 */
public MatrixFileReader(File f) throws FileNotFoundException {
	this.f = f;
}

/**
 * Costruttore della classe utilizzando una stringa come path del file
 * @param file String Path del file
 * @throws FileNotFoundException Eccezione se il file non è stato trovato
 */
public MatrixFileReader(String file) throws FileNotFoundException {
	if (!file.endsWith(".txt")) {
		throw new IllegalArgumentException("Il file non ha estensione txt");
	}
	this.f = new File(file);
}

/**
 * Restituisce il numero di nodi complessivi
 * @return int Numero di nodi
 * @throws IOException Errore accesso al file non riuscito
 */
public int getMatrixLength() throws IOException {
	int count = 0, i = 0;
	BufferedReader br = new BufferedReader(new FileReader(f));
	String s = br.readLine();
	while (i != s.length()) {
		if (s.charAt(i) == '1' || s.charAt(i) == '0') {
			count++;
		}
		i++;
	}
	br.close();
	return count;
}

/**
 * Restituisce la matrice booleana del file considerato
 * @return boolean[][] Matrice di adiacenza del grafo
 * @throws IOException Errore accesso al file non riuscito
 */
public boolean[][] getMatrix() throws IOException {
	int len = this.getMatrixLength(), k = 0;
	boolean adj[][] = new boolean[len][len];
	BufferedReader br = new BufferedReader(new FileReader(f));
	String line = br.readLine();
	while (line != null) {
		int i = 0, j = 0;
		while (i != line.length()) {
			if (line.charAt(i) == '1') {
				adj[k][j] = true;
				j++;
			}
			if (line.charAt(i) == '0') {
				adj[k][j] = false;
				j++;
			}
			i++;
		}
		line = br.readLine();
		k++;
	}
	br.close();
	return adj;
}
}

:)

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Ho messo apposto l'agoritmo e ora funziona (in teoria :P), utilizza una tecnica completamente diversa da quella di Prozac, anche se il ragionamento è simile (a graaaandi linee), se non ti serve non importa, puoi sempre presentarlo come alternativa :angel_not:

BipartiteGraph.java

package it.unitn.science.Algoritmi;

import java.io.*;

/**
* <p>Title: BipartiteGraph</p>
*
* <p>Description: Controllo di un grafo bipartito</p>
*
* <p>Copyright: Copyright (c) 2006</p>
*
* <p>Company: </p>
*
* @author Predator
* @version 1.0
*/
public class BipartiteGraph {
private MatrixFileReader file;
private boolean v1[], v2[];

public BipartiteGraph(File f) throws FileNotFoundException {
	file = new MatrixFileReader(f);
}

public BipartiteGraph(String s) throws FileNotFoundException {
	file = new MatrixFileReader(s);
}

/**
 * Funzione principale che contiene l'algoritmo di verifica se il grafo è bipartito oppure no
 * @return boolean True se è bibartito, False altrimenti
 * @throws IOException Se si ottiene qualche errore con il file
 */
public boolean isBipartite() throws IOException {
	int len = file.getMatrixLength();
	v1 = new boolean[len];
	v2 = new boolean[len];
	boolean adj[][] = file.getMatrix();
	for (int i = 0; i < len; i++) {
		v1[i] = v2[i] = false;
	}
	v1[0] = true;
	for (int i = 0; i < len; i++) {
		for (int j = i + 1; j < len; j++) {
			if (v1[i] == true) {
				if (adj[i][j] == true) {
					if (v1[j] == true && v2[j] == false) return false;
					v1[j] = false;
					v2[j] = true;
				} else {
					v1[j] = true;
				}
			} else if (v2[i] == true) {
				if (adj[i][j] == true) {
					if (v2[j] == true && v1[j] == false) return false;
					v2[j] = false;
					v1[j] = true;
				} else {
					v2[j] = true;
				}
			} else {
				return false;
			}
		}
	}
	return true;
}

/**
 * Stampa degli evetnuali sottografi del grafo bipartito
 * @throws NullPointerException Se gli array passati sono vuoti
 */
public void printSubgraphs() throws NullPointerException {
	System.out.print("V1 = { ");
	for (int i = 0; i < v1.length; i++) {
		if (v1[i] == true) {
			System.out.print(i + " ");
		}
	}
	System.out.println("}");
	System.out.print("V2 = { ");
	for (int i = 0; i < v2.length; i++) {
		if (v2[i] == true) {
			System.out.print(i + " ");
		}
	}
	System.out.println("}");
}
}

App.java

package it.unitn.science.Algoritmi;

import java.io.*;

/**
* <p>Title: BipartiteGraph</p>
*
* <p>Description: Controllo di un grafo bipartito</p>
*
* <p>Copyright: Copyright (c) 2006</p>
*
* <p>Company: </p>
*
* @author Predator
* @version 1.0
*/
public class App {
public App() {
}

public static void main(String[] args) {
	App app = new App();
	try {
		BipartiteGraph bg = new BipartiteGraph(System.getProperty(
				"user.dir") + "\\input.txt");
		if (bg.isBipartite()) {
			System.out.println("Il grafo è bipartito");
			bg.printSubgraphs();
		} else {
			System.out.println("Il grafo non è bipartito");
		}

	} catch (FileNotFoundException e) {
		e.printStackTrace();
	} catch (IOException ex) {
		System.out.println("Operazione sul file non valida");
	}

}
}

Spero riesca a capire il ragionamento anche se devo ancora controllarlo per il meglio :P

:)

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti
Ciao Ragazzi come state??Anke ragazze....mica esistete solo voi :P

Non ci crederete ma...HO INIZIATO A PRODURRE IL PROGRAMMA... :)

Ieri mi sono messa di impegno e ho iniziato a scrivere....

Ho utilizzato questo metodo.

Ho preparato un programma che sfruttando le matrici di adiacenza e inserendo io a mano archi e vertici mi costruisce il grafo e fa il controllo x buttare fuori la vista DFS. Ora sto ridefinendo il fatto che sia bipartito. Ma stamattina non ho tempo ci lavoro pome e se riesco ve lo posto prima di sera. Ho utilizzato il metodo di colorare i vertici in 2 modi differenti (che poi sono 3 :-p perché il colore iniziale è cmq importante :wub: ).

Poi al massimo mi date una mano x metterci la lettura dal file esterno ok? :leggi:

UN bacio a tutti....

Ciao Anna :P

Molto volentieri (B)

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Cavoli hai prodotto x davvero...

Ma grazieeeeeee :):P:P:wub:

Io avevo quasi finito il mio...però a sto punto ve lo devo fare vedere... se no mi arrabbio :locked: :P

Scherzo...grazie mille...pomeriggio finisco il mio provo il tuo e vediamo cosa ne risolvo ok??

Ciao un bacio a tutti Anna...

PS: Mi avete mandato il messaggiox diventare admin...purtroppo non posso...però ho un amico molto bravo...un mio compagno di univ...lui magari potrebbe essere interessato tra l'altro è molto professional...Lo faccio perché mi dispiacerebbe lasciarvi a mani vuote specie dopo tutto quello che avete fatto x me :dia: .

Fatemi sapere...che intanto gli inizio a dare il sito..e. gli dico di reg al forum... CIao Anna

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Bravi, sn contento delle vostre soluzioni. Purtoppo non ho potuto approfondire l'argomento... Nn trovo + i libri di testo.... peccato. Sn cose che ahimè nn tocco + da 6 anni... :P

Ho provato anche a :), ma nulla...

Le 2 soluzioni proposte fin ora sono veramente valide.

In, bocca a lupo a tutti.

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Ciao Raga...come state??Innanzitutto buona settimana a tutti.

Vi informo che il programma fatto da predator funziona alla perfezione...domani vi posto il mio...non è finito...però ci tengo a farvi vedere che qualcosa ho fatto anke io :-p.Tra l'altro...ho fatto una modifica al tuo predator nel senso che ho portato tutte le classi nel file della public class App perché devo consegnare un solo file...

GRAZIE MILLE CMQ DI TUTTO...

Domani avviso il mio amico ... appena riesce si registra e velo facio entrare in community...lo faccio passare di qua...cosi si presenta nu po anke lui :-)

Ciao A tutti buonanotte vista l'ora Anna :omaggi:

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Crea un account o accedi per lasciare un commento

Devi essere un utente registrato per partecipare

Crea un account

Iscriviti per un nuovo account nella nostra community. È facile!


Registra un nuovo account

Accedi

Sei già registrato? Accedi qui.


Accedi Ora
Accedi per seguire   
Seguaci 0